带时间窗的车辆路径规划(VRPTW)问题 遗传算法求解程序代码，蚁群算法，粒子群算法，节约里程算法，禁忌搜索算法 考虑车辆的最大容量限制 考虑违反时间约束和容量约束的惩罚系数 以距离最优为优化目标 代码注释清楚，可改性强，可替换自己的数据 代码使用matlab编写。 可以直接运行的
早上打开物流公司的调度系统，十辆货车堵在城北高架下不来——这场景让我决定动手写个VRPTW的智能算法库。今天先分享最核心的遗传算法实现，代码里埋了几个工程实战中的小技巧，咱们边看边聊。
先看主函数骨架：
function [bestRoute, minDist] = GA_VRPTW(data, popSize, maxGen) % 输入参数说明 % data: 客户数据矩阵 [x坐标, y坐标, 需求量, 时间窗起点, 时间窗终点] % popSize: 种群规模 % maxGen: 最大迭代次数 % 初始化参数 vehicleCap = 200; % 货车载重 punishTime = 100; % 时间窗惩罚系数 punishCap = 500; % 超载惩罚系数 % 初始化种群 population = initPopulation(data, popSize, vehicleCap); for gen = 1:maxGen % 计算适应度 fitness = calcFitness(population, data, vehicleCap, punishTime, punishCap); % 选择 newPop = selection(population, fitness); % 交叉 (两点交叉) newPop = crossover(newPop); % 变异 newPop = mutation(newPop, vehicleCap); population = newPop; end % 提取最优解 [~, idx] = min(fitness); bestRoute = population{idx}; minDist = fitness(idx); end这里的惩罚系数设置有个门道——超载惩罚要比时间窗惩罚狠得多。实际业务中货车超载被查的风险成本远高于迟到，这个权重比例需要根据业务特性调整。
看看种群初始化怎么处理约束：
function population = initPopulation(data, popSize, maxCap) numCustomers = size(data,1)-1; % 去掉仓库 population = cell(popSize,1); for i=1:popSize route = []; remainingCap = maxCap; unvisited = randperm(numCustomers) + 1; % 客户编号从2开始 while ~isempty(unvisited) next = unvisited(1); if data(next,3) <= remainingCap route = [route, next]; remainingCap = remainingCap - data(next,3); unvisited(1) = []; else route = [route, 0]; % 0表示换车 remainingCap = maxCap; end end population{i} = route; end end这里用0作为分隔符表示不同车辆的路径。比如[2,5,0,3,4]表示第一辆车跑2->5，第二辆跑3->4。初始化时采用贪婪随机策略，既保证容量约束，又引入随机性。
带时间窗的车辆路径规划(VRPTW)问题 遗传算法求解程序代码，蚁群算法，粒子群算法，节约里程算法，禁忌搜索算法 考虑车辆的最大容量限制 考虑违反时间约束和容量约束的惩罚系数 以距离最优为优化目标 代码注释清楚，可改性强，可替换自己的数据 代码使用matlab编写。 可以直接运行的
适应度计算是核心中的核心：
function fitness = calcFitness(population, data, maxCap, pt, pc) fitness = zeros(length(population),1); depot = data(1,:); for i=1:length(population) route = population{i}; totalDist = 0; violation = 0; currentPos = depot(1:2); currentTime = 0; currentLoad = 0; for node = route if node == 0 % 换车 % 回库距离 totalDist += norm(currentPos - depot(1:2)); currentPos = depot(1:2); currentTime = 0; currentLoad = 0; continue; end % 计算到达时间 custData = data(node,:); dist = norm(currentPos - custData(1:2)); arrivalTime = currentTime + dist/60; % 假设速度60km/h % 时间窗惩罚 if arrivalTime < custData(4) waitTime = custData(4) - arrivalTime; elseif arrivalTime > custData(5) violation += (arrivalTime - custData(5)) * pt; end % 载重累积 currentLoad += custData(3); if currentLoad > maxCap violation += (currentLoad - maxCap) * pc; end totalDist += dist; currentPos = custData(1:2); currentTime = max(arrivalTime, custData(4)) + 0.5; % 服务时间0.5小时 end % 回到仓库 totalDist += norm(currentPos - depot(1:2)); fitness(i) = totalDist + violation; end end注意这里的时间计算逻辑：早到要等待，晚到就记惩罚。实际项目中发现，把等待时间折算成司机成本加到目标函数里效果更好，有兴趣可以自己改。
交叉操作采用两点交叉，保留父代优良片段：
function newPop = crossover(parents) newPop = parents; for i=1:2:length(parents) p1 = parents{i}; p2 = parents{i+1}; % 找交叉点（避开换车点） crossPoints = sort(randperm(length(p1),2)); while any(p1(crossPoints(1):crossPoints(2))==0) || ... any(p2(crossPoints(1):crossPoints(2))==0) crossPoints = sort(randperm(length(p1),2)); end % 执行交叉 child1 = [p1(1:crossPoints(1)-1), p2(crossPoints(1):crossPoints(2)), p1(crossPoints(2)+1:end)]; child2 = [p2(1:crossPoints(1)-1), p1(crossPoints(1):crossPoints(2)), p2(crossPoints(2)+1:end)]; newPop{i} = repair(child1); newPop{i+1} = repair(child2); end end修复函数repair是关键，要处理可能出现的重复客户ID和容量超标。这里篇幅所限没展开，完整代码里会包含这个函数。
使用样例：
% 测试数据格式：仓库+4个客户 data = [ 0 0 0 0 24; % 仓库 20 80 30 8 12; 50 30 40 14 18; 100 70 20 9 15; 80 20 60 10 16 ]; [bestRoute, minDist] = GA_VRPTW(data, 50, 100); disp(['最优路径：', num2str(bestRoute)]); disp(['总成本：', num2str(minDist)]); % 可视化 figure; scatter(data(2:end,1), data(2:end,2), 'filled'); hold on; scatter(data(1,1), data(1,2), 100, 'r', 'filled'); title('客户点分布图');跑起来能看到类似这样的输出：
最优路径：2 0 4 3 1 总成本：358.6表示调度方案是：第一辆车跑客户2，第二辆车跑4->3->1（这里客户编号从2开始）。
代码拿回去改数据就能用，调整parameters结构体里的参数就能适应不同场景。想要更快的收敛速度，可以把选择策略改成锦标赛选择；追求解的质量，可以加入局部搜索算子。下期可能会讲讲用禁忌搜索做邻域搜索的trick，有问题的评论区见。
