一、算法介绍

 

二、模型

VRPTW的数学模型如下：

 

（2.2）保证了每个顾客只被访问1次

（2.3）保证了装载的货物不超过容量

（2.4）（2.5）（2.6）确保了每辆车从depot出发最后回到depot

（2.7）（2.8）确保在时间窗内开始服务

三、代码

clc %清空命令行窗口
clear %从当前工作区中删除所有变量，并将它们从系统内存中释放
close all %删除其句柄未隐藏的所有图窗
tic % 保存当前时间
%% 蚁群算法求解CDVRP
%输入：
%City           需求点经纬度
%Distance       距离矩阵
%Demand         各需求点需求量
%AntNum         种群个数
%Alpha          信息素重要程度因子
%Beta           启发函数重要程度因子
%Rho            信息素挥发因子
%Q              常系数
%Eta            启发函数
%Tau            信息素矩阵
%MaxIter        最大迭代次数


%输出：
%bestroute      最短路径
%mindisever     路径长度

%% 加载数据
load('../test_data/City.mat')	      %需求点经纬度，用于画实际路径的XY坐标
load('../test_data/Distance.mat')	  %距离矩阵
load('../test_data/Demand.mat')       %需求量
load('../test_data/Travelcon.mat')	  %行程约束
load('../test_data/Capacity.mat')     %车容量约束

%% 初始化问题参数
CityNum = size(City,1)-1;    %需求点个数

%% 初始化参数
AntNum = 8;                            % 蚂蚁数量
Alpha = 1;                              % 信息素重要程度因子
Beta = 5;                               % 启发函数重要程度因子
Rho = 0.1;                              % 信息素挥发因子
Q = 1;                                  % 常系数
Eta = 1./Distance;                      % 启发函数
Tau = ones(CityNum+1);                  % (CityNum+1)*(CityNum+1)信息素矩阵  初始化全为1
Population = zeros(AntNum,CityNum*2+1);  % AntNum行,(CityNum*2+1)列 的路径记录表
MaxIter = 100;                           % 最大迭代次数
bestind = ones(1,CityNum*2+1);	% 各代最佳路径
MinDis = zeros(MaxIter,1);              % 各代最佳路径的长度

%% 迭代寻找最佳路径
Iter = 1;                               % 迭代次数初值

end

%% 找出历史最短距离和对应路径
mindisever = MinDis(MaxIter); % 取得历史最优适应值的位置、最优目标函数值
bestroute = bestind; % 取得最优个体

%删去路径中多余1
for i=1:length(bestroute)-1
    if bestroute(i)==bestroute(i+1) %相邻位都为1时
        bestroute(i)=0;  %前一个置零
    end
end
bestroute(bestroute==0)=[];  %删去多余零元素

bestroute=bestroute-1;  % 编码各减1，与文中的编码一致

%% 计算结果数据输出到命令行
disp('-------------------------------------------------------------')
toc %显示运行时间
fprintf('Total Distance = %s km \n',num2str(mindisever))
TextOutput(Distance,Demand,bestroute,Capacity)  %显示最优路径
disp('-------------------------------------------------------------')

%% 迭代图
figure
plot(MinDis,'LineWidth',2) %展示目标函数值历史变化
xlim([1 Iter-1]) %设置 x 坐标轴范围
set(gca, 'LineWidth',1)
xlabel('Iterations')
ylabel('Min Distance(km)')
title('ACO Process')

%% 绘制实际路线
DrawPath(bestroute,City)

四、演示结果