一、車輛路徑問題簡介與求解要求
交通運輸是國民經濟的動脈，各種運輸方式在日常運輸營運管理工作中都要面對這樣一個共同的問題：如何為載運工具(汽車，列車，輪船和飛機，統稱為車輛)确定行駛路線及時間，有效地運送各站點間的旅客和貨物。運籌學界将此類問題統稱為車輛路徑問題（Vehicle Routing Problem, VRP）。
VRP最早由Dantzig于1959年首次提出，指一定數量的客戶，有各自的貨物需求，配送中心（車場）組織車輛向客戶提供貨物，設計最優的行車路線，以滿足客戶的需求，并達到路程最短、成本最小、耗費時間最少等目标。VRP示意圖如下：
本文内容求解所涉及的要求為：自己開發求解VRP的算法（什麼算法都行：單純型、蟻群、遺傳、鄰域搜尋、模拟退火、禁忌搜尋、神經網絡、深度學習、給定規則啟發式），與标準執行個體的最優解對比。
評價名額（重要度排序）：
1. 求解精度（與最優解的差距）；
2. 求解規模（顧客點的數量）；
3. 求解速度（運作時間）。
A-n32-k5.vrp，有31個顧客點，具體資料點選A-n32-k5.vrp的連接配接檢視（顧客點标号、坐标、需求量。其中1是車場）。最優目标是784，最優解有5輛車。
二、車輛路徑算法
1、遺傳算法介紹
本文我所選用的算法是遺傳算法，遺傳算法簡稱GA，在本質上是一種不依賴具體問題的直接搜尋方法，它是根據生物進化思想而啟發得出的一種全局優化算法，遺傳算法的概念最早是由Bagley J.D在1967年提出的，可是最開始研究遺傳算法的理論和方法的系統性研究是在1975年，在當時，這個算法的目的是說明自然和人類系統的自适應過程。
2、遺傳算法步驟
（1）生成初始種群。确定問題解表示的編碼方案，随機産生一組初始個體構成的初始種群。
（2）計算适應度。對于種群中的每一個體計算其适應度。
（3）選擇。更加适應度大小以一檔方式對種群執行選擇複制操作。
（4）交叉。按照交叉機率，對于種群執行交叉操作。
（5）變異機率。對種群執行變異操作。
3、流程圖
4、遺傳算法特點
（1）智能性：遺傳算法具有自組織、自适應和自學習 性等特性。遺傳算法的搜尋過程以目标函數為依據，并利用适應度函數，逐漸逼近目标值。
（2）全局最優性：遺傳算法由于采取交換操作和變異操作，進而在解空間便能産生出新的個體，進而擴大算法在解空間的搜尋範圍，并且遺傳算法從串集開始搜尋，覆寫面大，利于全局擇優，使得搜尋得到的結果不是局部最優解而是全局最優解
（3）不确定性：進化計算不确定性是伴随随機性而來的。在遺傳算法的主要步驟中即含有随機的因素，如變異的過程。是以在算法的進化過程中，事件發生與帶有很大的不确定性。
（4）并行性：遺傳算法可以同時搜尋解空間内的多個區域，同時，遺傳算法作為一種典型的進化算法，而進化算法本身就具有較好的并行性，适合于各種并行處理。
三、VRP數學模型
符号：
- 配送中心擁有的車輛台數m及每輛車的載重量（噸位）為Q；
- 需求點（也叫顧客點）個數為n及每個點的需貨量為Ri;
- 配送中心到各需求點的費用及各需求點之間的距離為dij。
目标：行駛總距離最小
決策變量：
四、遺傳算法結果分析
參考标準的執行個體庫，并根據執行個體庫中的資料，利 用兩種算法進行結果分析并與标準的最優解進行對比，同時分析産生一定誤差的原因。已知有1個車場和32個顧客點，同時每個顧客點的坐标和需求量如下所示，将初始車輛設定為25輛，利用matlab進行兩種算法的程式設計，求解出車輛的最短配送路徑以及最優解的車輛數。
1、資料表
| 顧客點編号 | 坐标 | 需求量 | 顧客點編号 | 坐标 | 需求量 |
| 1 | （82,76） | 17 | （88,51） | 18 | |
| 2 | （96,44） | 19 | 18 | （91,2） | 19 |
| 3 | （50,5） | 21 | 19 | （19,32） | 1 |
| 4 | （49,8） | 6 | 20 | （93,3） | 24 |
| 5 | （13,7） | 19 | 21 | （50,93） | 8 |
| 6 | （29,89） | 7 | 22 | （98,14） | 12 |
| 7 | （58,30） | 12 | 23 | （5,42） | 4 |
| 8 | （84,39） | 16 | 24 | （42,9） | 8 |
| 9 | （14,24） | 6 | 25 | （61,62） | 24 |
| 10 | （2,39） | 16 | 26 | （9,97） | 24 |
| 11 | （3,82） | 8 | 27 | （80,55） | 2 |
| 12 | （5,10） | 14 | 28 | （57,69） | 20 |
| 13 | （98,52） | 21 | 29 | （23,15） | 15 |
| 14 | （84,25） | 16 | 30 | （20,70） | 2 |
| 15 | （61,59） | 3 | 31 | （85,60） | 14 |
| 16 | （1,65） | 22 | 32 | （98,5） | 9 |
2、最優路線圖與最優目标趨勢圖
3、結果分析
從上面的結果圖形可以看出，遺傳算法無論是在求解品質、求解速度還是最優路徑的穩定性等方面都與标準執行個體的最優解大緻相同。可是對于遺傳算法來說，遺傳算法具有不确定性因素，如疊代的次數、變異的機率以及交叉的機率等，是以就算是相同參數設定也會得出不同的最優結果。是以還是選擇遺傳算法作為求解車輛路徑問題的最優算法，其最終實驗結果是從多次實驗結果中通過對比分析得到的一組最優解。
五、部分程式代碼
1、遺傳算法參數設定
alpha=10;
NIND=50;
MAXGEN=10000;
Pc=0.9;
Pm=0.05;
GGAP=0.9;
N=cusnum+v_num-1;
2、輸出随機解的路線和總距離
disp('初始種群中的一個随機值:')
[currVC,NV,TD,violate_num,violate_cus]=decode(Chrom(1,:),cusnum,cap,demands,dist);
currCost=costFuction(currVC,dist,demands,cap,alpha);
disp(['車輛使用數目：',num2str(NV),'，車輛行駛總距離：',num2str(TD),'，違反限制路徑數目：',num2str(violate_num),'，違反限制顧客數目：',num2str(violate_cus)]);
disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
相關資源：基于遺傳算法的車輛路徑問題
完整代碼請留言