带时间窗的多工地卡车调度是物流排班领域里非常典型的一类问题。我自己最早接触它是帮一个做商品混凝土运输的朋友优化搅拌车排班一个搅拌站要给五六个在建工地供料每个工地都有自己严格的浇筑时间窗去早了要等去晚了整个浇筑班组要停工等着混凝土一趟调度出错可能连锁影响几个工地的施工节奏。当时手工排班全靠调度员经验遇到高峰期手忙脚乱我才开始尝试用粒子群算法PSO做自动排班。现在回头总结这套 MATLAB 代码的设计思路和踩坑记录分享给大家。这个项目的核心是把“哪辆车、什么时候、去哪个工地、拉哪一车料”这个听起来像天书的问题变成一套可在 MATLAB 里运行的优化算法。它能解决人工排班三个痛点多工地时间窗重叠时的车辆分配冲突、早晚高峰的道路耗时波动、以及突发插单时的快速重排。适合正在学习智能优化算法的学生、做运输调度系统开发的工程师以及想用算法代替 Excel 排班的实际业务人员参考。全文会按“问题建模—算法原理—代码实现—调参实战—坑点排查”的顺序展开代码思路全部可复用。1. 问题场景与分析为什么工地调度比普通配送更头疼1.1 带时间窗的卡车多工地调度到底是什么先说清楚问题边界。一个带时间窗的多工地调度场景通常包含这些要素若干台卡车运力、若干个工地需求点、每个工地有服务时间窗口比如早上 8 点到下午 5 点以及一个或几个出发场站搅拌站、料场、土方场。每一趟运输任务有一个固定流程卡车从场站出发满载货物开到工地到达后可能排队、卸货、返回场站然后再执行下一趟任务。调度要做的事情就是决定哪辆车执行哪趟任务、任务按什么顺序执行、车几点出发。这类问题的难点和普通快递配送有本质区别。快递配送面对的是离散的包裹取送时间窗相对宽松而工地调度里的时间窗往往是硬约束或重惩罚约束——混凝土搅拌车提前到达工地泵送设备没准备好整车料在罐体里等迟到到达工地工人等着甚至这一罐料超过初凝时间整罐报废。更麻烦的是多个工地的时间窗可能相互重叠运力有限车辆要不停切换在运与在运之间周转。这本质上是带时间窗的车辆路径规划问题VRPTW的一个变体加上了多工地的并发约束。1.2 约束条件和目标函数怎么定在设计算法之前先把数学上的“规矩”立清楚。整个调度方案可以看成一组任务的排序与分配。每个工地有若干个需求车次每车次可以被任意车辆执行但同一车辆同一时刻只能执行一个车次且车次执行的顺序就是车辆的空间移动顺序。约束条件常见有这几类时间窗约束车辆到达工地的时间不能早于最早可服务时间也不能晚于最晚开始服务时间。车辆容量约束本文场景下每车次满载运输容量约束简化为车辆可执行任务总时长上限比如司机工时不能超 8 小时。连续性约束车回到场站、装料后再出发去下一个工地相邻任务之间存在时间和空间上的转移代价。场站资源约束同一时刻场站可发车数量、装料工位数量有限这在很多文献里被忽略但实际运行中影响很大。调度目标一般分几个层次。最优先的是把硬性约束全部满足尤其是时间窗的迟到惩罚其次是最小化总行驶成本、总等待时间或者总完工时间。在代码里我会把目标函数定义为加权和fitness w1 * 总行驶里程 w2 * 总等待时间 w3 * 总迟到惩罚 w4 * 车辆使用数量权重 w1、w2、w3、w4 可以根据业务侧重点调整如果燃油成本敏感就加大 w1如果工地投诉迟到多就加大 w3如果老板关心车的利用率就加大 w4。这种加权目标函数的好处是方便调试先跑通再调权。1.3 为什么选择粒子群算法而不是遗传算法车队规模上 10、任务量上 50 以内的调度问题粒子群算法是一个非常好的选择。我自己拿遗传算法GA和粒子群算法PSO在这个场景下反复对比过GA 的交叉变异算子设计在排列编码上很麻烦——调换顺序、防重复、保持可行性是个大坑而 PSO 的粒子位置直接就是连续数值配合随机键排序编码实现起来几乎零障碍。更重要的是 PSO 收敛速度确实快。同样是 200 次迭代PSO 大概到 80 次就已经能摸到不错的解GA 还在 120 次左右挣扎。做工程项目不是说算法越高级越好而是在有限代码量和有限调参周期里用最容易上手、最不容易出 bug 的方案解决问题。PSO 对初值的鲁棒性好编码简单可视化调试直观非常契合这类中型调度问题。2. 粒子群算法原理与调度问题的适配性拆解2.1 PSO 机制快速回顾粒子群算法的灵感来自鸟群觅食每个粒子就是一只鸟它在解空间里飞知道自己目前找到过的最好位置也知道整个群体找到过的最好位置然后靠着这两条信息调整自己的速度和方向。数学上粒子的速度更新公式是v v * w c1 * rand * (pbest - x) c2 * rand * (gbest - x); x x v;其中 w 是惯性权重c1 是个体学习因子c2 是全局学习因子rand 是 0 到 1 之间的随机数。这么设计的巧妙之处在于w 控制粒子多大程度继承之前的运动惯性c1 让粒子回头往自己发现过的优秀区域搜索c2 则让粒子朝全局最优方向靠拢。三个参数配合既保证了探索能力又保证了开发能力。2.2 调度问题怎么编码成粒子随机键排序法这是整个算法设计的灵魂。调度方案不是一个个独立数值而是“先执行任务 A、再执行任务 B、最后执行任务 C”的排列顺序。PSO 的位置更新公式是连续域的不能直接输出排列。业界常用做法是随机键编码Random Key。比如现在有 6 个任务粒子位置是一个 6 维向量每个分量是 0 到 1 之间的连续实数。要对这位粒子解码得到任务顺序就把这 6 个实数从小到大排序排序后的索引就是任务的执行顺序。举例粒子位置是 [0.72, 0.11, 0.85, 0.37, 0.55, 0.28]从小到大排序后得到顺序索引 [2, 6, 4, 5, 1, 3]即先执行任务 2再执行任务 6再任务 4、5、1、3。PSO 更新位置后哪怕是数值微小的变化也会导致排序映射改变但整体保持稳定。随机键编码最大的好处是让算法始终在连续空间里工作不需要处理离散取整、越界修复这些麻烦事。而且这种编码天然满足“可行性”后续做车辆插空分配时即使某个解在业务上不可行编码层面也不会出界。2.3 车速、卸料时间、时间窗这些现实数据怎么进入模型算法不落地就没有价值。对真实运行数据我的处理方式是构造一个“任务列表”taskList的表格每一行代表一个车次需求字段至少有任务ID、所属工地ID、货物量或车次类型、最早开始服务时间窗起点、最晚开始服务时间窗终点、建议卸货时长。车辆列表vehicleList也很关键每辆车有车辆ID、初始位置场站ID、最大工时限制、平均行驶速度。工地坐标siteCoord用于计算两两之间的欧氏距离或实际道路距离。计算两点间行驶耗时直接用距离除以速度。但在真实城市道路场景下早晚高峰车速差异很大我的做法是把一天划分成几个时段每个时段给不同的平均速度比如早高峰 20 km/h、平峰 35 km/h、晚高峰 22 km/h。虽然这会增加一点实现的复杂度但实测下来调度结果比恒定车速更贴近真实。时间窗有两种处理模式。严格硬约束下任何早到或晚到都视为不可行解软时间窗下给早到等待时间和迟到时间施加高额惩罚让算法在“稍微迟到但成本更低”和“绕路准时”之间做权衡。工程实践中推荐用软时间窗起步——硬约束下粒子群很容易在迭代初期全部掉进不可行区域导致搜索停滞软时间窗可以引导粒子逐步爬出惩罚区域边收敛边满足约束。3. MATLAB 代码实现的四个关键环节3.1 数据初始化与参数设定先定义全局数据结构。任务和车辆的初始化直接决定了后面所有函数的输入格式我的习惯是把所有输入数据打包成结构体 data一步到位传进适应度函数。% data 结构体示例 data.taskList [ 1, 1, 8.0, 10.0, 0.75; % 任务ID, 工地ID, 最早开始, 最晚开始, 卸货时长 2, 2, 9.0, 11.5, 0.50; 3, 1, 13.0, 15.0, 0.75; % ... 按需扩展 ]; data.siteCoord [ 0, 0; % 场站坐标 5, 12; % 工地1坐标 8, 3; % 工地2坐标 % ... ]; data.vehicleNum 10; % 可用车辆数 data.vehicleSpeed 32; % 平均车速 km/h data.wLoad 0.2; % 装卸排队附加时间系数PSO 参数初始化建议先抄一套基准值再根据问题规模微调nParticle 60; % 粒子数 nIter 300; % 迭代次数 wStart 0.9; % 惯性权重起点 wEnd 0.4; % 惯性权重终点 c1 1.8; % 个体学习因子 c2 1.8; % 全局学习因子 nTask size(data.taskList, 1);建议把惯性权重设计成随迭代线性递减前期 0.9 保证全局探索后期 0.4 加强局部精细搜索。这是 PSO 调参里最有效的单一改动之一。3.2 适应度函数核心也不复杂但得把惩罚算明白粒子位置向量通过随机键排序解码后得到任务执行顺序。适应度函数需要把这个顺序进一步分配到具体车辆上再模拟整个调度过程计算各项成本与惩罚。车辆分配我采用最简单的贪心插空策略按任务顺序逐个取任务对每辆车尝试将任务插入到该车当前任务序列的末尾计算插入后的新增成本选新增成本最小的车辆执行该任务。这种策略虽然贪心但在 PSO 迭代框架下配合全局搜索效果已经相当不错。function totalCost fitnessFunc(particle, data) order decodeParticle(particle, data.nTask); % 随机键解码得到任务顺序 % 贪心分配车辆模拟调度流程 for t 1:length(order) taskID order(t); bestVehicle -1; bestCost inf; for v 1:data.vehicleNum [newCost, feasible] tryInsertTask(v, taskID, schedule, data); if feasible newCost bestCost bestCost newCost; bestVehicle v; end end if bestVehicle -1 % 如果所有车辆都无法插入给出极高惩罚 totalCost 1e8; return; end schedule(bestVehicle).taskList(end1) taskID; end totalCost computeCost(schedule, data); end时间窗惩罚计算我建议用分段线性函数。设 arrive 是到达工地时刻readyTime 是最早可服务时间dueTime 是最晚开始服务时间则% 早到惩罚提前到只能等待不产生服务但占用车辆和司机时间 earlyPenalty max(0, readyTime - arrive) * wEarly; % 迟到惩罚每迟到一分钟损失很大 latePenalty max(0, arrive - dueTime) * wLate;wEarly 设置成较小值比如每 0.1 小时罚 10wLate 设置成较大值比如每 0.1 小时罚 200模拟“等一会儿没事迟到工地要爆炸”的业务逻辑。这个不对称惩罚设计非常贴合工地调度的真实痛点。3.3 PSO 主循环与收敛策略主循环部分很常规但有两个细节值得注意一是边界处理二是个体最优与全局最优的更新时机。for iter 1:nIter w wStart - (wStart - wEnd) * iter / nIter; for i 1:nParticle % 速度更新边界限幅 v(i,:) w * v(i,:) ... c1 * rand(1, nTask) .* (pbest(i,:) - x(i,:)) ... c2 * rand(1, nTask) .* (gbest - x(i,:)); v(i,:) max(min(v(i,:), vMax), -vMax); x(i,:) x(i,:) v(i,:); % 重新映射到 [0,1]保持随机键含义 x(i,:) (x(i,:) - min(x(i,:))) / (max(x(i,:)) - min(x(i,:)) eps); % 适应度评估与更新 cost fitnessFunc(x(i,:), data); if cost pbestVal(i) pbestVal(i) cost; pbest(i,:) x(i,:); end if pbestVal(i) gbestVal gbestVal pbestVal(i); gbest pbest(i,:); end end record(iter) gbestVal; endvMax 一般设为 0.2 到 0.5防止粒子速度过大导致位置剧烈跳变。归一化映射是随机键编码特别需要的一步——速度更新后位置虽然理论上仍围绕 0 到 1 波动但累积误差可能让位置漂移出界每次迭代做一次 min-max 缩放把位置拉回区间既保持了相对顺序又避免越界。3.4 结果输出与甘特图可视化排班结果如果只给一个最优解数值业务方根本没法用。可视化输出对实际落地极其重要我是这么处理的第一输出每辆车的任务队列车辆编号、按顺序执行的每个任务、每个任务的预计出发时间、到达时间、开始服务时间、结束服务时间。第二绘制调度甘特图。横轴是时间轴纵轴是车辆编号每一行用色块表示该车各时间段执行的任务。色块颜色按工地分组一眼就能看出车辆周转情况和工地覆盖情况。第三统计关键指标总行驶里程、总等待时间、迟到次数、最大完工时间、车辆数。figure; hold on; for v 1:vehicleNum for k 1:length(schedule(v).taskList) tStart schedule(v).startTime(k); tEnd schedule(v).endTime(k); rectangle(Position, [tStart, v-1, tEnd-tStart, 0.8], ... FaceColor, colorMap(siteID(k), :)); end end xlabel(时间/h); ylabel(车辆编号);这一段代码是调试验收时最有用的工具。算法跑完肉眼看一眼甘特图就知道车辆是不是在频繁空驶、任务是不是全挤在某个时间段、时间窗是否合理。比任何指标都直观。4. 实战调参与运行效果分析4.1 基准参数怎么设定一组可以直接抄的配置在自己的项目里我做过一组比较系统的参数对比实验问题规模是 4 个工地区域、18 个任务、10 台车。结论可以作为基准参考参数名推荐范围我的基准值说明粒子数40-10060太小容易早熟太大耗时剧增迭代次数200-500300看收敛曲线平了即可停惯性权重起始0.8-0.950.9兼顾初期探索惯性权重结束0.3-0.450.4后期收敛精细个体学习因子 c11.5-2.01.8自身记忆强度全局学习因子 c21.5-2.01.8社会信息强度最大速度 vMax0.2-0.50.3防止震荡早到惩罚 wEarly10-5020小值容忍等待迟到惩罚 wLate150-400300大值接近硬约束这个表可以直接抄作业。初跑不理想时先别急着改算法结构优先检查这些参数范围是否超出合理区间。4.2 三组真实场景测试记录场景 A全部工地时间窗错开早上 8 点到下午 6 点每 2 小时一个窗口。这种情况约束最松算法大概迭代 80 次就稳定总行驶里程比人工排班低 12% 左右最大完工时间提前 1.5 小时。场景 B三个工地时间窗高度重叠都挤在上午 9 点到 11 点。这是最崩溃的场景。约束收紧后粒子群初期大量粒子都落在惩罚区适应度值高达几万。但迭代到 150 次后逐渐找到可行方案最终通过让部分车辆提前出场、部分任务分配到下午时段软时间窗允许实现了 90% 任务窗口内完成10% 的小延误控制在了 15 分钟以内。场景 C加入动态突发事件比如某个工地临时加急 3 个任务。我做了两阶段重调度先把新增任务加入任务列表再以现有最优解为初始粒子不是在随机初始化的粒子群里重头跑这样重排速度快了三倍迭代 100 次以内就能给出新排班方案。这个“热启动”技巧在业务落地时价值极大。4.3 调参避坑经验迭代曲线没平之前不急着下结论调参最怕的是看一次运行结果就乱动参数。我的习惯是固定随机数种子跑 5 次看收敛曲线和最好解的分布。如果 5 次结果差异大说明粒子数或迭代次数不够算法还在随机乱撞如果 5 次结果接近但都明显差于期望那大概率是适应度函数或者惩罚权重设置不合理而不是 PSO 参数问题。另外惩罚系数不是越大越好。wLate 设到 1000 时粒子会为了不迟到而疯狂绕路、增加行驶距离适应度里时间窗惩罚变成了绝对主导距离成本被忽略。惩罚系数的正确设置标准是“迟到的成本”恰好和“为规避迟到而多跑的那段路成本”处于同一数量级让算法有真正的权衡空间。5. 常见问题排查与算法改进空间5.1 粒子群调度代码最容易踩的五个坑现象原因解决方案所有粒子适应度都是 1e8算法完全不动车辆序列插入逻辑写错或时间窗硬约束下初始解全不可行改用软时间窗在 tryInsertTask 里放开部分约束收敛曲线后期还在剧烈跳动vMax 设置过大粒子反复横跳vMax 降到 0.2 附近检查惯性权重是否线性递减结果里出现车辆闲置、任务全堆给一辆车贪心插入策略过强缺少车辆均衡机制在车辆使用数量项加惩罚 w4抑制车辆闲置早到等待时间巨大出发时间固定过晚车辆太早到工地等待出发时间作为决策变量一起编码和任务顺序联合优化跑一次一个结果完全不可复现MATLAB 随机数种子没固定开头加 rng(42)多次运行取最优先说第五个坑我在项目调试早期差点被它害惨。明明是同一份代码上午跑出来的排班结果和下午跑的完全不一样业务方直接质疑算法的稳定性。后来我把随机数种子固定再用多次独立运行取最优的方式上报结果才真正让算法结果可复现、可交付。5.2 车辆插空分配的性能瓶颈当任务数超过 30、车辆数超过 15 时每次适应度评估里的 tryInsertTask 会变成主要耗时点。原因是它对每辆车按顺序遍历所有时间槽并尝试插入复杂度是 O(车辆数 × 任务数)而整个 PSO 要调用几千上万次适应度函数。优化方向有两个一是用邻接表记录每辆车已分配任务的时间区间插入时只需检查相邻任务之间的空隙避免全量扫描二是对粒子做快速不可行剪枝如果任务的时间窗本身和车辆当前序列冲突明显直接跳过该车辆不进入精细成本计算。实测优化后运行时间缩短约 40%在大规模问题上效果更明显。5.3 算法可以往哪些方向扩展这个代码框架的扩展性很好几个升级方向都很适合后续文章深入。多场站协同把单个场站扩展成多个场站车辆可以选择从不同场站装料编码里增加场站分配维度。动态重调度实时接收新任务结合滚动时域优化框架每 5 分钟或 10 分钟触发一次重排。混合算法PSO 容易出现早熟可以尝试“PSO 局部搜索”的二阶段混合策略全局搜索后用 2-opt 或 Or-opt 做局部路径优化往往能再提升 5%-10%。多目标优化把“最小总成本”和“最小最大完工时间”拆成两个目标用多目标 PSO 输出 Pareto 前沿让业务方自己选平衡点。我个人最近的实践体会是这套基于 PSO 的调度框架真正的价值不在算法本身多精深而在编码方式和适应度函数能不能把业务约束翻译得足够准确。调度的本质是权衡时间窗是硬的还是软的、车辆是稀缺的还是充足的、迟到损失大还是空驶损失大——把这些想清楚再用粒子群这个简洁稳健的优化器去搜索结果自然差不了。如果你正卡在某个调度排班优化项目上不妨先照着这个代码框架把“随机键编码 软时间窗惩罚 贪心车辆插入”这三板斧跑通再去想更高级的算法。跑通一次你就能看见粒子群在调度问题上的真正威力了。