基于遗传算法的VRPTW问题求解：从元胞数组编码到多约束优化

1. 遗传算法与VRPTW问题初探第一次接触带时间窗的车辆路径问题VRPTW时我被它复杂的约束条件弄得头晕眼花。想象一下你是一家物流公司的调度员手上有7辆载重不同的货车需要给16个客户送货。每个客户都有特定的需求有的要求上午10点前送达有的只接受下午2-4点收货更麻烦的是每辆车的容量还各不相同。这就像玩一个高难度拼图游戏而遗传算法就是我的秘密武器。遗传算法的神奇之处在于它模拟了生物进化过程。我把它理解为达尔文式的数学优化随机生成一批初始解种群通过选择、交叉、变异等操作让解的质量像生物进化一样越来越好。在VRPTW问题中每个解都代表一种配送方案我们需要找到既满足所有约束条件时间窗、载重等又能让总成本最低的那个最优解。实际操作中最让我头疼的是如何表示这些复杂的配送方案。试过用矩阵、结构体等各种方法后我发现MATLAB的元胞数组简直是为此量身定做的神器。它就像个万能收纳盒可以把车辆数量、车型选择、客户分配这些不同类型、不同维度的数据整齐地打包在一起。比如用{1,2}位置存车型{1,3}位置存各车配送客户数{1,4}存具体客户编号这种结构既直观又便于后续的遗传操作。2. 元胞数组编码的艺术2.1 解结构的巧妙设计在项目初期我尝试用传统矩阵表示解很快就遇到了瓶颈——不同车辆的配送客户数量不同固定维度的矩阵要么浪费空间要么无法完整存储信息。直到改用元胞数组问题才迎刃而解。这里分享我的编码方案populationMat cell(50,4); % 50个个体每个个体4个字段 % 示例个体 populationMat{1,1} 4; % 使用4辆车 populationMat{1,2} [2,3,7,6]; % 车辆编号 populationMat{1,3} [5,6,2,3]; % 各车配送客户数 populationMat{1,4} [1 3 15 11 4 16 2 5...]; % 客户序列这种结构的精妙之处在于第三列和第四列形成了天然的键值对。比如第2号车配送5个客户就对应客户序列的前5个编号。在后续计算路径距离时这种存储方式可以直接映射到坐标矩阵进行计算。2.2 初始化种群的实战技巧创建优质初始种群是算法成功的关键。我的经验是完全随机生成会导致大量个体违反约束浪费计算资源。经过多次调试我总结出这些实用策略容量优先分配先对客户按需求量降序排列优先用大容量车辆服务大需求客户时间窗聚类将时间窗相近的客户尽量分配给同一辆车减少时间惩罚随机性控制引入概率矩阵确保初始解既有多样性又相对合理function populationMat InitializeIndividuality(...) for i 1:populationNumber % 基于概率矩阵选择车辆数 vehicleNum randsample(1:M,1,true,probabilityMat); % 按容量约束分配客户 while ~checkCapacity(assignment,truckVolume,customerRequirement) assignment smartAssignment(...); end populationMat(i,:) {vehicleNum, vehicleIDs, clientCounts, clientSequence}; end end实测发现这种半智能化的初始化方式能使算法收敛速度提升40%以上。特别是在处理20个以上客户点时效果更为明显。3. 多约束条件下的适应度设计3.1 成本函数的平衡之道适应度函数是遗传算法的指挥棒在VRPTW中需要同时考虑运输成本与行驶距离成正比时间惩罚早到或晚到的惩罚成本约束惩罚对超载、超时等违规的严厉惩罚我的方案采用分层加权法function fitness CalcuFitCapacity(...) baseCost alpha * totalDistance; % 基础运输成本 timePenalty D * sum(max(0, arrivalTime - acceptTime)); % 时间惩罚 violationPenalty 1e6 * (overload overtime); % 约束惩罚 fitness baseCost timePenalty violationPenalty; end这里有个重要细节约束惩罚系数1e6要远大于其他项确保算法优先满足硬约束。曾经因为把这个值设得太小1000结果算法为了节省一点距离成本竟然容忍了超载情况3.2 约束处理的实用技巧处理多重约束时我总结出这些经验预处理剪枝在计算适应度前先检查明显违规的解直接赋予极大惩罚值动态惩罚系数随着迭代次数增加逐步提高惩罚力度可行性优先在早期迭代中更看重约束满足后期再精细优化成本特别是在时间窗计算时要注意服务时间的累积效应车辆到达时间 上一客户离开时间 行驶时间 离开时间 max(到达时间, 最早允许时间) 服务时间这个计算过程需要按照客户访问顺序递推我专门写了时间计算函数来确保准确性。4. 遗传操作的优化策略4.1 选择算子的性能对比试过轮盘赌、锦标赛等多种选择方式后我发现精英保留锦标赛的组合效果最佳function newPopulation SelectionFunction(population,popNum,fitness) eliteNum round(0.1*popNum); % 保留10%精英 [~,idx] sort(fitness); newPopulation(1:eliteNum,:) population(idx(1:eliteNum),:); % 锦标赛选择 for i (eliteNum1):popNum candidates randperm(popNum,3); % 3人锦标赛 [~,best] min(fitness(candidates)); newPopulation(i,:) population(candidates(best),:); end end这种策略既保证了优秀基因不会丢失精英保留又维持了种群多样性锦标赛的随机性。实际测试中比纯轮盘赌选择收敛速度提高约25%。4.2 交叉操作的创新设计标准交叉操作在VRPTW问题中容易产生无效解。我设计了路径片段交叉法随机选择一辆车及其客户子序列在另一个体中寻找兼容的车辆有足够剩余容量交换这两个片段同时调整相关车辆的客户计数function offspring PathSegmentCrossover(parent1, parent2) % 选择父代1的某辆车及其客户 vehIdx randi(parent1{1}); segStart sum(parent1{3}(1:vehIdx-1)) 1; segEnd segStart parent1{3}(vehIdx) - 1; segment parent1{4}(segStart:segEnd); % 在父代2中寻找可插入位置 feasibleVehs find(truckVolume sum(customerRequirement(segment))); if ~isempty(feasibleVehs) insertVeh feasibleVehs(randi(length(feasibleVehs))); % 执行片段插入... end end这种交叉方式最大程度保留了有意义的路径片段相比单点交叉可行性提高了近60%。4.3 变异操作的精细调控变异是跳出局部最优的关键我采用多模式混合变异变异类型操作描述适用场景概率权重客户交换随机交换两个客户的位置局部优化40%车辆变更将部分客户转移到其他车辆全局探索30%时间窗优化调整客户访问顺序以满足时间窗约束处理30%实现时采用自适应变异率当种群多样性下降时适应度方差变小自动提高变异概率。这个技巧帮助我在多个测试案例中成功避免了早熟收敛。5. MATLAB实现中的性能优化5.1 向量化计算的加速技巧遗传算法需要反复计算适应度原始循环方式速度很慢。通过向量化改造我获得了近10倍的加速% 原始循环方式 for i 1:populationNumber for j 1:populationMat{i,1} % 计算每辆车的路径距离... end end % 向量化改造 allDistances zeros(populationNumber,1); for i 1:populationNumber vehicleRoutes mat2cell(populationMat{i,4}, 1, populationMat{i,3}); dists cellfun((route) sum(pdist(customerPos([1,route1,1],:))), vehicleRoutes); allDistances(i) sum(dists); end关键点在于使用mat2cell快速分割客户序列用cellfun替代内层循环预分配内存zeros初始化5.2 并行计算的实现方案当客户点超过30个时我启用了并行计算工具箱if N 30 parpool(local,4); % 启动4个工作进程 parfor i 1:populationNumber fitness(i) CalcuFitParallel(populationMat(i,:),...); end else % 串行计算... end注意并行化时要避免数据竞争我将适应度计算封装成独立函数确保每个worker访问的数据都是只读的。在16核服务器上处理50个客户点时速度提升可达8倍。6. 实战案例与结果分析6.1 16客户点案例详解以原始问题为例经过500代迭代后最优方案使用4辆车编号2,3,6,7总成本为285.7万元。具体配送路径为2号车配送中心→客户1→客户3→客户15→客户11→客户4→配送中心3号车配送中心→客户16→客户2→客户5→客户12→客户13→客户14→配送中心6号车配送中心→客户10→客户9→客户6→配送中心7号车配送中心→客户7→客户8→配送中心通过绘制收敛曲线发现前100代算法快速下降之后进入精细优化阶段。有趣的是在第237代时出现了一次显著改进通过分析日志发现是一次关键变异操作将客户14从超载的2号车转移到了3号车。6.2 大规模问题挑战当尝试将方法扩展到50个客户点时遇到了新挑战计算时间呈指数增长可行解比例急剧下降容易陷入局部最优我的改进措施包括采用分层优化先聚类分区域再分别优化引入局部搜索在变异操作中加入2-opt局部优化使用精英库保留历史最优解避免退化经过这些优化50客户点问题的求解时间从原来的3小时缩短到45分钟左右且解的质量提高了约15%。