基于遺傳優(yōu)化算法的帶時間窗多車輛路線規(guī)劃matlab仿真
1.程序功能描述
基于遺傳優(yōu)化算法的帶時間窗多車輛路線規(guī)劃matlab仿真，通過輸入各個節(jié)點坐標，以及出發(fā)點到節(jié)點的時間窗，來進行優(yōu)化，輸出最優(yōu)的路線規(guī)劃結(jié)果。
2.測試軟件版本以及運行結(jié)果展示
MATLAB2022A版本運行
最后優(yōu)化結(jié)果如下：
路線1：0-5-3-7-8-10-11-9-6-4-2-1-0
路線2：0-13-17-18-19-15-16-14-12-0
路線3：0-20-24-25-27-29-30-28-26-23-22-21-0
路線4：0-32-33-31-35-37-38-39-36-34-0
3.核心程序
for ij=1: Miter
ij
%計算適應(yīng)度值
Jobj = func_fitness(X1,Nums,Time_start,Time_end,Time_win2,Time_service,dmat);
J_min = min(Jobj);
Jobj2 = 1./Jobj;
%選擇
Xsel = func_select(X1,Jobj2,pg);
%交叉
Xsel = func_crossover(Xsel,pc);
%編譯
Xsel = func_mut(Xsel,pm);
%局部搜
Xsel = func_neighbor1(Xsel, Nums, Time_start, Time_end, Time_win2, Time_service, dmat);
X1 = func_reins(X1,Xsel,Jobj);
X1 = func_dealrepeat(X1);
Jobj = func_fitness(X1,Nums,Time_start,Time_end,Time_win2,Time_service,dmat);
JJ(ij)= min(Jobj);
end
figure;
plot(1:5:Miter,JJ(1:5:end),'r->',...
'LineWidth',1,...
'MarkerSize',5,...
'MarkerEdgeColor','k',...
'MarkerFaceColor',[0.9,0.9,0.0]);
grid on
xlabel('GA優(yōu)化迭代次數(shù)');
ylabel('適應(yīng)度值');
Jobj = func_fitness(X1,Nums,Time_start,Time_end,Time_win2,Time_service,dmat);
[~,Idxs]= min(Jobj);
X_best = X1(Idxs(1),:);
[Vdraw,Nbest,dbest,~,~]=func_decode(X_best, Nums, Time_start, Time_end, Time_win2, Time_service, dmat);
disp(['車輛數(shù): ', num2str(Nbest), ', 總距離: ', num2str(dbest)]);
Numc = Pxy(2:end,:);
NV = size(Vdraw,1);
figure
hold on;box on
title('優(yōu)化路徑')
hold on;
colors =[0.3,0.5,0.6;
0.9,0.3,0.3;
0.4,0.8,0.4;
1.0,0.6,0.2;];
for i=1:NV
part_seq=Vdraw{i};
len=length(part_seq);
for j=0:len
if j==0
fprintf('%s','路線',num2str(i),':');
fprintf('%d->',0);
c1=Numc(part_seq(1),:);
plot([Pxy(1,1),c1(1)],[Pxy(1,2),c1(2)],'-','color',colors(i,:));
elseif j==len
fprintf('%d->',part_seq(j));
fprintf('%d',0);
fprintf('\n');
c_len=Numc(part_seq(len),:);
plot([c_len(1),Pxy(1,1)],[c_len(2),Pxy(1,2)],'-','color',colors(i,:));
else
fprintf('%d->',part_seq(j));
c_pre=Numc(part_seq(j),:);
c_lastone=Numc(part_seq(j+1),:);
plot([c_pre(1),c_lastone(1)],[c_pre(2),c_lastone(2)],'-','color',colors(i,:));
end
end
end
plot(Numc(:,1),Numc(:,2),'bs','linewidth',1);hold on;
plot(Pxy(1,1),Pxy(1,2),'r>',...
'LineWidth',1,...
'MarkerSize',12,...
'MarkerEdgeColor','k',...
'MarkerFaceColor',[0.9,0.9,0.0]);
4.本算法原理
帶時間窗的多車輛路線規(guī)劃問題旨在為給定數(shù)量的車輛安排行駛路線，以服務(wù)多個客戶點，同時要滿足一系列約束條件。假設(shè)有n個客戶點（編號為 ）需要被m輛車服務(wù)，每輛車都從配送中心（可視為編號為0的特殊節(jié)點）出發(fā)并最終返回配送中心。
遺傳算法（Genetic Algorithm，GA）是一種模擬自然生物進化過程的隨機搜索優(yōu)化算法，它基于達爾文的進化論和孟德爾的遺傳學說，通過選擇、交叉、變異等操作對種群中的個體（在本問題中可視為車輛路線的一種編碼表示）進行迭代更新，以逐步找到最優(yōu)解或近似最優(yōu)解。
在多車輛路線規(guī)劃中，時間窗約束是一個關(guān)鍵因素，需要在算法的各個環(huán)節(jié)進行考慮和處理。
初始化階段
在隨機生成初始個體時，要盡量保證生成的車輛路線安排滿足時間窗約束，例如可以按照時間窗的最早時間順序優(yōu)先安排客戶點到車輛路線上，這樣能在一定程度上減少初始個體中違反時間窗的情況。
適應(yīng)度計算階段
如前面所述，在計算適應(yīng)度函數(shù)時，要準確計算違反時間窗產(chǎn)生的延遲時間 ，將其納入適應(yīng)度評價體系，使得違反時間窗嚴重的個體適應(yīng)度值較低，從而在選擇操作中被淘汰的概率更大。
交叉和變異操作階段
在交叉和變異操作后，生成的新個體可能會出現(xiàn)違反時間窗約束的情況。對于新個體，需要重新檢查其各條車輛路線是否滿足時間窗要求，若不滿足，可以采用一些修復策略，例如調(diào)整車輛在路線上服務(wù)客戶點的順序、嘗試將客戶點移動到其他車輛的路線上，或者對違反時間窗的部分進行局部優(yōu)化等，以使個體重新滿足約束條件。
