一、簡介
1 車輛路徑問題概述
車輛路徑問題(vehicle routing problem，VRP)給定一組有容量限制的車輛的集合、一個物流中心（或供貨地）、若幹有供貨需求的客戶，組織适當的行車路線，使車輛有序地通過所有的客戶，在滿足一定的限制條件（如需求量、服務時間限制、車輛容量限制、行駛裡程限制等）下，達到一定的目标（如路程最短、費用極小、時間盡量少、使用車輛數盡量少等）。
以配送總裡程最短為目标函數，限制條件滿足：(1)每條配送路徑上各客戶的需求量之和不超過配送車輛的載重量；(2)每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離；(3)每個客戶的需求必須滿足，且隻能由一台配送車輛送貨。
2 遺傳算法
遺傳算法（Genetic Algorithm, GA）是一種較為經典的智能優化算法，經大量的研究表明，其在求解離散組合優化問題中有着優異的表現。遺傳算法的思想為優勝劣汰，通過交叉操作、變異操作獲得多樣性的解，在下一代中保留目标函數最優的解，并通過輪盤賭方式選擇下一代個體，不斷循環疊代，進而不斷優化問題的解。本文采用Matlab R2010b程式設計實作，遺傳算法求解車輛路徑問題的具體内容及步驟如下：
2.1 編碼操作
車輛路徑問題為離散優化問題，結合限制條件3：每個客戶的需求必須滿足，且隻能由一台配送車輛送貨，可以以客戶整數編号的排序進行編碼，保證每個客戶編号能且隻能出現一次。比如說：客戶數量為8，則編碼的染色體可以為1-2-3-4-5-6-7-8。
2.2 解碼操作
解碼操作需要在滿足限制條件1、2的前提下，将染色體解碼為車輛的配送路徑，為計算目标值做好準備。根據排列順序進行解碼，主要判斷該客戶加入到車輛配送路徑後，是否滿足該車的最大行駛距離，是否滿足該車的最大載重量。比如說染色體1-2-3-4-5-6-7-8，第1輛車路徑：将客戶1加入到該車的路徑中，則第1輛車的行駛路線為0-1-0，表示，該車從物流中心0出發，将貨物運到客戶1，再傳回物流中心，計算行駛距離是否滿足第1輛車的最大行駛距離，同時計算運貨量是否滿足第1輛車的最大載貨量，再确定客戶2如果加入第1輛車的路徑是否滿足以上2個條件，如果滿足，則第1輛車的行駛路線為0-1-2-0，依次類推，如果不滿足其中的1個條件，則需要增加1輛車即為從物流中心出發的第2條行駛路線。
2.3 計算目标值
根據解碼出來的車輛行駛路徑，計算目标值即為總配送裡程。但需要判斷解碼出來的行駛路徑的數量是否超過總車輛數，若未超過則按所有車輛路徑相加得到總配送裡程，若超過總車輛數，則說明該配送路徑不可行，該解為不可行解，因該問題為最小化優化問題，可通過罰函數增大目标值來淘汰掉該不可行解。
2.4 交叉操作
交叉操作是根據兩個父代的染色體資訊，根據交叉機率Pc交換某些片段，進而使父代的資訊能夠遺傳給子代，本質是根據父代的染色體資訊産生子代（新解），交叉操作的實作方式有多種，本文給出了一種交換染色體片段的交叉操作，如下圖所示。
2.5. 變異操作
變異操作是在父代的染色體資訊基礎上，根據變異機率Pm改變某些基因位，進而使整個染色體發生變化，該操作對染色體的改變程度小于交叉操作，變異操作的實作方式有多種，本文給出了一種單點位基因突變的變異操作，如下圖所示。
2.6. 選擇操作
選擇操作以目标值較好的染色體及随機産生的新染色體組成，在確定優良基因能傳遞給下一代的基礎上，通過随機産生的新解擴大染色體的多樣性。
2.7. 算法流程
遺傳算法求解車輛路徑問題的算法步驟如下：
3、算法驗證
執行個體1：某物流中心有2台配送車輛，其載重量均為8t，車輛每次配送的最大行駛距離為50Km，配送中心（編号為0）與8個客戶之間及8個客戶互相之間的距離dij、8個客戶的貨物需求量qj（i, j=1，2，……，8）見下表1。要求合理安排車輛配送路線，使配送總裡程最短。
根據以上問題的資料資訊，設定好遺傳算法的參數，通過遺傳算法求解該車輛路徑問題得到最有解為【1-3-5-6-4-7-2-8】，最短距離為【69.5】，解碼操作得到的車輛路徑為【0-1-3-5-6-0】、【0-4-7-2-8-0】。
二、源代碼
clc
clear
close all;
tic;
%%
%算法參數
population_num=80;%種群規模
Max_gen=200;%疊代次數
Pc=0.9;%交叉機率
Pm=0.09;%變異機率
%%
%問題參數
%車輛數量Car_num=2
%客戶數量Customer_num=8
%車輛容量capacity_max=8
%行駛距離distance_max=50
Car_num=2;
Customer_num=8;
capacity_max=8;
distance_max=50;
load Demand %客戶的需求
load Distance %客戶間的距離
load X %物流中心到客戶間的距離
%%
%種群初始化
population=zeros(population_num,Customer_num);
for i=1:population_num
population(i,:)=randperm(Customer_num);
end
%%
y=1;%循環計數器
while y<Max_gen
%交叉
[new_pop_intercross]=Mating_pool(population_num,population,Pc);
%變異
[new_pop_mutation]=Mutation(new_pop_intercross,Pm);
%計算目标函數
mutation_num=size(new_pop_mutation,1);
Total_Dis=[];
for k=1:mutation_num
[Result]=decode(new_pop_mutation(k,:),distance_max,capacity_max);
[Total_Dis(k,1)]=parameter(Result,Customer_num,Car_num);
end
%更新種群
new_pop_new=zeros(population_num,Customer_num);
[Total_Dissort, index] = sort(Total_Dis);
for k=1:population_num
new_pop_new(k,:)=new_pop_mutation(index(k),:);
end
population=new_pop_new;
%疊代次數加一
y=y+1;
end
function [new_pop_intercross]=Mating_pool(population_num,population,Pc)
%%
%輸入:population,population_num,Pc
%輸出：1.new_popopulation_intercross
% 2.c3，配對池：随機将種群population兩兩配對
% 3.pool
%%
pl=randperm(population_num);
num=population_num/2;
c3=zeros(2,num);
pool=[];
new_pop_intercross=population;
for kj=1:num
c3(1,kj)=pl(2*kj-1);
c3(2,kj)=pl(2*kj);
end%生成“配對池c3”
%%判斷“配對池c3”每一對個體的随機數是否小于交叉機率Pc
rd=rand(1,num);
for kj=1:num
if rd(kj)<Pc
pool=[pool,c3(:,kj)];
end
end
%%判斷配對池每一對個體的随機數是否小于交叉機率Pc,若小于，儲存到“産子池pool”1
pool_num=size(pool,2);
for kj=1:pool_num
c1=population(pool(1,kj),:);
c2=population(pool(2,kj),:);
[new_c1,new_c2]=cross(c1,c2);
new_pop_intercross(pool(1,kj),:)=new_c1;
new_pop_intercross(pool(2,kj),:)=new_c2;
end
end
function [Total_Dis]=parameter(Result,Customer_num,Car_num)
%% 解碼1
if Result(Customer_num,2)<=Car_num
Current_Workstation=1;
Total_Dis=0;
for i=1:Customer_num
if Result(i,2)==Current_Workstation;
continue
else
Total_Dis=Total_Dis+Result(i-1,3);
Current_Workstation=Current_Workstation+1;
end
end
Total_Dis=Total_Dis+Result(Customer_num,3);
else
Total_Dis=10000;%引入罰函數
end
三、運作結果
四、備注
版本：2014a