一、論文方法簡介
參考文獻：Optimisation of takeaway delivery routes considering the mutual satisfactions of merchants and customers
1、模型簡介
（1）VRPPDTW模型，就是帶時間窗的外賣配送模型，約束條件見論文， 
（2）客戶滿意度模型
（3）目標函式：
2、演算法簡介
（1）采用啟發式插入演算法構造初始種群，加快遺傳演算法的收斂速度，
（2）采用前向連續交叉的交叉策略，
（3）采用差異突變的突變策略
（文中的差分突變方法似乎對自然數編碼帶來的都是不可行解？）
（4）演算法流程
二、實驗仿真
1、模型假設
以文中所給1的B1測驗樣例采用改進的遺傳演算法(IGA)進行復現，進一步簡化模型，考慮30個訂單由6個騎手送，主要約束條件為先取貨在送貨，否則設定其適應度為0（由于取0后求倒數會發生錯誤，可以設為0.0000001），
2、部分程序
（1）對B1實體中商家節點和客戶節點重新編號
（2）啟發式插入構造初始種群，可以發現初始種群都是可行解
3、實驗結果
（1）迭代300次后的種群平均總成本（由于文中未給出三個成本函式的權重，故與論文中的總成本存在一定的數值差距）
（2）論文中結果（可以發現與論文結果的演算法收斂趨勢差不多）：
（3）迭代300次后的最優個體的總成本
（4）迭代300次時的騎手1配送路線，藍色圓圈為配送中心
（4）迭代300次時的騎手2配送路線
（5）迭代300次時的騎手3配送路線
（6）迭代300次時的騎手4配送路線
（7）迭代300次時的騎手5配送路線
（8）迭代300次時的騎手6配送路線
三、實驗代碼及說明
資料檔案及完整專案下載地址：
gitub:https://github.com/LiuKang-coder/Improved-take-out-delivery-method-based-on-genetic-algorithm/tree/main
（求收藏！！！）
CSDN:https://download.csdn.net/download/qq_45063357/72873237
主函式：IGA.m
%%%主程式：用IGA求解30個訂單，10個騎手的配送問題，假設只用了6個騎手配送，每個騎手都滿載
%1：設定引數
Psize=60;%初始種群大小
% Fmax=0.0001;%最大適應度值
% Mbest=zeros(1,20);%最優個體的容量
Pc=0.8;%交叉概率
Pm=0;%突變概率
Gen=300;%迭代次數
X=zeros(Gen,Psize);%存盤每代的最優個體
%2；產生初始種群
P0=F1(MN,Psize);%利用商戶節點和顧客節點以及初始種群大小，采用插入式啟發演算法產生初始種群
%3：計算種群適應度累計概率
[Fit PP]=F2(TW,P0,XY,C0);
% GK=1;%迭代次數
%4 選擇
for GK=1:Gen %%最大迭代次數
for j=1:2:Psize %%隔一個選擇30次，為了保證不選擇兩個相同的基因型進行交
%輪盤賭法選擇
Slc=Select(P0,PP);%選擇的兩個個體
%前向連續交叉
scr=Cross(P0,Slc,Pc);
Scnew(j,:)=scr(1,:); %交叉后產生的子代
Scnew(j+1,:)=scr(2,:);%交叉后產生的子代
%染色體突變方法
smnew(j,:)=mutation(Scnew(j,:),Pm,P0); %子程式4，對新產生的子群進行變異操作
smnew(j+1,:)=mutation(Scnew(j+1,:),Pm,P0); %子程式4，對新產生的子群進行變異操作
end
P0=smnew; %產生了新的種群
%計算新種群的適應度
[Fit PP]=F2(TW,P0,XY,C0); %計算新種群的適應度和累計概率
%記錄當前代最好的適應度和平均適應度
[fmax,nmax]=max(Fit); %計算當代最大的適應度和代數
fmean=mean(Fit); %當前代的平均適應度
ymax(GK)=1/fmax; %最大的適應度
ymean(GK)=1/fmean;%平均的適應度
%記錄當前代的最佳染色體個體
X(GK,:)=P0(nmax,:); %當前代的最佳染色體個體
end
%最大適應度
figure;
hand1=plot(1:GK,ymax);
set(hand1,'color','b','linestyle','-','linewidth',1.8);
xlabel('迭代次數');ylabel('總成本');xlim([1 Gen]);
% legend('最優個體的總成本');
title('Pc=0.8,Pm=0.2時最優個體的總成本')
grid on
%平均適應度
figure;
hand2=plot(1:GK,ymean);
set(hand2,'color','r','linestyle','-','linewidth',1.8)
xlabel('迭代次數');ylabel('總成本');xlim([1 Gen]);
% legend('種群的平均總成本');
title('Pc=0.8,Pm=0.2時平均總成本')
grid on
%%%畫出迭代300次路線圖
node=X(300,:)';
route=XY(node,:);%節點對應的坐標
for iii=1:6
route1=route(10*(iii-1)+1:10*iii,:);
route1=[C0;route1;C0];
%畫連線圖
figure
plot(C0(1),C0(2),'ob', 'MarkerSize',20,'linewidth',3)
hold on
plot(route1(:,1),route1(:,2),'.-r', 'MarkerSize',14)
title(['迭代300次時的騎手',num2str(iii),'的配送路線圖'])
end
F1.m
%F1:插入式啟發演算法產生初始種群
function P=F1(MN,Psize)%P=F1(MN,60)
%%隨機插入商家節點
% Psize=60;
m=size(MN,1);
for i=1:Psize;
%對MN隨機排列，產生i個隨機種子
PM(i,:)=randperm(m);%產生隨機1-30序號排列
R1(1:5)=PM(i,1:5);
R2(1:5)=PM(i,6:10);
R3(1:5)=PM(i,11:15);
R4(1:5)=PM(i,16:20);
R5(1:5)=PM(i,21:25);
R6(1:5)=PM(i,26:30);
%%啟發式插入顧客節點
%隨機生成顧客節點排列
PC1=R1+30;
PC2=R2+30;
PC3=R3+30;
PC4=R4+30;
PC5=R5+30;
PC6=R6+30;
%對PC隨機排列，產生i個隨機種子
ID1(1:5)=randperm(5);%產生顧客隨機序號
ID2(1:5)=randperm(5);%產生顧客隨機序號
ID3(1:5)=randperm(5);%產生顧客隨機序號
ID4(1:5)=randperm(5);%產生顧客隨機序號
ID5(1:5)=randperm(5);%產生顧客隨機序號
ID6(1:5)=randperm(5);%產生顧客隨機序號
NPC1(1:5)=PC1(ID1(1:5));
NPC2(1:5)=PC2(ID2(1:5));
NPC3(1:5)=PC3(ID3(1:5));
NPC4(1:5)=PC4(ID4(1:5));
NPC5(1:5)=PC5(ID5(1:5));
NPC6(1:5)=PC6(ID6(1:5));
NR1(i,1:10)=[R1 NPC1];
NR2(i,1:10)=[R2 NPC2];
NR3(i,1:10)=[R3 NPC3];
NR4(i,1:10)=[R4 NPC4];
NR5(i,1:10)=[R5 NPC5];
NR6(i,1:10)=[R6 NPC6];
end
NP=[NR1 NR2 NR3 NR4 NR5 NR6];
P=NP;
End
F2.m
%%計算適應度和累計概率
function [Fit PP]=F2(TW,P0,XY,C0)
%計算每個訂單的距離長度
[m,n]=size(P0);
%%%求每條染色體的適應度
for i=1:m
p1=P0(i,:);%每條染色體
D=zeros(1,m);%總距離
T=zeros(1,m);%總時間成本
for j=1:10:51 %第j個騎手
d(1)=Dist(C0,XY(p1(j),:));%起點到第一個節點
d(11)=Dist(XY(p1(j+9),:),C0);%最后一個節點到終點
for jn=2:10 %第j個騎手對應的節點
%%計算距離
d(jn)=Dist(XY(p1(j+jn-2),:),XY(p1(j+jn-1),:))/1000;
end
dd=sum(d);%每個騎手對應的總距離
D(i)=0.1*(D(i)+dd);%訂單總距離:km，C2未告訴，取0.2
%%求解時間窗損耗
tt=Ftime(TW,p1,d,j);%每個騎手對應的懲罰時間，10個節點
T(i)=T(i)+tt;%訂單總懲罰時間
end
%%計算每條染色體的總成本，分別為啟動成本、騎行成本、懲罰時間成本
f(i)=0.24*100+0.12*D(i)+0.64*T(i);%總成本
Fit(i)=1/f(i);%適應度取倒數
end
%%將不滿足約束條件的染色體個體的適應度設為0，由于0取倒數會存在問題，這里設為0.000001
for i=1:m %整個種群
p1=P0(i,:);%每條染色體
for id=1:30
IDm=find(p1==id);%商家節點序號
IDc=find(p1==(id+30));%顧客節點序號
if IDc<IDm %顧客節點在商家節點前面，令適應度為0.00000001
Fit(i)=0.00000001;
break;
end
end
end
%%%求累計概率PP
%求總適應度
PS=sum(Fit);
PP(1)=Fit(1)/PS;
for ii=2:m
PP(ii)=PP(ii-1)+Fit(ii)/PS;%累計概率
end
PP=PP';
end
Ftime.m
function tt=Ftime(TW,p1,d,j)
% T=0;%總懲罰時間
%%%每個客戶節點的服務時間為2分鐘
%騎行速度為10 km/60min
%騎行到每個節點的時間為距離除以速度,騎行到第一個節點是沒有服務時間的
tt(1)=d(1)*6;%1km騎6分鐘
%從第2個節點到其它11個節點的騎行時間
for jj=1:10 %jj對應第jj個客戶節點
t(jj)=2+d(jj)*6;%騎行時間
ta(jj)=sum(t);%到達每個節點的時間
tcost(jj)=0.1*(max(ta(jj)-TW(p1(jj-1+j),1),0)+max(TW(p1(jj-1+j),2)-ta(jj),0));%%C3為告訴，取0.1
end
tt=sum(tcost);%總懲罰時間
end
Select.m
%子程式2：新種群選擇操作, 函式名稱存盤為Select.m
function Slc=Select(P0,PP);%%輸入種群，累計概率
%從種群中選擇兩個個體
for i=1:2 %一下選擇兩個個體
r=rand; %產生一個（0,1）亂數
prand=PP-r;%所有元素減r
j=1;
while prand(j)<0 %
j=j+1; %j所在的累計概率是第一個大于r的，即多次生成r,就能選擇累計概率最接近r的個體，即是輪盤賭法選擇
end
Slc(i)=j; %第一次和第二次選中的個體代號，為了方便交叉
end
mutation.m
%子程式4：新種群變異操作，函式名稱存盤為mutation.m
function snnew=mutation(Scnew,Pm,P0);%一下輸入一個子群和變異概率
[m,n]=size(P0);;%子群位長
snnew=Scnew;%%變異后的子群
pmm=IfCroIfMut(Pm); %根據變異概率決定是否進行變異操作，1則是，0則否，類似交叉 %子程式7
if pmm==1
chb1=round(rand*(m-1))+1; %在[1,60]范圍內隨機產生一個變異位
chb2=round(rand*(m-1))+1; %在[1,60]范圍內隨機產生一個變異位
%交換兩個變異位
mm=snnew(chb1:chb1+1);
snnew(chb1)=snnew(chb2:chb2+1);%交換
snnew(chb2)=mm;
end
end
Cross.m
%子程式3：前向連續交叉,函式名稱存盤為Cross.m
function Scr=Cross(P0,Slc,Pc);%初始種群，選擇的個體，交叉概率
[m,n]=size(P0);
pcc=IfCroIfMut(Pc); %根據交叉概率決定是否進行交叉操作，1則是，0則否
if pcc==1 %進行交叉
chb=round(rand*(m-2))+1; %在[1,59]范圍內隨機產生一個交叉位，rand為【0，1】之間的亂數，chb后面才交叉，故到m-1
Scro(1,:)=[P0(Slc(1),:) P0(Slc(2),chb+1:m)];%%在chb,前一部分保留，后一部分交叉
Scro(2,:)=[P0(Slc(2),:) P0(Slc(1),chb+1:m)];%%在chb,前一部分保留，后一部分交叉
%%%洗掉重復節點
S1=fliplr(Scro(1,:));%倒序
S2=fliplr(Scro(2,:));%倒序
S1=unique(S1,'stable');%洗掉重復節點
S2=unique(S2,'stable');%洗掉重復節點
Scr(1,:)=fliplr(S1);
Scr(2,:)=fliplr(S2);
else
Scr(1,:)=P0(Slc(1),:); %不進行交叉
Scr(2,:)=P0(Slc(2),:); %進行交叉
end
Dist.m
%求歐幾里得距離函式dist
function y=Dist(x1,x2) %輸入坐標
y=sqrt((x2(1)-x1(1))^2+(x2(2)-x1(2))^2);
end
IfCroIfMut.m
%子程式7：判斷遺傳運算是否需要進行交叉或變異, 函式名稱存盤為IfCroIfMut.m
function pcc=IfCroIfMut(mutORcro); %輸入交叉概率
test(1:100)=0;
L=round(100*mutORcro);%l=L，概率取整
test(1:L)=1;
n=round(rand*99)+1;%%隨機生成1到100之間的數
pcc=test(n); %以90%的概率判斷是否進行交叉
不是完全復現哈哈哈，簡化了模型，把軟約束條件去掉了，但基本方法和思路是一樣的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/400410.html
標籤：其他
上一篇：深度強化學習-策略梯度演算法推導