物流优化 OR-Tools：车辆路径与调度问题求解

FreeGuideOnline 最新 2026-06-24

物流优化实战：用 OR-Tools 破解车辆路径与调度难题

在物流配送、网约车调度、冷链运输等场景中，如何在满足约束的前提下规划最优路线，直接决定成本与效率。谷歌的 OR-Tools 是一套开源运筹优化利器，其内置的路径求解引擎能帮你快速求解经典的车辆路径问题及其变种。本教程将从零带你搭建求解环境，用最少代码实现带时间窗、容量限制的路径优化，让你的物流系统拥有“智能大脑”。

什么是车辆路径问题？

车辆路径问题的核心是：给定一个仓库和若干客户点，由一支车队负责服务所有客户，每个客户只能被访问一次，每辆车从仓库出发并最终返回，在满足车辆容量、时间窗等限制下，使得总行驶距离或总成本最小。

OR-Tools 提供了专门的 Routing 库，它内置了大量搜索策略与元启发式算法，你只需要定义节点、车辆、约束和成本，即可快速获得高质量可行解，非常适合工程化落地。

第一步：环境搭建与 API 初识

本教程基于 Python，请确保安装 OR-Tools：

pip install ortools

导入核心模块：

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

pywrapcp 是 OR-Tools 的 C++ 内核的 Python 封装，性能强劲。我们还需要 routing_enums_pb2 来配置搜索策略。

第二步：创建最基本的数据模型

一个完整的 VRP 通常需要以下数据：

距离或时间矩阵：表示任意两点间移动的成本
客户需求量：用于容量约束
车辆容量
时间窗：允许到达客户的最早和最晚时间
仓库索引

我们先从一个简单的有容量限制的 VRP 开始，暂不考虑时间窗。假设5个客户，1个仓库（索引为0）。

def create_data_model():
    data = {}
    # 距离矩阵（单位：公里），对称矩阵
    data["distance_matrix"] = [
        [0, 5, 8, 6, 7],
        [5, 0, 4, 3, 6],
        [8, 4, 0, 5, 3],
        [6, 3, 5, 0, 4],
        [7, 6, 3, 4, 0],
    ]
    # 每个客户的需求量（索引0为仓库，需求为0）
    data["demands"] = [0, 2, 1, 2, 1]
    # 车辆容量
    data["vehicle_capacities"] = [4, 4]  # 两辆车，容量均为4
    # 车辆数量
    data["num_vehicles"] = 2
    # 仓库索引
    data["depot"] = 0
    return data

实际项目中距离矩阵可通过地图 API 获取真实路网距离，OR-Tools 对此没有限制。

第三步：初始化路由模型与回调函数

OR-Tools 采用“回调”机制定义移动成本。距离（或时间）回调必须是模型能调用的函数。

data = create_data_model()
manager = pywrapcp.RoutingIndexManager(
    len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)
routing = pywrapcp.RoutingModel(manager)

RoutingIndexManager 负责将用户索引（0,1,2...）转换为求解器内部的索引，同时自动处理多车辆和仓库。

定义距离回调：

def distance_callback(from_index, to_index):
    # 从内部索引转换回用户索引
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data["distance_matrix"][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

第四步：添加容量约束

容量约束需要两个回调：需求量函数和车辆容量设置。

def demand_callback(from_index):
    from_node = manager.IndexToNode(from_index)
    return data["demands"][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_callback_index,
    0,                # 空载时无缓冲
    data["vehicle_capacities"],  # 车辆容量列表
    True,             # 容量在路径开始时重置（设为0）
    "Capacity"
)

AddDimensionWithVehicleCapacity 会自动为每辆车累加需求量，并确保整条路线载重始终不超过容量。

第五步：设置搜索策略并求解

OR-Tools 支持多种搜索策略，常用的 PATH_CHEAPEST_ARC 启动后跟 GUIDED_LOCAL_SEARCH 进行局部搜索优化。

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
)
search_parameters.time_limit.seconds = 5  # 设置求解时间上限

solution = routing.SolveWithParameters(search_parameters)

第六步：解析并输出解决方案

