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

Matlab 遗传算法求解带时间窗的车辆路径问题 VRPTW问题源码+详细注释问题描述：配...

news 2026/7/3 14:24:50

Matlab 遗传算法求解带时间窗的车辆路径问题 VRPTW问题源码+详细注释问题描述：配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足。可改坐标，需求量等数据保证运行

今天咱们来聊聊怎么用Matlab玩转带时间窗的车辆路径问题（VRPTW）。这个场景在物流配送里特别常见——比如你们小区门口那个每天定点送鲜奶的冷链车，既要准时送到又不能超载，咱们的算法就得解决这种带约束的路径规划。

先看核心代码结构，整个遗传算法实现分为五个模块：初始化种群、适应度评估、选择、交叉、变异。咱们重点看看适应度计算和变异操作这两个最容易出彩的部分。

% 适应度计算函数（精简版） function [fitness] = calculateFitness(population, distMatrix, demand, timeWindows, vehicleCapacity) penalty = 1000; % 时间窗违反惩罚系数 [popSize, chromLength] = size(population); fitness = zeros(popSize,1); for i=1:popSize route = population(i,:); totalDistance = 0; timeViolation = 0; currentLoad = 0; currentTime = 0; prevNode = 1; % 配送中心起点 for j=1:chromLength currNode = route(j); currentLoad = currentLoad + demand(currNode); % 载重超限则返回中心 if currentLoad > vehicleCapacity totalDistance = totalDistance + distMatrix(prevNode,1); prevNode = 1; currentLoad = demand(currNode); currentTime = 0; % 装货时间暂简化为0 end travelTime = distMatrix(prevNode, currNode); arrivalTime = currentTime + travelTime; % 计算时间窗惩罚 if arrivalTime > timeWindows(currNode,2) timeViolation = timeViolation + (arrivalTime - timeWindows(currNode,2)); elseif arrivalTime < timeWindows(currNode,1) timeViolation = timeViolation + (timeWindows(currNode,1) - arrivalTime); end totalDistance = totalDistance + travelTime; prevNode = currNode; currentTime = max(arrivalTime, timeWindows(currNode,1)); % 等待策略 end fitness(i) = totalDistance + penalty * timeViolation; end end

这个适应度函数暗藏玄机：时间窗惩罚不是简单计数而是累加偏差量，这样算法会更倾向于修正严重超时的个体。注意第28行的等待策略——司机如果到得太早不会立即卸货，而是等到时间窗开启，这更符合真实场景。

变异操作咱们玩点有意思的，用了个贪婪插入策略：

function newChrom = greedyMutation(chromosome, distMatrix) candidate = find(chromosome > 1); % 排除配送中心 if length(candidate) < 2 newChrom = chromosome; return; end % 随机选个倒霉节点 target = candidate(randi(length(candidate))); remainingNodes = setdiff(candidate, target); % 找最优插入位置 minCost = inf; bestPos = -1; for i=1:length(remainingNodes)+1 tempChrom = [remainingNodes(1:i-1), target, remainingNodes(i:end)]; cost = calculateRouteCost(tempChrom, distMatrix); if cost < minCost minCost = cost; bestPos = i; end end newChrom = [1, tempChrom(1:bestPos-1), target, tempChrom(bestPos:end)]; end

这种变异方式比随机交换更高效，每次尝试把某个节点插到当前最优位置。注意第7行排除配送中心的操作，保证路径始终从中心出发。

在实战中，建议把交叉算子换成顺序交叉（OX），避免破坏优良基因段。比如：

function child = oxCrossover(parent1, parent2) points = sort(randperm(length(parent1),2)); segment = parent1(points(1):points(2)); remaining = parent2(~ismember(parent2, segment)); child = [remaining(1:points(1)-1), segment, remaining(points(1):end)]; end

这种交叉方式能保留父代中连续的优良路径片段，同时引入新的排列组合。

跑个实例看看效果，设置20个客户点，3台车：

% 参数配置 custnum = 20; % 客户数量 v_num = 3; % 车辆数 pop_size = 50; max_gen = 300; % 随机生成数据（实际使用可替换为真实坐标） coordinates = [randi([0,100],custnum,2); 50 50]; % 最后一个是配送中心 demand = [randi([1,5],custnum,1);0]; timeWindows = [randi([0,50],custnum,1), randi([60,200],custnum,1); 0 200]; vehicleCapacity = 15; % 计算距离矩阵 distMatrix = pdist2(coordinates, coordinates);

运行后典型优化过程如下图（假装有图），前50代快速收敛，150代后进入精细搜索阶段。实际测试中，20个点的问题能在2分钟内找到可行解。

几个调参小技巧：