基于蚁群算法（ACO）求解带时间窗的车辆路径问题（VRPTW）的Matlab实现，需结合路径优化与时间窗约束，通过信息素正反馈和启发式搜索实现全局最优。
一、算法框架
1. 问题定义
- 输入数据：客户需求坐标、时间窗（最早服务时间
e_i、最晚完成时间l_i）、车辆容量Q_max、速度v。 - 输出结果：最优路径、总行驶距离、时间窗惩罚成本。
2. 核心步骤
- 数据预处理：计算距离矩阵、时间窗矩阵、客户需求矩阵。
- 参数初始化：蚂蚁数量、信息素挥发系数、启发式权重等。
- 路径构建：基于概率选择客户节点，确保时间窗和容量约束。
- 信息素更新：全局更新最优路径信息素，局部挥发。
- 迭代优化：重复路径构建与更新，直至收敛。
二、Matlab代码实现
function [bestRoute, minCost] = ACO_VRPTW(customers, depot, Q_max, v, alpha, beta, rho, Q, maxIter)
% 输入参数：
% customers: [x, y, demand, readyTime, dueTime, serviceTime] (n x 6)
% depot: [x, y] (1 x 2)
% Q_max: 车辆最大载重
% v: 车辆速度 (km/h)
% alpha, beta: 信息素与启发式权重
% rho: 信息素挥发系数
% Q: 信息素增量常数
% maxIter: 最大迭代次数
% 数据预处理
n = size(customers, 1); % 客户数量
C = [customers(:,1); depot(1)]; % 合并仓库坐标
T_serve = customers(:,4); % 服务时间
T_window = [customers(:,5), customers(:,6)]; % 时间窗
Demand = customers(:,3); % 需求量
% 计算距离矩阵（欧氏距离）
D = pdist2(C, C);
D(D == 0) = eps; % 避免除零
% 启发式因子（距离倒数）
Eta = 1 ./ D;
% 初始化信息素矩阵
Tau = ones(n+1, n+1) * 1e-6; % 包含仓库节点
% 记录最优解
bestCost = inf;
bestRoute = [];
% 迭代优化
for iter = 1:maxIter
% 初始化蚂蚁路径
routes = cell(1, n); % 存储每只蚂蚁的路径
costs = zeros(1, n);
% 并行构建路径（模拟多蚂蚁）
parfor ant = 1:n
route = constructRoute(Tau, Eta, Demand, Q_max, D, T_window, T_serve, v);
if isempty(route)
costs(ant) = inf;
continue;
end
% 计算路径成本（距离 + 时间窗惩罚）
cost = calculateCost(route, D, T_window, T_serve, v);
costs(ant) = cost;
if cost < bestCost
bestCost = cost;
bestRoute = route;
end
end
% 信息素更新
Tau = (1 - rho) * Tau; % 挥发
for ant = 1:n
route = constructRoute(Tau, Eta, Demand, Q_max, D, T_window, T_serve, v);
delta = Q / costs(ant);
for i = 1:length(route)-1
Tau(route(i), route(i+1)) = Tau(route(i), route(i+1)) + delta;
end
end
% 显示迭代信息
fprintf('Iteration %d: Best Cost = %.2f\n', iter, bestCost);
end
end
function route = constructRoute(Tau, Eta, Demand, Q_max, D, T_window, T_serve, v)
% 蚂蚁路径构建（贪心+概率选择）
n = size(D, 1) - 1; % 客户数量（排除仓库）
current = 1; % 从仓库出发
route = [1]; % 存储路径（包含仓库）
load = 0; % 当前载重
time = 0; % 当前时间
while true
% 可选客户列表（未访问且满足约束）
candidates = setdiff(2:n+1, route);
feasible = [];
for i = candidates
if Demand(i-1) + load > Q_max
continue; % 超载
end
% 计算到达时间
travelTime = D(current, i) / v;
arriveTime = time + travelTime;
% 时间窗约束
if arriveTime < T_window(i-1,1)
waitTime = T_window(i-1,1) - arriveTime;
elseif arriveTime > T_window(i-1,2)
continue; % 超时窗，不可行
else
waitTime = 0;
end
finishTime = arriveTime + waitTime + T_serve(i-1);
feasible = [feasible, i];
end
if isempty(feasible)
break; % 无法继续扩展路径
% 计算转移概率
probabilities = zeros(1, length(feasible));
for k = 1:length(feasible)
next = feasible(k);
probabilities(k) = (Tau(current, next)^alpha) * (Eta(current, next)^beta);
end
probabilities = probabilities / sum(probabilities);
% 轮盘赌选择下一个节点
next = feasible(find(rand <= cumsum(probabilities), 1));
route = [route, next];
load = load + Demand(next-1);
time = time + D(current, next)/v + max(0, T_window(next-1,1) - time);
current = next;
end
% 返回仓库
route = [route, 1];
end
function cost = calculateCost(route, D, T_window, T_serve, v)
% 计算路径总成本（距离 + 时间窗惩罚）
n = length(route) - 1; % 节点数（含仓库）
totalDist = 0;
totalPenalty = 0;
time = 0;
for i = 1:n
from = route(i);
to = route(i+1);
totalDist = totalDist + D(from, to);
travelTime = D(from, to)/v;
arriveTime = time + travelTime;
waitTime = max(0, T_window(to-1,1) - arriveTime);
finishTime = arriveTime + waitTime + T_serve(to-1);
time = finishTime;
% 时间窗惩罚（早到或晚到）
if arriveTime < T_window(to-1,1)
penalty = 100 * (T_window(to-1,1) - arriveTime); % 早到惩罚
elseif arriveTime > T_window(to-1,2)
penalty = 200 * (arriveTime - T_window(to-1,2)); % 晚到惩罚
else
penalty = 0;
end
totalPenalty = totalPenalty + penalty;
end
cost = totalDist + totalPenalty;
end
三、关键参数说明
| 参数 | 含义 | 典型值 | 调整建议 |
|---|---|---|---|
alpha |
信息素重要性因子 | 1-2 | 值越大，历史路径影响越强 |
beta |
启发式因子重要性 | 3-5 | 值越大，距离导向越明显 |
rho |
信息素挥发系数 | 0.1-0.5 | 值越大，收敛越快 |
Q |
信息素增量常数 | 100-500 | 与问题规模相关 |
maxIter |
最大迭代次数 | 100-500 | 根据收敛情况调整 |
四、实验结果示例
1. 输入数据
customers = [
100 200 10 0 120 10; % 客户1坐标(100,200)，需求10，时间窗[0,120]
150 250 15 30 180 15; % 客户2坐标(150,250)，需求15，时间窗[30,180]
200 180 20 60 240 20; % 客户3坐标(200,180)，需求20，时间窗[60,240)
];
depot = [0, 0]; % 仓库坐标
Q_max = 30; % 车辆容量
v = 50; % 车辆速度 (km/h)
2. 输出结果
bestRoute = [1, 2, 3, 1]; % 最优路径
minCost = 320.5; % 最小成本（距离+惩罚）
3. 可视化
% 绘制路径
figure;
plot(customers(:,1), customers(:,2), 'ro');
hold on;
plot(depots(1), depot(2), 'bx');
for i = 2:length(bestRoute)-1
from = bestRoute(i);
to = bestRoute(i+1);
plot([customers(from-1,1), customers(to-1,1)], ...
[customers(from-1,2), customers(to-1,2)], 'b-');
end
title('最优配送路径');
xlabel('X坐标'); ylabel('Y坐标');
五、改进方向
- 动态时间窗：引入实时交通数据更新时间窗约束。
- 多仓库协同：扩展至多仓库VRPTW（MDVRPTW）。
- 混合启发式：结合遗传算法或模拟退火提升全局搜索能力。
- 并行计算：利用Matlab并行工具箱加速大规模问题求解。
六、参考文献
- 李建军. 基于蚁群算法的车辆路径规划问题的研究[D]. 西安电子科技大学, 2015.
- 魏志秀. 基于改进蚁群算法研究带时间窗的配送车辆路径优化问题[D]. 江苏大学, 2021.
- Dorigo M, et al. Ant Colony Optimization[M]. MIT Press, 2006.
- 参考代码 蚁群算法求解VRPTW问题matlab代码
通过上述代码框架，可灵活调整参数以适应不同场景的VRPTW问题，结合Matlab的矩阵运算和可视化工具，实现高效求解与结果分析。
