带软时间窗的车辆路径问题：车辆数给定的配送优化

带软时间窗的车辆路径问题：车辆数给定的配送优化

本文探讨了车辆数给定的带软时间窗的车辆路径问题，使用遗传算法进行优化求解。代码实现了车辆路径优化模型，并包含了目标函数计算、遗传算法操作、结果输出和路线可视化等功能。

问题描述

给定多个配送点（包括起点和终点），每个配送点都带有软时间窗，以及车辆数、载重限制、速度等参数，需要找到最佳的配送路线，使得总配送时间最短，且满足所有配送点的软时间窗约束。

遗传算法实现

代码使用遗传算法来求解车辆路径问题，主要步骤如下：

1. 初始化种群: 随机生成一组初始解，每个解表示一个车辆的配送路线。
2. 适应度评价: 计算每个解的目标函数值，目标函数值越小，解的质量越高。
3. 选择: 根据适应度值，选择一些优秀的解进入下一代。
4. 交叉: 将选中的解进行交叉操作，产生新的解。
5. 变异: 对新解进行变异操作，增加解的多样性。
6. 重复步骤2-5: 直到满足停止条件。

代码实现

% 带软时间窗的车辆路径问题，配送的车辆数给定
% CFZ20160629
% 02:28
clear;
clc;
%%
%读取具体的订单信息，并计算距离矩阵
location=xlsread('testdata3.xlsx','Sheet1','B2:D592');%点集合
E=xlsread('testdata3.xlsx','Sheet2','B2:VT592');      %边集合
data=xlsread('testdata3.xlsx','Sheet3','A2:J13');    %订单信息
%%
%问题参数
num_center=408;              %配送重点编号
num_car=3;                  %车辆数
speed=50;                 	%车速
num_order=size(data,1); 	%订单数
max_load=6;                 %每辆车的载重上限
w_dist=1;                   %距离权重
w_overweight=1000000;       %超重的惩罚值
w_earlytime=2;            	%早到的惩罚值
w_latetime=1000000;      	%迟到的惩罚值
%%
%算法参数
maxgen=500;             	%迭代次数上限
stopgen=40;                 %最优解最少保持代数
sizepop=80;                    %个体数目
GGAP=0.9;                   %选择概率
pmutation=0.2;              %变异率
%%
%生成点到点的距离矩阵，无边直接相连赋值为0，点到自身赋值为0
D=zeros(size(location,1));
for i=1:size(location,1)
    for j=i:size(location,1)
        if E(i,j)==1
            D(i,j)=((location(i,2)-location(j,2))^2+(location(i,3)-location(j,3))^2)^0.5; %计算存在边相连的两点之间的距离
        else
            D(i,j)=NaN; %两点之间无边直接相连，距离记为NaN
        end
    end
end
D(isnan(D))=0;          %将矩阵中的NaN变为0
D=D+D';                 %将上三角矩阵变成对称矩阵
% %验证道路数据是否连通
% for i=1:size(location,1)
%     Dist0(i,:)=graphshortestpath(sparse(D),i);
% end
% [aa,bb]=find(Dist0==Inf);
% cccc=[aa bb];%记录不连通的两点
% if ~isempty(cccc)
%     error('存在不连通图')
% end
% 生成订单到订单的距离矩阵
Seq=[num_center;data(:,2)];
for i=1:length(Seq)
    for j=1:length(Seq)
        Dist(i,j)=graphshortestpath(sparse(D),Seq(i),Seq(j));
    end
end
%%
%生成初始解
for i=1:sizepop
    Chrom2(i,:)=randperm(num_order);
    zero_location=randperm(num_order-1);
    zero_location=zero_location(1:num_car-1);
    Chrom(i,:)=insertzeros(Chrom2(i,:),zero_location);
end
Chrom=[zeros(sizepop,1) Chrom zeros(sizepop,1)];%初始解
ObjV=Objectfunction(Chrom,data,Dist,speed,num_order,max_load,w_dist,w_overweight,w_earlytime,w_latetime);%计算初始解的目标函数值
[bestObjV,bestindex]=max(ObjV);
bestsol=Chrom(bestindex,:);
%%
%循环开始
gen=1;  %初始遗传代数
gen0=0; %初始保持代数   
while gen0<stopgen && gen<=maxgen
    disp(gen)
    FitnV=ranking(-ObjV);                                   %分配适应度值(Assign fitness values)
    SelCh=select('sus', Chrom, FitnV, GGAP);                %选择
    SelCh=cross(SelCh,num_car+1,floor(sizepop*GGAP/2)*2);      %重组
    SelCh=mut(SelCh,pmutation,floor(sizepop*GGAP/2)*2);        %变异
    ObjVSel=Objectfunction(SelCh,data,Dist,speed,num_order,max_load,w_dist,w_overweight,w_earlytime,w_latetime);           %计算子代目标函数值
    [Chrom,ObjV]=reins(Chrom, SelCh, 1, 1, ObjV, ObjVSel);	%重插入
    [newbestObjV,newbestindex]=max(ObjV);
    [worestObjV,worestindex]=min(ObjV);
    if newbestObjV>bestObjV
        bestObjV=newbestObjV;
        bestsol=Chrom(newbestindex,:);
        gen0=0;
    else
        gen0=gen0+1;                    %最优值保持次数加1
    end
    Chrom(worestindex,:)=Chrom(newbestindex,:);
    ObjV(worestindex,:)=newbestObjV;
    trace(gen,1)=1/bestObjV;            %记录每一代进化中最好的适应度
    trace(gen,2)=sum(1./ObjV)/sizepop;  %记录每一代进化中平均适应度
    gen=gen+1;                          %遗传代数加1
