自适应双种群协同鸡群算法求解带时间窗外卖配送路径规划Matlab实现

下午两点四十分骑手App里同时跳出12个新订单取餐点在两个商圈送餐点分布在五个写字楼其中三个客户备注请在12点半前送到电动车续航还剩45公里后座保温箱只剩三个空位——你先跑哪条线放弃哪几单怎么绕才不超时这样的调度问题每天在城市里发生数百万次而运营方给出的答案往往不是靠骑手经验而是靠路径规划算法。本文要聊的就是这类问题的一种求解方案用自适应双种群协同鸡群算法ADPCCSO来解带时间窗的外卖配送路径规划问题并给出完整的Matlab实现思路和源码级拆解。这个问题的本质是典型的VRPTW带时间窗的车辆路径问题变体目标函数融合了路径成本、服务客户数量、服务时间、载量、路径长度等多个维度属于多约束组合优化问题。文章适合运筹优化方向的研究生、物流调度工程师、以及正在做智能算法课程设计或毕业设计的同学我会从数学建模讲到算法原理再落到Matlab代码和实验调参尽量把每个决策背后的原因说清楚。1. 带时间窗的外卖配送问题先搞清楚要解什么1.1 骑手视角下的难题怎么变成算法能算的模型骑手送外卖最直观的目标是跑的路越短越好。但往深了想好的定义要复杂得多客户给你一个2小时的预计送达窗口实际早到10分钟可以等晚到10分钟就可能收获一个投诉保温箱容量有限取了一大堆餐却发现最后一个订单没法装电动车续航决定了你不可能无限绕路甚至取餐顺序本身也有讲究——一个订单先到店取餐再送到客户手上取送顺序不能颠倒。这些约束交织在一起就构成了一个比标准车辆路径问题更复杂的组合爆炸问题。用运筹学的语言重新描述有一个骑手也可以推广到多个骑手从配送站点出发要访问多个订单的取餐点、送餐点每个点有服务时间窗口骑手有载量限制目标是让总成本最小。每个订单拆成两个节点取餐点和送餐点且必须先到取餐点再到送餐点。这就是带时间窗、带取送货配对约束的车辆路径问题学术上称为PDPTWPickup and Delivery Problem with Time Windows外卖场景在此基础上还叠加了容量小、批次多、时效性强的特点。1.2 目标函数路径成本不只是距离标题里提到的目标函数包含五个要素最优路径成本、服务客户数量、服务时间、载量、路径长度。我在建模时的做法是把它们统一成一个加权总成本形式如下min F w1 * D_total w2 * T_wait w3 * T_delay w4 * V_penalty - w5 * N_served其中D_total是所有骑手行驶的总路径长度T_wait是早到造成的等待总时长T_delay是晚到造成的延迟总时长V_penalty是载量超限的惩罚项N_served是实际服务的客户数收益项反过来做负向奖励。这里有几个关键设计理由。第一路径长度和路径成本并不是一回事。路径成本可以包含行驶距离带来的能耗、时间带来的骑手工时成本所以D_total前面有系数w1必要时还可以对每段路径按路况加权。第二时间窗违规必须拆成等待和延迟两个独立项因为早到等待只是消耗骑手时间晚到则直接伤害客户体验惩罚系数应当不对称。第三服务客户数量放在目标函数里是为了防止算法为了省钱而放弃订单——当一个解服务了更多客户但路径稍长时w5 * N_served的收益能平衡这个取舍这在现实中对应着骑手多接单、平台多成交的诉求。1.3 约束条件的处理方式什么必须硬什么可以软约束分两类。载量约束和取送顺序约束是硬约束违反后解不可行需要在解码阶段就保证满足。时间窗约束我建议做成软约束用惩罚函数处理原因很现实外卖平台在实际运营中允许一定程度的超时完全硬性要求每个订单都在时间窗内送达可能根本不存在可行解尤其是在高峰期订单密度大的时候。时间窗的软硬设计也有讲究。我测试过的做法是分段惩罚早到等待按每分钟一个较低系数晚到延迟按每分钟一个较高系数超过一个容忍上限比如30分钟再加一个二次项惩罚模拟客户取消订单或投诉的边际效应。这个分段设计在实验里比单一段线性惩罚收敛效果更好因为惩罚梯度更符合实际业务风险曲线。2. 从鸡群觅食到ADPCCSO三个关键改进都是冲着什么去的2.1 鸡群算法的等级秩序本身就是一种分工策略鸡群算法Chicken Swarm Optimization, CSO是2014年提出的一种群体智能算法灵感来自鸡群觅食时的等级社会结构。公鸡是头领适应度最好负责大范围搜索引导方向母鸡跟在公鸡附近觅食局部探索小鸡只跟着自己所属的母鸡活动搜索范围最小。每隔一定代数鸡群的等级关系就重新洗牌一次优秀个体有机会成为公鸡掉队的会被降级。这个机制和粒子群、遗传算法最大的不同在于角色分工天然存在。粒子群里所有粒子都是同质个体各自朝自己的历史最优和全局最优飞行容易聚集到局部解而鸡群里公鸡、母鸡、小鸡的搜索半径和引导方式差异明显种群天然形成了多层次探索结构。我刚开始用CSO解这个配送问题时发现它对中小规模实例20到60个订单还不错但有两个明显短板一是收敛后期精度不够二是对时间窗约束强的问题容易早熟——所有个体都挤到一个还不错的局部解但离最优解还有距离。ADPCCSO的三处改进就是针对这两个短板来的。2.2 自适应参数让搜索步长跟着收敛状态走第一处改进是自适应参数调整。原版CSO里公鸡的搜索步长由正态分布决定但这个正态分布的标准差是固定的迭代前期后期一个样这不符合优化问题的普遍规律——前期需要大步长铺开探索后期需要小步长精细打磨。ADPCCSO让标准差随迭代次数动态变化sigma_t sigma_max * exp(-lambda * (t / T)^2)其中T是总迭代次数lambda是衰减系数前期sigma大公鸡跳跃范围大能快速覆盖解空间后期sigma缩小公鸡在最优解附近细致搜索。母鸡和小鸡的跟随系数C1、C2、F也做类似的自适应处理但变化曲线不同——跟随系数采用分段策略在迭代中期调高让种群在完成全局定位后加强局部开发。实测下来这个改动对收敛精度提升非常明显60客户规模的问题平均最优解能再压低3%到5%。2.3 双种群与协同一个管时间紧不紧一个管路线顺不顺第二处改进是双种群设计。外卖配送问题有两个核心目标经常互相打架满足时间窗和缩短路径长度。一条距离最短的路线可能因为有客户卡在时间窗边缘而频频超时一条时间窗全部满足的路线又可能绕了很多冤枉路。单个种群在搜索时很难同时兼顾这两种方向。ADPCCSO的做法是把种群拆成两个各100只鸡的独立子种群各自用不同的评价偏好。子种群A在适应度评估里把时间窗惩罚系数调高强制个体优先满足时效子种群B把路径长度的权重调高重点优化行驶距离。这样两个子种群在解空间里形成了不同的搜索偏向一个从时间可行的角度爬山一个从距离最短的角度爬山。第三处改进就是协同机制。如果双种群各搜各的等于白分所以ADPCCSO每10代执行一次信息交换把子种群A的top10%精英解拷贝到子种群B替换掉B中适应度最差的个体反之亦然。这个机制保证两个子种群不会在各自的偏好方向上钻牛角尖而是时刻知道另一条路线上也有好解。我试过不交换信息的双种群版本效果和单种群没本质差别说明协同在设计上是决定性的。3. ADPCCSO的Matlab实现编码、解码、约束处理全流程3.1 用random-key编码把离散路径变成连续变量鸡群算法的原生设计面向连续优化问题个体的位置是一个实值向量。但配送路径规划是离散的组合优化问题最简单的做法是做自然数排列编码比如1 3 2 4表示按1、3、2、4的顺序访问节点可是排列编码的交叉、变异操作和鸡群运动公式很难对接——鸡群的位置更新是实值加减你没法对一条排列直接加减另一个排列。我的方案是用random-key编码每个个体用一个长度为2NM-1的实值向量表示其中N是订单数M是骑手数。解码时服务节点部分按实值大小排序得到访问顺序每一段的结束位置由一个分隔符阈值决定。这样鸡群的实值位置更新算法可以原封不动地使用只需要在适应度评估时多一步解码过程。简单说算法搜索的是实值空间解码后映射到离散路径空间搜索过程和问题域解耦这是连接群智能算法和组合优化最稳妥的桥。3.2 解码与路径拆分容量和时间窗可行性怎么判断解码是核心中的核心。我把解码拆成两步走避免一步到位的复杂逻辑容易出错。第一步先按实值向量排序生成订单的访问序列。每个订单有两个服务节点——取餐点pickup和送餐点delivery排序时对订单ID排序然后在路由过程中逐一扩展pickup和delivery节点。这样保证了一个订单的两个节点天然配对不会出现先送后取的违约情况。第二步把序列分给各骑手。分隔符的处理我采用一个简单可靠的方法先把所有节点序列排好再按骑手容量和时间窗可行性逐个尝试插入。试错法虽然朴素但当节点数在可接受范围内时它的逻辑清晰、不易出错——写算法代码逻辑可靠性比花哨技巧重要得多。载量约束在解码时就做硬性检查当一个骑手的已分配订单总重量加上下一个订单的重量超过容量上限就强制开一条新路径。时间窗约束则不在解码时做硬拒绝只是把该路径上的时间窗违反度累积起来算进惩罚项方便后续算法探索稍晚一点也还行的有潜力解。硬约束保证可行性软约束保留搜索空间这个分工要想清楚。3.3 三种时间窗惩罚方案我从分段惩罚里收获了什么时间窗惩罚我踩过不少坑。第一种方案是硬性拒绝超时一违反就丢弃这个解结果是大量个体不可行种群很快就失去多样性收敛曲线惨不忍睹。第二种方案是线性惩罚每分钟超时罚一个固定值可行不可行都在一个尺度上比较但问题在于早到和晚到混在一起罚算法最终会倾向于让小部分订单极度超时而大部分订单准时这不符合实际——顾客对一份迟迟不来的外卖的愤怒是加速上升的。最终我采用了分段二次惩罚模型Penalty alpha * sum(wait_i) beta * sum(max(0, delay_i)) gamma * sum(max(0, delay_i - tau).^2)alpha对应早到等待的每分钟成本beta对应常规延迟成本gamma是延迟超过阈值tau后的加速惩罚tau一般设为15到20分钟。alpha、beta、gamma本身也做自适应迭代前中期用小罚值保证搜索自由的探索空间迭代后期逐步加大罚值让算法收网去精修可行解效果比固定罚值好不少。3.4 主循环骨架ADPCCSO核心代码结构下面这段是ADPCCSO主循环的Matlab核心骨架我做了简化去掉了参数细节保留了算法轮廓function [best_solution, best_cost] ADPCCSO(data, params) % data: 包含客户坐标、时间窗、需求量等结构的实例数据 % params: 种群规模、迭代代数、双种群交互间隔等参数 % 初始化两个子种群, 每个个体是 random-key 实值向量 pop_A init_population(params.pop_size, params.dim); pop_B init_population(params.pop_size, params.dim); for iter 1:params.max_iter for sub 1:2 pop eval_selection(sub, pop_A, pop_B); % 选择当前子种群 fitness evaluate_population(pop, data); % 解码 计算目标函数 % 鸡群等级排序: 适应度排序, 分配公鸡/母鸡/小鸡角色 [sorted_fit, idx] sort(fitness); hierarchy build_hierarchy(sorted_fit, idx); % 按角色更新位置: 自适应参数在 update_position 内部调用 pop_new update_position(pop, hierarchy, iter, params); pop_new boundary_repair(pop_new); % 边界修复 pop select_elite(pop, pop_new, fitness);% 精英保留 end % 每10代执行双种群精英交换 if mod(iter, params.exchange_interval) 0 pop_A exchange_elite(pop_A, pop_B, 0.1); pop_B exchange_elite(pop_B, pop_A, 0.1); end end best_solution decode(best_individual, data); best_cost sum(best_solution.cost_components); end这段骨架里最需要注意的有两点。一是角色分配的依据是适应度排序每隔一定代数重新洗牌但它只在种群内部进行两个子种群的角色分布可以不同。二是边界修复random-key向量虽然理论上允许任意实值但约束在[0,1]区间内的个体变异后超出边界时不能简单截断我试过截断法会引入大量重复值导致解码时排序失效后来改成越界个体重新在边界内随机初始化一小段分量种群多样性保住了很多收敛稳定性也上来了。成功的解码还有一个容易被忽略的点距离矩阵必须预先算好并缓存。在Matlab里重复计算欧式距离是很大的开销预处理一次距离矩阵后续所有解码操作都直接查表整个算法运行时间可以缩短30%以上。4. 实验对比ADPCCSO在60个客户规模下的实际表现4.1 测试数据怎么生成才公平这里有几个原则为了验证算法效果我构造了几组不同规模的测试实例从20个客户到100个客户。数据生成遵循以下原则客户坐标在[0,100]的二维平面内随机分布取餐点聚集在3到5个区域模拟商圈分布送餐点分散模拟居民区和写字楼。这个结构成心制造取送分离的难度比纯随机分布更难解否则算法性能拉不开差距。每个客户的时间窗采用两种生成方式。方式一随机生成一个期望送达区间比如[9, 11]小时模拟配送时段每个客户的时间窗宽度从30分钟到90分钟不等模拟不同的时效容忍度方式二从起送点出发按最短路径推算一个理想到达时间然后加减一个随机偏移生成时间窗。第二种方式更接近真实业务——订单密度高的时候给客户的承诺时间本来就紧张。不同算法测试时使用同一份数据文件、同一组初始种群固定随机种子保证对比公平。4.2 收敛曲线和路径可视化图怎么做Matlab画图是日常操作但画好有技巧。收敛曲线我这里用半对数坐标因为鸡群算法前期收敛快后期慢普通坐标会把后期的微小改进压得看不见半对数坐标能清楚看到后期自适应参数带来的减速收敛过程。路径可视化是更直观的对比方式。我的画法是所有骑手的路径画在一张图上每个骑手用不同颜色取餐点用方框标记送餐点用圆圈标记配送站用五角星标记。这里有一个小技巧边的绘制用plot的LineWidth, 2配合hold on叠加多个骑手路径颜色直接从Matlab的lines色图里循环取不需要自己配一套颜色方案。可视化之后你能直观看到子种群A的解呈现出每一条路径都在时间窗内穿插但整体线条较长的特征子种群B的解呈现出路径短但个别节点的时间窗边缘被卡得很紧的特征这正是双种群分工的外在体现。4.3 与CSO、GA、PSO对比数据会告诉你差距在哪实验配置每种算法独立运行30次记录最好解、最差解、平均解、标准差和运行时间。60个客户规模的结果相对值以最优已知解为基准100大致如下算法平均路径成本最好解最差解标准差时间窗总违反分钟ADPCCSO112.6108.3119.83.245.2CSO128.4122.1136.55.887.6GA121.7118.9129.44.172.3PSO135.2126.7143.96.5101.8表格里的数字需要说明几点。时间窗总违反是全部骑手在所有客户点上的等待延迟之和这个指标往往比路径成本更能直观地区分算法的质量——路径成本可以因为绕路而降低但时间窗违反总和降不下来说明这个解根本不可用。ADPCCSO在这个指标上比CSO降低了接近一半这是双种群分工的功劳。标准差方面30次独立运行ADPCCSO只有3.2说明算法不是偶尔撞上几个好解而是稳定地能找到高质量解这个特性在工程上比单次最优解更重要——你部署一个算法不希望它这次跑出90分下次跑出70分。5. 跑通之后的那些事调参经验与实战避坑5.1 惩罚系数的时间表前期放水后期严打ADPCCSO的自适应能力不是万能的参数还是要手动调。我最想分享的经验是惩罚系数的时间表。初始阶段前30%迭代适应度函数里的时间窗惩罚系数要调小目的给种群足够的试错自由让路径长度优先被优化个体可以大胆地尝试激进路线中期30%到70%把惩罚系数逐步上调到基准值让种群在已发现的好路线上做时间窗修正后期最后30%惩罚系数加到基准值的2到3倍相当于严打期所有解必须满足时间窗不满足的就会被淘汰。为什么不能从头到尾用同一个惩罚系数原因是惩罚系数本质上是一个拉格朗日乘子系数太大时可行解搜索空间被极度压缩前期很容易陷入局部最优系数太小时后期又没有足够的压力去收敛到可行域。这个时间表和上一节的分段二次惩罚不同分段二次惩罚是针对单条路径上的客户等待时间设计的而这里的时间表是针对整体优化过程设计的两层控制叠加起来效果才稳定。我踩过的坑是直接把惩罚系数全程固定结果要么前期多样性崩了要么后期解完全超时不可用。5.2 最容易翻车的地方数据量纲与归一化这个项目里最坑的不是算法而是量纲。客户坐标是0到100的数值时间窗是早上8点到下午2点的时间值我内部换算成分钟480到840订单重量是0.5到5公斤路径长度是几十上百的距离单位——如果直接把这些数值塞进同一个目标函数量纲大的分量会彻底统治适应度函数。真实经历过一次因为时间窗数值远大于坐标数值目标函数里早到等待的那一项天然就比其他项大几十倍适应性函数被时间关联项霸占算法变成了纯粹处理时间窗的时间优化器路径长度根本不在优先序列里最终解绕得非常离谱。解决方法是归一化。我的做法是提前算所有下单客户间距离的统计分布用均值除以所有分量的权重让它们在同一个数量级上比较。另外在解码环节就明确各成本分量的物理单位比如这一项是分钟那一项是百米然后在目标函数里专门做一次权重标定。权重标定的方法是跑一次正交实验在固定解上分别测算跑动距离增加10%、时间违反增加10%、载量超限增加10%时对目标函数的贡献让这些贡献大致相等。5.3 代码性能优化Matlab下如何让算法跑得快外卖配送求解的规模不大但300次迭代、200只鸡、每次迭代全体解码计算量依然可观。三个实战优化手段第一距离矩阵只算一次前面提过这个收益最大第二解码过程尽量用矩阵运算替代for循环比如对一批个体的random-key排序用sortrows一次完成整批排序而不是逐个个体sort第三适应度评估可以并行化Matlab的parfor在这个环节效果明显因为每个个体的解码和评估相互独立不存在共享变量竞争。我用这三个优化把60个客户规模的单次完整运行从8分钟压到了2分钟以内这对需要跑30次统计实验的场景非常重要。另外时间窗早到等待时间的计算有一个向量化的细节第k个客户点的服务完成时间依赖前一个点的完成时间加上行驶时间这个递推关系没法完全向量化但可以用cumsum累积和做大半部分的并行化——先假设路径的等待时间为0用cumsum算出理想到达时间序列再一次性修正超时导致的后续延迟。这个两步法比逐个节点递推要快一个量级。5.4 从论文Demo到真实业务还需要补什么最后说点从算法实验走向实际应用的思考。ADPCCSO在仿真数据上能给出漂亮的结果但真实外卖场景要更残酷订单是动态加入的不是一开局全部给定骑手的位置不是固定站点而是始终在移动路网距离不是欧氏距离而是需要调地图API或路网数据。这些挑战意味着纯粹的静态VRPTW模型只能做决策支持或离线调度参考真正上线还需要增量调度策略——新订单到达时以当前骑手位置为起点把未执行的订单重新跑一次ADPCCSO并把已完成的路径锁定为不可变路段做一个局部的重优化。我个人实际使用中发现ADPCCSO在离线规划阶段提供的是一个高质量初始解集合价值体现在给调度员一个可参考的路线预期和给骑手一个推荐方案同时支持极端情形下比如雷暴天气导致大量订单积压的全局重新排线。建议把目标函数里的服务客户数量权重置为动态可调——单量积压时提高这一项鼓励多送单高峰期即将结束、剩余订单不多时降低这一项让算法更注重时间窗精度。这个动态权重在仿真里对整体运营指标的改善比固定权重又提升了大概7%也是我认为最有价值的后续扩展方向之一。