粒子群算法求解物流配送路線問(wèn)題（python）

1.查找論文文獻(xiàn)

找一篇物流配送路徑優(yōu)化+粒子群算法求解的論文

參考文獻(xiàn)：基于混沌粒子群算法的物流配送路徑優(yōu)化

2.了解粒子群算法的原理

講解通俗易懂，有數(shù)學(xué)實(shí)例的博文：https://blog.csdn.net/daaikuaichuan/article/details/81382794
可參考文獻(xiàn)：車輛路徑問(wèn)題的粒子群算法研究
里面給出了粒子群算法求解一般VRP問(wèn)題的算法實(shí)現(xiàn)步驟。

3.確定編碼方式和解碼策略

3.1編碼方式

物流配送路線的粒子編碼方式：

3.2解碼策略

例如 ， 假如一個(gè)有 7個(gè)客戶點(diǎn)， 3臺(tái)車輛的物流配送問(wèn)題 ，
其第 i 個(gè)粒子的位置向量 z如表 1所示

4.算例的輸入?yún)?shù)

5.處理關(guān)鍵技術(shù)

5.1將不可行解轉(zhuǎn)化為可行解

在迭代過(guò)程中形成的粒子可能是不滿足數(shù)學(xué)模型約束條件的不可行解，要將進(jìn)化生成的不可行解轉(zhuǎn)變?yōu)榭尚薪狻?/p> def get_feasible_x(x):# 修正粒子為滿足約束的可行解粒子，超過(guò)其范圍時(shí)按邊界取值vehicle_element = np.rint(x[:demand_node_num]) # 取整數(shù)表示哪輛車拜訪哪個(gè)客戶點(diǎn)for index in range(len(vehicle_element)):# x_bound = [[1, vehicle_num], [1, demand_node_num]] # 自變量的上下限限制if vehicle_element[index] < x_bound[0][0]:vehicle_element[index] = x_bound[0][0]elif vehicle_element[index] > x_bound[0][1]:vehicle_element[index] = x_bound[0][1]x[:demand_node_num] = vehicle_elementreturn x

判斷生成的粒子是否滿足車輛最大行駛里程數(shù)限制和車輛最大裝載量約束限制，若不滿足上述的兩個(gè)條件的其一，則隨機(jī)生成新的粒子直到滿足所有的約束條件。
文獻(xiàn)：車輛路徑問(wèn)題的粒子群算法研究
采用的方式是：對(duì)于有某條路徑上的各發(fā)貨任務(wù)的總需求量超過(guò)此條路徑配送車容量的不可行解，則將該方案的評(píng)價(jià)值置為一個(gè)可行解不可達(dá)到的極大值。

def get_feasible_solution(x):"""# 判斷是否滿足車輛最大行駛里程數(shù)限制和車輛最大載重量限制，若原粒子不滿足條件則生成滿足約束條件的可行解:param x: x為一個(gè)粒子:return:"""x = get_feasible_x(x)length, total_path_list = calculate_fitness(x)result_list = []for i in range(len(total_path_list)):path_list = total_path_list[i]path_length = 0for j in range(len(path_list)-1):segment = [path_list[j], path_list[j+1]]path_length += distance_graph[segment[0], segment[1]]if path_length > length_max:new_x = set_codeForm(1)[0]result_list.append(False)else:# 候選解滿足車輛行駛最大里程數(shù)要求，再判斷車輛的實(shí)際裝載量是否在最大裝載量范圍內(nèi)path_list = total_path_list[i][1:-1]capacity = sum([quantity_graph[j-1] for j in path_list])if capacity > capacity_max:new_x = set_codeForm(1)[0]result_list.append(False)else:result_list.append(True)if False not in result_list:return x, length, total_path_listelse:return get_feasible_solution(new_x)

5.2根據(jù)解碼規(guī)則計(jì)算適應(yīng)度函數(shù)值

