当前位置：首页 > news >正文

MATLAB优化VRPTW规划问题：基于蚁群算法的解决方案

news 2026/8/27 19:32:43

MATLAB采用蚁群算法解决VRPTW规划问题

VRPTW（带时间窗的车辆路径问题）这玩意儿在实际物流场景里能把人逼疯——既要控制成本又得满足客户时间要求。今天咱们用MATLAB整点有意思的，试试用蚁群算法来干这个活。

先来点直观的算法设定：假设我们有10个客户点，3辆货车。每只蚂蚁要构建满足容量和时间窗约束的路径。关键参数直接扔代码里：

num_ants = 30; % 蚂蚁数量 max_iter = 100; % 迭代次数 alpha = 1; % 信息素重要程度 beta = 2; % 启发因子重要程度 rho = 0.1; % 信息素挥发系数 Q = 100; % 信息素强度

重点看路径生成部分。每只蚂蚁从仓库出发，用轮盘赌选择下一个节点。这里有个骚操作——把时间窗违反量转化为惩罚成本：

function path = generate_path(ant) current_node = depot; remaining_capacity = vehicle_capacity; path = {[]}; while ~all_visited() feasible_nodes = find(... % 筛选未访问、容量足够、时间窗允许的节点 (demands <= remaining_capacity) & ... (current_time + travel_time <= time_windows(:,2))); if isempty(feasible_nodes) % 返回仓库并换新车 path{end}(end+1) = depot; path{end+1} = []; remaining_capacity = vehicle_capacity; continue end % 带时间窗修正的概率计算 probabilities = compute_probs(feasible_nodes); next_node = roulette_wheel(probabilities); path{end}(end+1) = next_node; remaining_capacity = remaining_capacity - demands(next_node); current_time = max(current_time + travel_time, time_windows(next_node,1)); end end

时间窗处理这里有个坑：直接用硬约束会频繁出现无解情况。咱们在适应度函数里加了个柔性处理，允许轻微超时但会被惩罚：

function fitness = calc_fitness(path) total_distance = 0; time_violation = 0; for route in path if isempty(route), continue; end % 计算路径长度 total_distance += sum(travel_matrix(route)); % 计算时间窗违反量 current_time = 0; for i = 2:length(route) arrival = current_time + travel_time; if arrival > time_windows(route(i),2) time_violation += arrival - time_windows(route(i),2); end current_time = max(arrival, time_windows(route(i),1)); end end fitness = total_distance + 50 * time_violation; % 惩罚系数需要调参 end

信息素更新这块儿容易翻车。我们的策略是：全局更新最优路径，局部更新所有蚂蚁经过的路径。注意挥发系数别设太大，不然收敛太快：

% 信息素矩阵初始化 tau = ones(n, n) * 0.1; % 每轮迭代后更新 delta_tau = zeros(n, n); for ant = 1:num_ants for i = 1:length(path)-1 from = path(i); to = path(i+1); delta_tau(from, to) += Q / calc_fitness(ant_path); end end tau = (1 - rho) * tau + delta_tau; % 挥发+新增

跑完算法后画个路线图最直观。用MATLAB的gplot函数配合邻接矩阵，不同颜色区分车辆路线：

colors = hsv(num_vehicles); hold on; for k = 1:length(routes) plot(coords(routes{k},1), coords(routes{k},2), 'Color', colors(k,:), 'LineWidth', 2); end scatter(coords(:,1), coords(:,2), 'filled');

实际跑起来有几个经验参数：