基于Google OR-Tools实现带日起终约束的跨多天单车辆TSP咨询
单车辆跨多日路径规划(基于OR-Tools)方案评审与优化建议
现有方案核心实现
- 场景适配目标:支持单车辆跨多日连续作业的路径优化,可灵活配置优化覆盖天数、每日专属起止作业位置、每日工作开始与结束时间,覆盖40个待访问点位的调度需求
- 节点矩阵构建逻辑:每新增1个优化日,就在距离矩阵的最前端前置插入当日的起点、终点2个专属节点
- 1天优化场景(对应参数
NUM_DAYS=1):矩阵共42个节点,结构为[第1天起点, 第1天终点, 待访问点位1, 待访问点位2,...待访问点位40] - 2天优化场景(对应参数
NUM_DAYS=2):矩阵共44个节点,结构为[第1天起点, 第1天终点, 第2天起点, 第2天终点, 待访问点位1, 待访问点位2,...待访问点位40] - N天优化场景:矩阵总节点数为
40 + 2*N,按日期顺序前置插入各日起止节点
- 1天优化场景(对应参数
- 已落地的基础能力
- 支持按需丢弃待访问点位换取求解可行性,为每个待访问点位配套设置了丢弃惩罚项
- 强制约束待访问点位必须在其指定的时间窗范围内被访问
- 配套实现节点跳转约束回调、跨日时间重置逻辑、求解参数配置,可稳定复现2天优化场景的求解输出
方案合理性评估
从单车辆小规模调度的落地性角度看,该套实现的基础框架是可行的:
- 前置插入每日起止节点的矩阵构建方式,将“跨日作业的段间隔离”转化为OR-Tools原生支持的路径节点逻辑,没有引入高复杂度的自定义建模,整体实现门槛低、调试成本可控,对于40个待访问点位的规模场景完全可以支撑稳定求解。
同时当前实现存在几处容易导致求解结果不符合预期的共性逻辑漏洞(也是OR-Tools做多日路径规划的常见踩坑点):
- 跨日节点顺序无硬约束:OR-Tools本身并不知道你前置插入的节点代表不同日期的作业段,只会默认按照总距离最短的逻辑跳转节点,当前实现没有强制要求“走完第i天的终点节点后,必须进入第i+1天的起点节点”,求解器很容易输出乱序的节点序列——比如未走完第1天的终点就直接跳到第2天起点,或是走完第2天的作业节点后折返访问第1天的终点,直接破坏多日作业的时间顺序要求。
- 跨日时间累计存在偏差:当前通过自定义回调实现跨日时间重置,在存在早到等待、临时停靠的场景下,很容易把前一日的停靠时间、行驶时间错误累计到次日的工作时长计算中,导致求解得到的每日作业时长和实际规则不匹配。
- 点位分配边界模糊:所有待访问点位和每日起止节点同处于可自由跳转的节点池,没有从建模层面约束“待访问点位的访问时刻必须落在当日的工作时间范围内”,求解器可能为了最小化行驶距离,把本该分配到当日的点位跨日调度,不符合实际作业排班预期。
可落地的优化方向
- 补全跨日节点顺序硬约束:在路由模型中为相邻日的起止节点添加强制先后访问约束——即第i天的终点节点,必须在第i+1天的起点节点之前被访问,从建模层面杜绝节点跨日乱序的问题,减少回调逻辑的判断压力。
- 替换自定义跨日时间重置逻辑:将手动实现的时间重置回调,适配为OR-Tools原生的时间维度分段累计规则——每经过一个当日终点节点,就清零累计的行驶时间、已消耗工作时长,直接对应“跨日时段不累计工作时间”的实际规则,降低自定义逻辑带来的计算偏差。
- 细化每日时间边界配置:为每个日起止节点绑定对应的工作时间窗(即当日的工作开始、结束时间),让求解器在计算时间维度时,自动把夜间停靠等非作业时段的时长从有效工作时间里扣除,不需要手动计算跨日的时间差。
- 优化点位丢弃的管控规则:在现有丢弃惩罚项的基础上,补充最高丢弃量约束,即限制求解过程最多丢弃固定数量的高优先级点位,避免求解器为了快速凑出可行解,无意义丢弃高价值的待访问点位。
内容的提问来源于stack exchange,提问作者Josh Kautz
相关产品推荐
相关产品推荐

