欢迎访问上邦|专注企业 AI 数字化转型落地 · 咨询热线 400-667-6771
免费咨询
首页 / 资讯中心 / 技术干货 / 文章详情
技术干货

零售履约路径优化实战:用 OR-Tools 求解带时间窗的车辆路径问题

上邦 AI 工程团队2026-09-20阅读 约 8 分钟
连锁零售补货、即时零售骑手调度、仓到店配送,本质都是车辆路径问题(VRP)。本文用 Google OR-Tools 的 Routing 求解器,从距离矩阵、时间窗与车辆容量出发建模带时间窗的多车路径问题,并给出接入真实地图路况、分区分批求解与生产落地的工程建议。

为什么门店配送要算路径

连锁零售的补货、即时零售的骑手调度、仓到店的配送,本质都是车辆路径问题(VRP)。门店多、时间窗紧、车辆有限时,人工排线既慢又难最优。用求解器把距离、时间窗与载重整合成约束,能在秒级给出成本更低的路线。

用 OR-Tools 建模 VRPTW

Google 的 OR-Tools 提供成熟 Routing 求解器。下面用距离矩阵、时间窗与车辆数建模一个带时间窗的多车路径问题,目标为总行驶距离最小。
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

# 距离矩阵(示意,单位公里),第 0 行为仓库
dist = [[0, 5, 8, 6],
        [5, 0, 4, 7],
        [8, 4, 0, 5],
        [6, 7, 5, 0]]
n = len(dist)
demand = [0, 3, 2, 4]   # 各点货量,仓库为 0
cap = 10                # 单车容量
time_window = [(0, 100), (10, 40), (20, 60), (15, 70)]  # (最早,最晚)

mgr = pywrapcp.RoutingIndexManager(n, 2, 0)  # 2 辆车,仓库为起点
routing = pywrapcp.RoutingModel(mgr)

def d(a, b): return dist[mgr.IndexToNode(a)][mgr.IndexToNode(b)]
tid = routing.RegisterTransitCallback(d)
routing.SetArcCostEvaluatorOfAllVehicles(tid)
routing.AddDimension(tid, 60, 100, True, 'time')

for i in range(1, n):
    routing.AddDisjunction([mgr.NodeToIndex(i)], 100000)  # 允许未访问的惩罚

params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
sol = routing.SolveWithParameters(params)
print('目标值(总距离):', sol.ObjectiveValue() if sol else '无解')
第一步:用门店经纬度调用地图 API 生成真实距离/时间矩阵,替代示意矩阵。第二步:把营业时间、预约时段写成时间窗约束。第三步:加入车载重与最大工时约束。第四步:求解后导出每辆车停靠顺序,回写调度系统并做司机端展示。

工程注意

真实场景往往还有返程、多点取货、骑手技能等约束,可逐步叠加。求解器给出的是较优解而非绝对最优,门店数超过两三百时建议分区分批求解。时间窗别写太死,预留缓冲以应对突发拥堵。
提醒:本示例为最小可运行骨架,生产环境需接入实时路况、订单波次与异常处理,并保留人工干预入口。

参考来源

Vehicle Routing Problem - Google OR-Tools 官方文档。 OR-Tools Routing 求解器说明 - Google Developers。
相关标签:路径优化VRPOR-Tools履约调度零售物流

免费咨询上邦技术顾问

一对一上邦方案顾问对接 · 免费定制企业专属 AI 数字化转型方案

立即获取上邦方案