def print_solution(data, manager, routing, solution):
    total_distance = 0
    total_load = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"车辆 {vehicle_id} 的路线:\n"
        route_distance = 0
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data["demands"][node_index]
            plan_output += f" {node_index} ->"
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        # 回到仓库的节点
        node_index = manager.IndexToNode(index)
        plan_output += f" {node_index}\n"
        plan_output += f"行驶距离: {route_distance} km\n"
        plan_output += f"载重: {route_load}\n"
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print(f"总距离: {total_distance} km, 总载重: {total_load}")

if solution:
    print_solution(data, manager, routing, solution)

输出示例：

车辆 0 的路线:
 0 -> 1 -> 3 -> 0
行驶距离: 14 km
载重: 4
车辆 1 的路线:
 0 -> 2 -> 4 -> 0
行驶距离: 14 km
载重: 2
总距离: 28 km, 总载重: 6

进阶一：加入时间窗约束

时间窗约束需要在数据模型中加入 time_windows 矩阵，并为每个节点定义 (最早到达时间, 最晚到达时间)，服务时间也可定义。

扩展数据模型：

# 时间窗：单位分钟，仓库时间窗可设得很宽
data["time_windows"] = [
    (0, 480),    # 仓库
    (60, 120),   # 客户1
    (30, 90),    # 客户2
    (180, 240),  # 客户3
    (0, 180)     # 客户4
]
data["service_time"] = [0, 10, 10, 10, 10]  # 每个地点的服务时间

需要使用带时间维度的回调：

def time_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    # 行驶时间 = 距离矩阵值（假设速度 1 min/km）
    return data["distance_matrix"][from_node][to_node] + data["service_time"][from_node]

time_callback_index = routing.RegisterTransitCallback(time_callback)
routing.AddDimension(
    time_callback_index,
    60,         # 允许的松弛时间
    480,        # 车辆最大工作时间（可设为一天时长）
    False,      # 时间并非必须从 0 开始（以仓库时间窗为准）
    "Time"
)
time_dimension = routing.GetDimensionOrDie("Time")

# 为每个位置设置时间窗
for location_idx, time_window in enumerate(data["time_windows"]):
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

# 仓库时间窗约束（对于每辆车的起始和结束节点）
for vehicle_id in range(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetRange(
        data["time_windows"][0][0],
        data["time_windows"][0][1]
    )

此时求解器会同时满足容量和时间窗限制。你可以很自然地组合多种约束。

进阶二：处理异构车队与回程载货

现实中的车队可能包含不同容量、不同固定成本、不同速度的车辆。OR-Tools 允许设置每辆车的容量和固定费用，通过 SetFixedCostOfVehicle 影响成本。

回程载货（即先送货后取货）可通过添加“取货-送货”配对约束实现，使用 AddPickupAndDelivery 方法。

进阶三：自定义成本与软时间窗

除了行驶距离，还可以将违反时间窗的惩罚作为软约束加入总成本，这样在无法全部遵守时依然能得到一个可行的妥协解。

# 时间维度允许超出时间窗，添加违反惩罚
time_dimension.SetSpanCostCoefficientForAllVehicles(10)  # 每分钟迟到惩罚10

性能调优技巧

缩小搜索空间：合理设置 time_limit，优先使用 GUIDED_LOCAL_SEARCH 或 TABU_SEARCH。
使用初始解：由人工经验或上历史最优解启动，可显著加速收敛。
减少距离矩阵规模：通过聚类或地理围栏先划分区域。
并行求解：OR-Tools 支持多线程搜索，在参数中设置 search_parameters.num_search_workers = 4。

总结：从原型到生产的路

通过本教程，你已掌握：

OR-Tools 路由引擎的核心架构（Manager + Routing + Dimension）
容量约束和时间窗的实现
多车辆异构问题的基本配置
如何解析输出并集成到业务系统

下一步建议将模型封装为微服务，通过 REST API 接收订单坐标与时间窗，实时返回最优配送序列。OR-Tools 的 C++/Java/.NET 版本也能无缝嵌入到更高性能的场景中。

开始动手调参，你会发现那几条简短的路线背后，藏着运筹学的优雅与工程的力量。