優(yōu)化物流配送路徑問(wèn)題的粒子群編碼方式類似于遺傳算法的雙層整數(shù)編碼方式，第一層片段上面的數(shù)字表示客戶點(diǎn)由哪輛車來(lái)進(jìn)行配送，該表示方法的最大優(yōu)點(diǎn)是使每個(gè)客戶需求點(diǎn)都得到車輛的配送服務(wù)，并限制每個(gè)需求點(diǎn)的需求僅能由某一車輛來(lái)完成 ，使解的可行化過(guò)程計(jì)算大大減少；第二層利用數(shù)字的大小來(lái)確定車輛拜訪各個(gè)由它服務(wù)的客戶點(diǎn)的次序。
該算例的適應(yīng)度函數(shù)值為車輛的總行駛里程數(shù)最小。

def calculate_fitness(x):"""# 計(jì)算適應(yīng)度函數(shù):param x: x為一個(gè)粒子:return:"""# x = [[1.6,1.3,2.9,2.5,3.4,3.5,1.3,2,3,1,2,2,1,1]]total_path_list = []vehicle_element = x[:demand_node_num]path_element = x[demand_node_num:]actual_vehicle = list(set(vehicle_element))for j in range(len(actual_vehicle)):# customer_list表示第j輛車負(fù)責(zé)配送的客戶位置索引列表customer_list = np.where(vehicle_element == actual_vehicle[j])path_list = path_element[customer_list]path_list = [customer_list[0][customer_index] for customer_index in np.argsort(path_list)]path_list = [element + 1 for element in path_list]path_list.insert(0, 0)path_list.append(0)# path_list表示第j輛車訪問(wèn)各個(gè)客戶節(jié)點(diǎn)的拜訪順序total_path_list.append(path_list)# 0-3-1-2-0total_length = 0for path in total_path_list:for index in range(len(path)-1):segment = [path[index], path[index+1]]total_length += distance_graph[segment[0]][segment[1]]return total_length, total_path_list

6.算例結(jié)果

運(yùn)行python3程序，運(yùn)行環(huán)境為win64，pycharm2019.3.2，在某一次運(yùn)行中得到的算例結(jié)果如下：

全局最優(yōu)解結(jié)構(gòu)為： [1. 1. 1. 2. 1. 2. 2. 1. 4. 7. 6. 6. 6. 4. 4. 6.]
最優(yōu)路線長(zhǎng)度為： 67.5
最優(yōu)車輛運(yùn)行路線為： [[0, 1, 3, 5, 8, 2, 0], [0, 6, 7, 4, 0]]，表示車輛1的配送方案為：0-1-3-5-8-2-0（從配送中心0出發(fā)依次訪問(wèn)客戶點(diǎn)1、客戶點(diǎn)3、客戶點(diǎn)5、客戶點(diǎn)8和客戶點(diǎn)2，最后再返回配送中心）；車輛2的配送方案為：0-6-7-4-0。

參考文獻(xiàn)：
Matlab實(shí)現(xiàn)粒子群算法的程序代碼：https://www.cnblogs.com/kexinxin/p/9858664.html
matlab代碼求解函數(shù)最優(yōu)值：https://blog.csdn.net/zyqblog/article/details/80829043

numpy模塊中矩陣和數(shù)組的區(qū)別：https://www.cnblogs.com/wj-1314/p/10244807.html
random模塊的常用方法：https://www.cnblogs.com/liangmingshen/p/8909376.html
numpy模塊入門級(jí)用法介紹：
https://www.jianshu.com/p/3e566f09a0cf
matplotlib模塊簡(jiǎn)單使用技巧：https://www.cnblogs.com/bainianminguo/p/10952586.html
PYTHON 畫(huà)圖神器 Matplotlib：https://www.jianshu.com/p/c41ac57cea33

總結(jié)

以上是生活随笔為你收集整理的粒子群算法求解物流配送路线问题（python）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。