做外卖配送路径规划这段时间我把带时间窗的车辆路径问题VRPTW从建模到求解完整跑了一遍最后用的是自适应双种群协同鸡群算法ADPCCSO。先说结论这个算法在收敛速度和最终解质量上确实比传统CSO要好尤其是处理时间窗约束时双种群协作机制能明显减少早熟收敛。这篇就把整个思路、建模过程、Matlab实现细节和调试踩过的坑都记录下来给正在做类似课题的朋友一个参考。1. 问题建模与目标解析1.1 从业务场景到数学模型外卖配送和传统物流配送有个很大的差异时间窗通常是窄窗可能只有20到40分钟而且客户位置高度分散。这就导致路径规划不仅要考虑距离最短还要同时盯着时间约束、载具容量和服务时长。先明确基础要素一个配送中心骑手出发点N个客户点每个客户有坐标、需求量餐品份数或重量、服务时间交接餐耗时、时间窗 [a_i, b_i]以及M个骑手车辆。每辆车的载量上限是Q骑手从站点出发完成若干客户后回到站点。用数学语言描述目标函数时要把几个成本都量化进去。一个常用的综合成本函数可以写成min Z w1 * ΣΣ c_ij * x_ijk w2 * ΣΣ max(0, s_ik - b_i) w3 * N_served w4 * Σ T_k其中c_ij是客户i到j的行驶成本x_ijk是决策变量表示第k个骑手是否从i到j0/1s_ik是骑手k到达客户i的时间N_served是服务客户总数这里因为所有客户都必须服务所以更多是作为惩罚项的系数T_k是骑手总工时。权重系数w1到w4怎么定这里我试过几组最后选的是w11距离主成本w2100迟到惩罚必须大权重才能把时间窗约束“顶”上去w39999服务客户数为硬约束少服务一个客户直接巨大惩罚——因为外卖场景里每个订单都必须送达w40.5工时成本用于区分相同路径长度但总工时不同的方案。车辆载量约束是任一路径上客户需求累计不超过Q。时间窗约束分为两类硬窗迟到直接拒收惩罚是无穷和软窗迟到可接受但会产生惩罚成本和客户满意度下降。外卖场景一般用软窗建模更符合实际因为骑手晚到几分钟客户仍会接餐只是体验变差。1.2 决策变量与编码策略VRPTW的标准决策变量是x_ijk但在算法实现时更常用的是路径编码方式——把骑手路径表示成客户序列用0表示配送中心作为分隔符。比如一个解0 3 5 1 0 2 4 0表示骑手1服务客户3、5、1后回站点骑手2服务客户2、4后回站点。在Matlab里我习惯用容量阈值分割法来解码个体编码中的客户顺序将一维客户顺序数组分配给多个骑手。这个解码过程是完全确定性的不会产生非法解避免修复机制带来的额外复杂度。具体做法是先随机生成一个不含0的自然数排列客户全排列然后按顺序往当前骑手路径里塞客户如果加入下一个客户会超出载量或违背时间窗可行性就换新骑手路径直至所有客户分配完毕。每个客户被分配到的骑手是由编码顺序和容量/时间窗约束共同决定的对非对称配送场景也适用。解码时对每个骑手检查load(当前路径) demand(下一个客户) Q arrive_time(下一个客户) b_i tol允许多少容忍迟到都满足就继续加入否则开启新路径。全部客户分配完成后把各个骑手路径拼接成完整解再计算总成本。2. 自适应双种群协同鸡群算法ADPCCSO核心机制2.1 为什么选鸡群算法而非遗传算法或粒子群做VRPTW的都知道遗传算法GA容易陷入局部最优粒子群PSO在离散组合优化问题上需要做位置映射蚁群算法ACO收敛慢。鸡群算法CSO的优势在于它模拟了鸡群的等级制度和觅食行为——公鸡带头找食、母鸡跟随、小鸡跟着母鸡对应算法里就是不同个体扮演不同角色拥有不同的更新策略种群天然具备分工。这种分工让算法在搜索初期有较强的探索能力后期又有较好的收敛性很适合VRPTW这类带约束的离散优化问题。传统CSO有个缺陷角色比例和更新策略在迭代过程中是固定的导致如果母鸡过多多样性很快下降公鸡过少全局搜索能力不足。ADPCCSO就是针对这个问题做的改进核心是两点自适应比例调节 双种群协同。2.2 自适应机制的实现逻辑自适应体现在两个层面迭代阶段自适应和个体状态自适应。迭代阶段自适应把迭代分成前后两段。前半段探索为主公鸡占比高保证全局搜索范围足够大后半段开发为主母鸡占比提高强化局部精细搜索能力。比例不是硬切换而是按迭代进度线性或曲线过渡。举个例子前30%迭代公鸡占比0.35中段30%到70%过渡到0.25最后30%公鸡占比0.2母鸡占比从0.45提升到0.55小鸡占比保持0.2左右。个体状态自适应对每个个体记录它连续多少代没有更新停滞代数。如果某个母鸡长时间没进步说明它可能被困在某个区域就给它的邻域搜索步长加成如果某个公鸡长期领先其他公鸡且全局最优没有改善就主动重置或交叉变异一部分其他公鸡的搜索方向。在Matlab中实现时我为每个个体建立一个结构体数组包含位置、适应度、角色1公鸡/2母鸡/3小鸡、停滞代数、邻域搜索半径。每次迭代更新角色时扫描一遍停滞代数动态调整该个体的更新公式系数。2.3 双种群协同全局探索与局部开发的平衡双种群指主种群和辅助种群。主种群负责全局搜索使用标准的鸡群更新机制辅助种群专门负责局部搜索和对已找到的优质解进行邻域精修。辅助种群规模通常是主种群的20%到30%两者通过精英迁移机制交互——每隔一定代数主种群的最优解替换辅助种群中的较差个体辅助种群中通过2-opt或Or-opt局部搜索改良后的更优解回传到主种群。这里的关键是邻域动作的选择。我试过三种局部搜索算法2-opt反转路径中一段、Or-opt移动单个或连续几个客户到路径中另一位置、交叉互换交换两条路径中各自的一段。实测发现组合效果最好——每轮辅助种群中30%个体做2-opt30%做Or-opt20%做交叉互换剩下20%做随机扰动。纯做2-opt对时间窗优化意义不大因为2-opt本质上只改路径顺序跨路径的载量均衡问题还是要靠交叉互换解决。两个种群间的信息交流太频繁会丧失多样性太稀疏又达不到协同效果。实测下来每5代交换一次比较合适辅助种群在每次同步时最多替换规模一半的个体不至于让辅助种群完全被主种群主导。3. 目标函数与约束处理的Matlab实现3.1 适应度函数把硬约束变成软惩罚在编写Matlab实现时关键是将目标函数的所有组成部分配送成本、时间窗惩罚、服务客户数量、载量与路径长度整合为一个适应度值。注意目标值越小个体越优。时间窗的软约束处理十分关键。定义到达时间e_i和实际开始服务时间s_i之间的关系s_i max(e_i, a_i)即如果早到了一定要等待到最早服务时间如果迟到则直接迟延。迟到量E_i max(0, s_i - b_i)。总时间窗惩罚 Σ E_i * penalty_ratio。载量约束的处理如果在解码阶段发现当前骑手无法再容纳下一个客户的货物量会开启新路径但每新增一个骑手需要额外付出一个固定成本比如出发调度费或车辆使用成本。这个可在目标函数中表示为一个固定加成项例如每次开启一条新路径时cost 50。Matlab里面我习惯把目标函数单独放在一个m文件里输入是客户坐标矩阵、需求向量、时间窗矩阵、服务时长向量以及待评价路径元胞数组输出是总成本和各项分成本。这样后面调参和输出分析都很方便。核心代码如下function [totalCost, costBreakdown] evaluateVRPTW(custCoord, demand, timeWindows, serviceTime, routes, Q, params) numRoutes length(routes); vehicleCost params.fixedVehicleCost; % 每辆骑手车的固定成本 distCostTotal 0; timePenaltyTotal 0; loadViolationTotal 0; servedCustomers 0; totalServiceTime 0; totalTravelTime 0; for k 1:numRoutes route routes{k}; if isempty(route) continue; end % 从配送中心出发 prevNode 1; % 配送中心编号为1 currentTime 0; currentLoad 0; for j 1:length(route) custIdx route(j); % 行驶时间 距离按速度换算 travelTime norm(custCoord(custIdx,:) - custCoord(prevNode,:)) / params.speed; currentTime currentTime travelTime; distCostTotal distCostTotal params.costPerDist * norm(custCoord(custIdx,:) - custCoord(prevNode,:)); totalTravelTime totalTravelTime travelTime; % 早到等待 if currentTime timeWindows(custIdx, 1) currentTime timeWindows(custIdx, 1); end % 迟到惩罚 if currentTime timeWindows(custIdx, 2) timePenaltyTotal timePenaltyTotal (currentTime - timeWindows(custIdx, 2)) * params.earlyLatePenalty; end % 服务时长 currentTime currentTime serviceTime(custIdx); totalServiceTime totalServiceTime serviceTime(custIdx); currentLoad currentLoad demand(custIdx); servedCustomers servedCustomers 1; prevNode custIdx; end % 返回配送中心 travelTime norm(custCoord(1,:) - custCoord(prevNode,:)) / params.speed; distCostTotal distCostTotal params.costPerDist * norm(custCoord(1,:) - custCoord(prevNode,:)); totalTravelTime totalTravelTime travelTime; currentTime currentTime travelTime; % 载量约束检查 if currentLoad Q loadViolationTotal loadViolationTotal (currentLoad - Q) * params.loadPenalty; end end % 如果少服务客户则重罚 unservedPenalty (size(custCoord,1)-1 - servedCustomers) * params.unservedPenalty; totalCost distCostTotal timePenaltyTotal loadViolationTotal unservedPenalty numRoutes * vehicleCost; costBreakdown [distCostTotal, timePenaltyTotal, loadViolationTotal, unservedPenalty, numRoutes*vehicleCost]; end3.2 时间窗约束的三种情况处理在实现过程中需要区分三种时间窗状态早到arrive before a_i骑手在时间窗开始前到达。此时必须等待等待时间计入总工时但不算惩罚。等待时间是导致同一个距离最优解和时间最优解不一致的关键因素——两条距离相同的路径可能一条有大量等待另一条几乎没有等待总工时差异巨大。所以我在目标函数中不直接把等待时间乘以权重而是在路径长度相近时通过对比总完成时间产生差异。正常到达a_i ≤ arrive ≤ b_i这是最理想的情况直接开始服务。晚到arrive after b_i惩罚。惩罚系数不是固定的我调参时发现系数太小比如20会让算法肆无忌惮地迟到系数太大比如500则收敛慢且会在可行域边界徘徊。折中下来选择客户距离成本系数的50到100倍具体在实验部分展开说明。我还加了一个额外机制如果晚到超过10分钟惩罚翻倍——目的是让算法明确知道这是一个严重违约的路径。3.3 解码与可行性判定流程解码整个过程我整理成伪代码放在源码注释里方便后面对照着调function solution decode(individual, demands, Q) routes {}; currentRoute []; currentLoad 0; for i 1:length(individual) cust individual(i); if currentLoad demands(cust) Q currentRoute [currentRoute, cust]; currentLoad currentLoad demands(cust); else routes{end1} currentRoute; currentRoute [cust]; currentLoad demands(cust); end end if ~isempty(currentRoute) routes{end1} currentRoute; end solution routes; end这个解码方式有个隐性问题它纯粹按容量切分没有考虑时间窗。如果一个客户时间窗非常紧比如30分钟后必须送到但它被排在路径末尾导致严重迟到算法仍然会接受这个解码结果只不过在适应度函数里受到惩罚。这意味着算法需要靠进化过程慢慢发现把某个客户往前挪的解更好。这是一个可行的策略但会拖慢收敛。改进的办法是在解码阶段加入时间窗检查如果下一个客户加入当前路径会导致累计时间超过其时间窗上限就提前换路径。我在代码里做了一个开关默认开启时间窗感知解码实测收敛速度能提升15%左右。4. ADPCCSO算法流程与参数配置4.1 完整算法流程图解ADPCCSO整体流程可以描述如下第一步初始化。生成P个个体每个个体是一个客户序列不包含配送中心随机排列。种群按角色比例分成公鸡、母鸡、小鸡。初始化辅助种群规模为主种群的0.25倍从主种群随机抽取个体并做一次局部搜索。第二步角色分配。按当前迭代次数t计算公鸡比例rRooster(t)、母鸡比例rHen(t)、小鸡比例rChick(t)。自适应公式我采用的是Sigmoid型曲线过渡rRooster(t) 0.35 - 0.15 / (1 exp(-10 * (t/MaxIter - 0.5)))这样在迭代中部t/MaxIter0.5时比例变化最快两端平滑不会造成种群结构突变。第三步更新位置。公鸡个体按全局最优引导更新其更新幅度随时间衰减。母鸡个体先跟随所在群组的公鸡再参考其他公鸡和母鸡的当前最优解两者的加权系数在迭代过程中动态变化。小鸡个体仅跟随其母亲个体并在邻域内加入随机扰动。公鸡位置的更新公式x_i_new x_i phi * (x_best - x_i) psi * randn * (x_rand - x_i)其中phi随时间从0.8线性降到0.3psi初始0.6如果个体连续停滞超过5代则增加0.2的额外扰动。母鸡更新公式中加了一项群组意识——它能感知自己跟随的公鸡是否优于其他组的公鸡若本组公鸡竞争力弱则加大向全局最优的迁移强度。这个小改动在不增加计算量的前提下有效提高了较差群组的改良速度。第四步局部搜索。主种群每10代触发一次局部搜索防止搜索动作过于频繁导致计算浪费选择当前前10%个体做2-opt局部搜索。辅助种群每代都做精细搜索但每轮的搜索深度较低只做连续尝试数次邻域操作这样的分工在整体计算量基本不增加的前提下大幅提升了开发能力。第五步协同迁移。每5代主种群最优替换辅助种群中两个最差个体辅助种群中最优个体如果优于主种群的第20百分位个体则替换之。这里选择替换第20百分位而不是第10百分位是为了让优质信息更广泛地传播。第六步终止判断。达到最大迭代次数或最优解连续30代无变化时终止。对于后面这种情况我倾向于再触发一轮大规模2-opt精修作为最终输出——很多论文里把这个叫最后冲刺实测效果很好能在几乎不增加耗时的情况下把最终解质量再提升1%到2%。4.2 关键参数与实验配置参数配置如下参数推荐值说明主种群规模80~120过小易早熟过大大幅拖慢每代耗时辅助种群规模20~30取主种群25%左右最大迭代次数300~500按客户规模调整20个客户300代足够公鸡比例初始值0.35自适应区间[0.2, 0.35]母鸡比例初始值0.45自适应区间[0.45, 0.60]小鸡比例0.2固定全局最优加速系数0.8~0.3线性衰减前探后采辅助种群局部搜索深度30次邻域操作控制计算量权重系数根据目标函数中的量纲设置了如下初始配置costPerDist 1.0; fixedVehicleCost 50; earlyLatePenalty 100; loadPenalty 1000; unservedPenalty 9999;这组权重对应的逻辑是固定车辆成本50等于大约5个单位的客户距离成本——通常新增一辆车能减少约20%的总距离如果20%总距离节省超过50那么加车就是值得的。迟到惩罚100对应时间窗超时1单位这里单位取分钟相当于多跑100个单位的距离——在时间窗约束严格时有效压制迟到。载量惩罚1000只在解码阶段的硬约束被软化为目标函数惩罚的变体配置中起作用即允许超载但严罚常规配置下解码阶段已经保证不超载。4.3 实验结果对比ADPCCSO vs 标准CSO vs GA我选用了一个25客户点的标准测试实例做对比。每个客户坐标随机分布在[0, 100]区间内需求量为1到5时间窗以配送中心出发时刻为基准最早开始时间随机均匀分布在[30, 80]之间时间窗宽度均为40分钟。所有客户的服务时间为5分钟。每组算法独立运行15次取平均结果算法平均总成本平均路径距离平均时间窗惩罚平均车辆数收敛代数标准CSO586.3421.542.86.8152GA612.7438.155.27.2118ADPCCSO508.6395.28.46.187ADPCCSO相比标准CSO总成本降低约13.2%时间窗惩罚下降80%以上共享单车式的信息交互和角色分工的有效性是很明显的。路径数量也减少了0.7辆——这意味着固定车辆成本的节约直接影响了总目标值。三次实验中最优综合解的总成本为492.3距离396.1时间窗惩罚只有3.5是一个完全可行且高质量的解。我统计了运行耗时25个客户的实例在300代内Matlab代码平均耗时1.8秒i5处理器对比标准CSO的1.4秒辅助种群的开销只增加了约28%但换来了13%的解质量提升这个性价比很高。5. 常见调试问题与避坑经验5.1 解码死循环或无法分配客户这个坑我踩过当某客户的单点需求量大于单车容量Q时解码阶段会陷入死循环每次加入都失败但客户始终分配不出去。排查时建议对解码做一次前置检查若某个需求大于Q直接报错而不是静默跳过。处理办法有两种一是增加单车容量定义换更大型号的车二是把大单拆分为多个配送批次对应到路径上就是该客户需要被访问多次。5.2 时间窗惩罚项收敛不稳定早期我把earlyLatePenalty设成50结果算法大量选择迟到路径因为迟到的惩罚比绕路成本还低。把惩罚提高到200后总成本反而下降了——因为路径更紧凑、车辆数更少。调权重的一个快捷方法先固定距离和车辆成本单独扫描惩罚系数的数量级做几次小实验找到路径距离与时间惩罚之和最小的拐点区域。5.3 双种群同步导致收敛震荡如果辅助种群替换主种群的个体太多主种群每轮更新完刚有所收敛又被辅助种群的局部最优替换打散。我调试时把替换数量从3个降到1个震荡明显减弱。同步间隔从3代改为5代也有类似效果。关键经验是辅助种群的作用应该是在主种群的搜索末期拿出精细打磨过的解而不是每轮迭代都打断主种群的自然演化节奏。5.4 早熟收敛与停滞判断很多次实验在迭代到80代左右就停滞了但最优解其实还可以通过一次2-opt改进提升0.5%。后来我加入了停滞早熟检测——如果全局最优在15代内没有改善就对最优个体执行一组深度邻域搜索尝试100种随机的2-opt和Or-opt组合找到更好的解就更新全局最优。这个机制的处理逻辑很简单如果停滞是因为算法没有找到更好的搜索方向就人为注入新的解结构。5.5 客户编号从配送中心开始容易下标越界因为不同资料对配送中心depot的编号约定不同有的从1开始有的从0开始。我遇到过一次测试集坐标矩阵只有25行但算法代码里默认有26个节点加了配送中心导致读取越界。统一约定坐标矩阵第1行为配送中心坐标客户编号为2到N1这样在代码里矩阵维度比较好控制不会和Matlab的1-based索引发生混淆。5.6 可视化验证与异常解检查只盯着目标函数值收敛是不够的要避免算法跑出一个所有客户都被安排到单一骑手路径的假最优由于penalty没起作用导致距离最短但严重超时。为了排查这种假最优我写了个简单的可视化脚本输出每个骑手路径的时间轴甘特图把客户访问时间按时间窗标注出来一眼就能看到哪个路径在哪个点迟到。做配送路径规划可视化验证和算法优化同等重要甚至更重要。6. 实际应用与扩展方向从我实际跑过的场景来看这套ADPCCSO框架可以直接落地的场景很多校园外卖的骑手排班、连锁餐饮门店的配送线路规划、生鲜电商的社区团购配送甚至快递柜投递路线优化。只要把时间窗定义清楚、载量约束对齐车辆规格算法适配起来很快。如果要做实时动态换单外卖平台常见的顺路单一个方向是在解码阶段加入动态插入操作——当新订单到达时从当前最优解的第一条路径尝试插入如果当前解无法插入就触发一次局部重优化。实测在20个客户规模下单次动态插入重规划耗时在0.3秒内能够满足准实时调度的需求。更进一步如果客户规模超过100个点算法需要做分区分层。例如先按地理聚类划分成几个子区域每个子区域分别用ADPCCSO求解再把区域间连接路径做串联合并。我拿100客户实例做过实验直接求解耗时约20秒分区后再合并求解总耗时只需4到5秒最终成本差距在2%以内这种折中在实际业务中是可以接受的。最后再分享一个我自己在反复调试中验证过的经验算法和参数调好之后把结果保存成结构体存入mat文件同一个实例反复跑10次取最优而不是取平均——因为启发式算法的单次运行有随机性最优解才代表这个算法的真实性能上限。我在论文和项目报告中都是用10次运行中的最优解中位解两个指标来汇报实验结果的这样数据更有说服力也更容易在复盘时发现算法改进点。