1 简介
车 辆 路 径 问 题 ( Vehicle Ｒouting Problem，VＲP) 是一类经典的组合优化问题。一般指对一系列的客户点组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件 ( 如货物需求量、车辆容量限制等) 下，达到一定的目标 ( 如距离最短、费 用 最 少 等) ，带 时 间 窗 车 辆 路 径 问 题( Vehicle Ｒouting Problem with Time Windows，VＲPTW) 是在 VＲP 的基础上要求在配送过程中按照客户要求在一定的时间窗内到达客户点，即在不违背车辆容量限制、时间限制等约束条件的前提下，合理制定运输时的车辆配送路径方案，以尽可能小的成本满足处在不同地理位置的客户对货物运送和服务时间的要求。由于 VＲPTW 带有服务时间的访问限制，VＲPTW 比 VＲP 更贴近实际应用，广泛地应用于交通和物流领域，由于 VＲPTW 是NP 难问题，主要都是使用启发式算法来求解，已有不少学者对该问题进行了相关的研究。
2 部分代码
clc %清空命令行窗口
clear %从当前工作区中删除所有变量，并将它们从系统内存中释放
close all %删除其句柄未隐藏的所有图窗
tic % 保存当前时间
%% 蚁群算法求解VRPTW
%输入：
%City 需求点经纬度
%Distance 距离矩阵
%TravelTime 行驶时间矩阵
%Demand 各需求点需求量
%Travelcon 行程约束
%Capacity 车容量约束
%TimeWindow 各需求点时间窗
%AntNum 种群个数
%Alpha 信息素重要程度因子
%Beta 启发函数重要程度因子
%Rho 信息素挥发因子
%Q 常系数
%Eta 启发函数
%Tau 信息素矩阵
%MaxIter 最大迭代次数
%输出：
%bestroute 最短路径
%mindisever 路径长度
%% 加载数据
load('./test_data/City.mat') %需求点经纬度，用于画实际路径的XY坐标
load('./test_data/Distance.mat') %距离矩阵
load('./test_data/TravelTime.mat') %行驶时间矩阵
load('./test_data/Demand.mat') %需求量
load('./test_data/TimeWindow.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(MaxIter,CityNum*2+1); % 各代最佳路径
MinDis = zeros(MaxIter,1); % 各代最佳路径的长度
取得最优个体
%删去路径中多余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(bestroute,Distance,TravelTime,Demand,TimeWindow,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')
img =gcf; %获取当前画图的句柄
print(img, '-dpng', '-r600', './img.png') %即可得到对应格式和期望dpi的图像%% 绘制实际路线
DrawPath(bestroute,City)
img =gcf; %获取当前画图的句柄
print(img, '-dpng', '-r600', './img1.png') %即可得到对应格式和期望dpi的图像
3 仿真结果
4 参考文献
[1]刘小兰. 有时间窗的车辆路径问题(VRPTW)的近似算法研究. Diss. 华南理工大学, 2003.