end
gen=gen-1;
%计算每个车辆的线路
bestzero_location=find(bestsol==0);     %寻找最优解中0的位置
for i=1:num_car
    Seq_order{1,i}=bestsol(bestzero_location(i):bestzero_location(i+1));%每个车辆配送的订单编号顺序
	circle{1,i}=Seq(Seq_order{1,i}+1)'; %订单位置顺序
    route{1,i}=circle{1,i}(1);          %每个车辆配送的订单位置顺序
    for j=1:length(circle{1,i})-1
        [~,temp_route]=graphshortestpath(sparse(D),circle{1,i}(j),circle{1,i}(j+1));
        route{1,i}=[route{1,i} temp_route(2:end)];%每个车辆的行驶线路
    end
end
%%
%结果输出
disp('---------------------------------------------------------------------')
disp('最优订单顺序：')
disp(bestsol)
for i=1:num_car
    disp(['车辆',num2str(i),'配送的订单顺序：'])
    disp(Seq_order{1,i})
    disp(['车辆',num2str(i),'的配送路线：'])
    disp(route{1,i})
end
disp('最优值：')
disp(1/bestObjV)
%%
%绘图
%图1：优化过程图
figure
plot(1:gen,1./trace(:,1));
plot(1:gen,trace(:,1),'r-',1:gen,trace(:,2),'b--');
title(['目标函数优化曲线  ' '终止代数＝' num2str(gen)],'fontsize',12);
xlabel('进化代数','fontsize',12);
ylabel('目标函数值','fontsize',12);
legend('各代最佳值','各代平均值');
xlim([1,gen])
%图2：全部车辆的配送路线图
figure
hold on
plot(location(:, 2), location(:, 3), 'r.', 'MarkerSize', 10);
shift2=0.0003;
for i=1:size(location,1)
    text(location(i,2)+shift2,location(i,3)+shift2,num2str(i),'fontsize',8);
end
plot(location(num_center,2),location(num_center,3),'rp','MarkerSize',20);
for i=1:size(E,1)
    for j=i:size(E,1)
        if E(i,j)==1
            plot([location(i,2) location(j,2)], [location(i,3) location(j,3)], 'k:.', 'LineWidth', 1)
        end
    end
end
colour=linspecer(num_car);
shift=0.0004;%坐标位移量
for i=1:num_car
    LL=[];
    LL=location(route{1,i},2:3);
    for j=2:length(route{1,i})
        quiver(LL(j-1,1),LL(j-1,2)+(i-1)*shift,(LL(j,1)-LL(j-1,1))/0.9,(LL(j,2)-LL(j-1,2))/0.9,'color',colour(i,:),'linewidth',1.5);
%         [arrowx,arrowy] = dsxy2figxy(gca,LL(j-1:j,1)+(i-1)*shift,LL(j-1:j,2)+(i-1)*shift);%坐标转换
%         annotation('textarrow',arrowx,arrowy,'HeadWidth',9,'color',colour(i,:),'linewidth',1.5);
    end
end
xlabel('横坐标')
ylabel('纵坐标')
title('全部车辆的配送路线图')
box on
hold off;

说明

1. 代码中使用了 xlsread 函数读取 Excel 文件数据，请确保您的工作目录中存在名为 testdata3.xlsx 的 Excel 文件，并且文件包含了配送点的坐标信息、道路连接信息和订单信息。
2. 代码中使用了 graphshortestpath 函数计算两点之间的最短路径，请确保您的 MATLAB 环境中安装了 graph 工具箱。
3. 代码中使用的 ranking 函数用于分配适应度值，该函数需要根据实际情况进行编写，例如，可以根据目标函数值进行排名，或者使用其他适应度函数。
4. 代码中使用了 select、cross、mut 和 reins 等函数来实现遗传算法的各个操作，这些函数可以从 MATLAB 的遗传算法工具箱中获得，或者自行编写。
5. 代码最后部分使用了 plot 和 quiver 函数绘制了车辆的配送路线图，方便观察优化结果。

注意

1. 代码中部分函数的实现需要根据实际情况进行调整。
2. 代码中使用了 testdata3.xlsx 文件，请根据实际情况修改文件名和文件路径。
3. 代码中部分参数的取值需要根据实际问题进行调整。

总结

本文提供了一个使用遗传算法求解带软时间窗的车辆路径问题的代码示例，代码包含了目标函数计算、遗传算法操作、结果输出和路线可视化等功能，方便您理解和学习遗传算法的应用。

相关链接

1. MATLAB 遗传算法工具箱
2. 车辆路径问题
3. 软时间窗