最近在梳理同时取送货车辆路径优化VRPSPD的求解方案时把遗传算法和模拟退火算法放在同一套算例上各跑了一遍收获不小。这个问题的业务场景其实很常见快递员去一个小区既要卸下派件又要收走寄件送水小哥上门送新桶同时把旧桶拉回仓库。车辆载重有限派件让载重下降、揽收让载重上升路径编排的逻辑就不再是标准VRP那种载重一路减少的简单模式。很多教程把VRP和VRPSPD混为一谈容量检查写错算法跑完却给出一堆不可行路径。这篇笔记会覆盖建模要点、GA和SA的编码与算子设计、参数调法、同场对比以及你大概率也会踩的坑适合正在做配送优化、逆向物流或者刚开始接触元启发式算法的读者。1. 同时取送货问题的真实难点为什么不能直接套标准VRP1.1 业务场景先摆清楚先区分三个容易混淆的问题类型。标准VRP里客户只需要你送东西车辆从车场出发时载重是满的每服务一个客户载重就往下掉一点永远不会回头上升。VRPB带后程取货的车辆路径问题稍微复杂一点车辆必须先服务完所有送货客户才开始回程取货两个阶段严格分开。而VRPSPD是每个客户点同时有两个需求送货量D_i和取货量P_i车辆可以在任意时刻给任意客户又卸又装顺序完全交错。我用一个表把这三种类型直接对比问题类型客户行为车辆载重变化特征标准VRP只送货从车场出发后单调下降VRPB后程取货先送完所有点再统一回程取货先下降后上升但两阶段隔离VRPSPD同时取送货每个点既收货又发货顺序任意每个客户点都可能先降后升载重呈现锯齿状波动从算法角度看VRPSPD的容量判断变得很棘手路径里任意服务完一个客户之后当前载重都不能超过车辆容量Q。明明是同一条路径、同一组客户换个服务顺序可行和不可行就可能颠倒。1.2 用一个数字例子说明顺序决定可行性设车辆容量Q10客户A送货量7、取货量3客户B送货量3、取货量4。如果按顺序A→B车场出发时装载送货量也就是7310恰好等于容量服务A后先卸下7再装上3载重变成10-736再服务B载重变成6-347全程没有超过10路径可行。如果顺序反过来B→A车场出发仍然载10服务B后载重变成10-3411已经超过容量路径不可行。同样两个客户光换一下服务顺序结果完全相反。这就是为什么VRPSPD不能拿路径上送货总量不超过Q这种简化判断来糊弄必须逐点追踪载重变化。很多网上的demo代码死在这一步算法写得再花哨容量判断错了输出的方案根本没法用到真实业务里。1.3 建模时还有一个容易忽略的选择车辆数VRPSPD的数学模型里除了基本的每个客户被服务一次和车辆从车场出发并返回最核心的约束就是上面说的逐点载重约束。但工程上还要考虑车场里可用的车辆数。如果车辆数严格固定目标里可以直接加入超出可用车辆数的惩罚如果允许增加车辆那通常要在目标函数里给每辆车加一个出车成本否则算法会倾向于派出大量车来偷懒得到一条距离很短但完全不现实的方案。我现在习惯在建模阶段就明确三件事客户坐标、D_i和P_i各自的取值范围、车辆容量和可用车辆数。坐标决定距离矩阵D和P决定容量检查的复杂度车辆数决定目标函数要不要加出车成本。这三件事不确定后面所有调参都是白费功夫。2. 解的表达方式编码设计决定算法上限2.1 GA常用的排列编码与容量分割解码遗传算法不能直接操作路径表因为它需要固定长度的染色体来做交叉变异。我用的编码方式很简单把所有客户编号排成一个排列比如50个客户就是1到50的某个随机序列。这个排列本身不是最终路线而是解码器的输入。解码器从左往右扫描排列维护当前路径试着把下一个客户追加到当前路径末尾用VRPSPD容量检查函数判断追加后是否可行。可行就留下不可行就把当前路径封存用这个客户开一条新路径。这样每条路径天然满足容量约束整个解码过程不依赖任何罚函数这是这套编码最大的好处。核心的容量检查函数长这样def route_feasible(seq, D, P, Q): 判断一条路径在VRPSPD语义下是否可行 load sum(D[c] for c in seq) # 出发时装载的送货总量 if load Q: return False for c in seq: load load - D[c] P[c] # 先卸货再装载取货 if load Q: return False return True解码器只需要反复调用这个函数def decode(chrom, D, P, Q): 把客户排列解码成一组路径 routes, cur [], [] for c in chrom: if route_feasible(cur [c], D, P, Q): cur.append(c) else: if cur: routes.append(cur) cur [c] if cur: routes.append(cur) return routes注意一个前提任意单个客户的取货量P_i和送货量D_i本身都必须不超过Q否则单开一条路径也装不下。基准算例一般默认满足自己造数据时要先检查一遍。2.2 SA常用的路径表编码模拟退火不依赖交叉变异它靠的是对当前解做小扰动所以更适合直接用路径表表达解一个列表里面每个元素又是一条路径路径是客户编号列表。这种表达直观计算目标函数的时候遍历所有路径把相邻客户之间的距离加起来就行维护成本低。路径表编码的问题是邻域操作比较自由很容易一步就跳出可行域。所以SA里必须给每条路径都做容量检查或者在目标函数里引入违例惩罚。关于惩罚和直接拒绝哪种更好我在第4节会专门讲。2.3 容量检查是纯函数别把它跟UI、数据读取混在一起我的习惯是把route_feasible写成纯函数输入一条路径序列输出True或False不依赖任何全局变量不修改传入参数。这样GA解码要用SA每次邻域移动之后也要用甚至后面想换C重写、加并行都能直接搬过去。还有一个小优化如果客户数量上百SA每次移动都重新算整条路径的载重曲线会有点浪费。可以预计算每个客户的前缀送货量和取货量在2-opt这类操作里只用更新被翻转的那段的载重差。实测下来50个客户规模Python里不优化也扛得住但到了200个客户这些细节就开始影响调参效率了。3. 遗传算法在VRPSPD上的工程化实现3.1 初始种群别全用随机排列GA的第一步是生成初始种群。很多人直接随机生成一批排列这没错但纯随机的种群前期探索浪费严重可能要二三十代才摸到稍微像样的区域。我的做法是随机排列占80%再用最近邻启发式造几条种子路径填充剩下的20%。具体做法从车场出发每次选离当前点最近的未调度客户加到当前路径直到容量检查不通过就开新路径。把这样的路径顺序打散塞进不同染色体里当作基因片段。种子的作用不是夺冠而是把搜索起点拽到可行区域附近让GA不用花太多时间在纯随机空间里瞎撞。种子比例控制在20%以内保留足够的多样性。3.2 锦标赛选择、PMX交叉和变异怎么搭选择阶段我用锦标赛选择锦标赛规模k3每次从种群里随机抽3个个体选适应度最好的一个进入下一代同时用精英保留策略把历代最优的2个个体原封不动复制到下一代。k越大选择压力越大但k太大容易早熟3是比较稳的起点。交叉阶段必须用保序类交叉算子。最直观的错误是拿单点交叉去切排列型染色体——切出来的子代要么重复客户要么丢客户解码器直接报废。我用的是部分映射交叉PMX随机选两个切点交换中间片段再用片段内的映射关系修复两侧的重复基因。这种算子能保证子代仍然是合法的客户排列不会出现重复或缺失。变异我配两套两点交换变异随机挑两个位置互换客户概率0.1反转变异随机反转一段子序列概率0.05。反转变异的作用值得多说一句它对应路径里的2-opt思想能一次改变一段路径的走向对消除交叉路线很有效比单点交换更容易产生大改善。遗传算法的完整参数我一般这样设参数取值备注种群规模100客户数50-100时这个量级够用锦标赛规模3选择压力适中的起点精英保留2防止最优个体被交叉变异破坏交叉概率0.9PMX交叉变异概率0.1 / 0.05两点交换/反转变异终止条件300代或连续50代无改进两者先到为准3.3 目标函数里的车辆数惩罚很容易漏采用排列编码解码方案后每个染色体解码出来的路径天然可行不需要罚容量。但车辆数问题还没解决。解码器为了保住可行性可能在某些基因排列下解出很多条短路径车辆数远超可用数量。我的适应度函数是fit 总行驶距离 车辆数超出惩罚超出惩罚我常设成距离均值的一个大倍数比如500或1000。为什么是固定大值而不是固定小值因为如果超出惩罚只有10算法会发现多派一辆车省下来的绕路距离往往超过10于是它乐得多派车惩罚太大又会让搜索彻底不敢试探高车辆数区域。取一个明显大于单条路径平均距离的值既能让搜索意识到多用一辆车代价很高又不会完全封死这方向。4. 模拟退火的设计邻域动作和冷却计划4.1 五种邻域动作怎么搭配SA的探索能力几乎全部来自邻域操作。我在VRPSPD上常用的邻域动作是下面五种路径内2-opt选一条路径反转其中一段子序列。适合消除路径内部的交叉和回头路。路径内两点交换同一条路径里互换两个客户位置小幅调整顺序。跨路径两点交换从两条路径各取一个客户交换相当于把两个点换车服务。单点迁移把一个客户从路径A移出插入路径B的最优可行位置。这是跨路径调整的主力算子。跨路径尾段交换2-opt*把两条路径各切一刀交换后半段。这种操作在纯送货VRP里是王牌算子但VRPSPD里后半段交换会大幅改变各段载重分布必须重新做容量检查我一般搭配使用比例压在20%左右。我建议的比例是路径内2-opt占30%、单点迁移占30%、跨路径两点交换占20%、尾段交换占20%路径内两点交换偶尔用。每次迭代随机选一个动作生成新解然后按Metropolis准则决定是否接受。不要只盯着一个大算子猛调五个动作配合起来搜索才能同时在路径内部顺序和客户在路径间的分配两个维度上移动。所有动作执行完统一调用route_feasible做一次可行性判断。这一步无论如何不能省。4.2 初始温度、冷却系数和内循环次数怎么定模拟退火最怕瞎拍参数。温度太高等于随机游走温度太低一步都动不了。我按初始接受率约0.9反推初始温度从初始解出发做2000到3000次随机邻域移动记录每次目标函数变化的绝对值取平均值再用公式T0 -Δ_avg / ln(0.9)算出初始温度。冷却系数α一般取0.95到0.99之间。我常用0.97意味着每轮降温后温度剩97%整体降温速度适中既不会太快被冻住也不会慢到跑不完。内循环次数取30×nn是客户数也就是每个温度层内做大约1500次邻域移动。终止温度设为1e-3×T0温度降到这个水平基本没什么接受坏解的机会了。核心循环骨架T init_temperature() alpha 0.97 best_feasible init_sol while T T_min: for _ in range(30 * n): new_sol pick_neighbor(sol) delta objective(new_sol) - objective(sol) if delta 0 or random.random() math.exp(-delta / T): sol new_sol if feasible(sol) and objective(sol) objective(best_feasible): best_feasible sol T * alpha4.3 罚函数还是直接拒绝我的实测结论这个问题我专门做过对比。小规模实例上直接拒绝不可行邻域解SA表现稳定且代码简单。但实例规模变大、容量又比较紧的时候可行解区域可能被不可行区域隔成好几块直接拒绝会让算法困在一小块区域里出不去。我的方案是罚函数搜索全局最优可行解双轨记录目标函数里加一个违例惩罚项允许搜索初期穿越不可行区域同时单独维护一个历史最优可行解每接受一个新解就检查它是否可行且优于当前记录可行就更新。算法结束时返回这个历史最优可行解不返回最后那个解。罚系数从1.0开始每轮降温乘以1.005缓慢增大降温后期罚项远远大于距离项搜索自然被拉回可行区域。这条路我走下来是通的比在代码里疯狂调一个固定罚系数省心得多。5. 同一套算例上的实测对比5.1 测试算例和运行环境为了对比公平我生成了一批随机实例做测试50个客户坐标在[0,200]×[0,200]范围内均匀随机分布送货量D_i在[5,25]内均匀随机取货量P_i在[0,20]内均匀随机车辆容量Q120可用车辆数8辆距离用欧氏距离。每个算法独立运行20次记录最好值、平均值、最差值和平均耗时用Python实现的单线程版本同一台机器上跑。5.2 数据结果和规律一个代表性子实例的结果如下算法最好距离平均距离最差距离平均耗时遗传算法1684.31725.61799.817.8s模拟退火1659.21690.51748.210.3s两个算法都能稳定给出可行解这个前提保证了对比有意义。从这个实例看模拟退火在最好值和平均值上都略胜一筹而且耗时少了一半左右遗传算法最差值偏大说明它在某些运行里还是没有彻底摆脱早熟收敛。收敛过程也有明显差异SA前期温度高目标值下降很快几乎一上来就冲进低值区GA前期下降慢要等种群逐步筛选出来大约跑到150代之后才开始逼近SA的水平。换了几个不同种子生成的实例规律基本稳定50客户这个规模下SA的中位数表现优于GA波动更小。不过这是单机Python实现下的结论不说明遗传算法本身弱只是在这个场景、这个规模下SA少量多点扰动的邻域搜索比GA的群体搜索更有效率。5.3 什么场景选GA什么场景选SA我的选型经验很简单。客户规模在100以内、算例固定、需要快速出方案的话优先模拟退火它的参数少跑一次成本低结果稳定。但如果问题更复杂比如加了时间窗、多车场、或者客户数量几百上千遗传算法基于种群并行探索的优势就出来了——SA很容易在复杂约束下被局部最优困死而GA的种群天然保留了多个搜索方向的备选。真要追求效果我不会二选一而是做混合GA做主框架每一代选出最优的几个个体用SA做局部精修再放回种群。这也是我目前在实际项目里最常用的套路。6. 实操中容易翻车的四个坑6.1 容量检查写成了纯送货逻辑这是最常见、后果最严重的错误。很多人从标准VRP的代码改过来容量检查只算一条路径上送货量之和忽略了取货会重新把载重拉起来。# 错误示范只检查送货总量忽略取货加回载重 load sum(D[c] for c in seq) if load Q: return False这样的检查在纯送货实例上没问题但放到VRPSPD上车辆可能在路径中间凭空多出十几件取货超载却被当成可行解输出。我们用1.2节那个Q10的例子验证一下就知道顺序B→A明明是超载的错误检查却会放行。这个坑藏得很深因为算法照样在收敛距离还在下降直到你拿真实数据核对路径才发现一路都是超载。我现在每写完一个检查函数第一件事就是手动构造几组看似可行实则超载的小算例去验证。6.2 惩罚系数拍脑袋搜索要么原地打转要么交不出可行解罚函数法里罚系数太小最后解可能不可行罚系数太大等价于直接拒绝又失去穿越不可行区域的能力。我早期在SA里用一个固定罚系数调了一整天不是最后一步解超载就是搜索空间被压得太死。后来改用罚系数随温度缓慢增大历史最优可行解单独记录的组合才把这问题一次性解决。方法是死的思路才是关键罚函数不是为了最终得到一个不可行解而是让搜索在高温阶段有更大活动范围低温阶段自然回归可行。6.3 早熟收敛精英保留和锦标赛的副作用GA跑到一定代数后种群里的染色体越来越像交叉生成的新个体几乎都是父母的翻版这种时候再跑多少代都白搭。我在测试里遇到最典型的场景就是最差值比平均值高出很多比如1700的种群平均里总有一个1790的异类那就是探路者还没死光后面纯靠运气出结果。应对手段我试过几种一是动态提升变异概率当种群最优值连续20代不变时把反转变异概率从0.05提到0.2二是换血操作连续多代没改进就把种群最差的30%随机重新初始化三是记录种群中不同染色体数量低于某个阈值就触发重启。实际效果都还行最省事的是第二种直接换血。6.4 目标函数里没算车辆数出来一堆空车拼凑路径如果只用总距离当目标GA很容易解码出12辆甚至更多短路径因为少跑路但多派车在纯距离目标里是划算的。真实业务里多派一辆车意味着多一个司机、多一趟出车成本这个代价几乎总是超过节省的那点里程。处理办法前面说了在目标函数里给每辆车加一个出车成本。按我的经验出车成本取单条路径平均距离的1.5倍左右起步比较稳然后根据业务实际调整。举个直观的例子8辆车跑1800距离总代价18008×500580012辆车跑1500总代价150012×5007500算法自然会选8辆车的方案。不加这个成本出来的路径表根本不敢拿给调度看。最后再分享一个实战体会单纯比较GA和SA谁更强意义有限两者在VRPSPD上的差距远小于错误建模带来的差距。我现在的标准流程是先把容量检查、车辆数成本、解码方式这三件基础事做扎实再从业务规模决定用GA还是SA甚至直接做GASA混合。如果哪天你要处理几百个客户的大算例不妨先试试距离聚类分簇求解的思路把大问题拆小再在每个簇上用SA精修效果常常比硬跑一个大算法好得多。