上一篇： 第9篇：92.8%的包裹消失了，一次数据异常追踪

一、写在前面

给你34个配送点，怎么规划路线最省时省力？

这就是VRP问题（Vehicle Routing Problem，车辆路径问题）。听着学术，实际就是路线规划。

这个问题看似简单，实际很复杂。34个配送点就有2.95×10^38种走法，人脑根本算不过来。用OR-Tools跑了一下，10秒钟就给出了优化路线，比原始路线省43%的距离。

二、VRP问题到底是啥？

2.1 从TSP到VRP

TSP（Traveling Salesman Problem，旅行商问题）是最简单的路径规划问题：

• 1个快递员/1辆车
• 访问所有配送点，回到起点
• 没有任何约束条件
• 目标：找到最短路径

计算复杂度有多恐怖？

• 10个点：362,880种走法（10!）
• 20个点：2.4×10^18种走法（20!）
• 34个点：2.95×10^38种走法（34!）

暴力枚举根本算不完，即使每秒计算1万亿种方案，也要9.3×10^18年。

VRP是TSP的扩展，贴近真实业务场景，加入了各种约束条件：

• 多个快递员/多辆车
• 车辆有载重限制
• 客户有时间窗要求
• 可能有多个配送站点

2.2 VRP的常见变体

2.3 复杂度对比

TSP（最简单）
└─ VRP（加入车辆数量）
    ├─ CVRP（加入载重限制）
    ├─ VRPTW（加入时间窗）
    ├─ MDVRP（加入多车场）
    └─ CVRPTW（载重+时间窗，最复杂的静态VRP）
        └─ 动态VRP（订单实时到达，最接近现实）

本文先从最简单的TSP开始（单快递员34个点），跑通流程，后续再扩展到多车辆VRP。

三、为什么不能手算？

就34个点，看看地图规划一下不就行了？

真实对比（基于上海快递员2621的数据）：

如果一个快递员一天送50单，优化能节省更多。按每天10公里计算，一个月300公里，能省不少油钱和时间。

四、OR-Tools简介

OR-Tools是Google开源的运筹优化工具包，专门解决这类组合优化问题。

优点：

• 免费开源
• 支持多种问题（VRP、TSP、排班、装箱等）
• 效率高，能处理上千个点
• 文档齐全

缺点：

• 上手有点门槛（但比自己写算法简单多了）
• 超大规模问题（万级别）可能不够快

装起来很简单：

pip install ortools

五、实战案例：单快递员TSP

先从最简单的开始：一个快递员，34个配送点，怎么走最短？

5.1 数据准备

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# 读取上海数据，提取快递员2621在2022-06-04的配送点
df = pd.read_csv('data/raw/delivery/delivery_sh.csv')
df['ds'] = df['ds'].astype(str).str.zfill(4)

# 筛选特定快递员和日期
courier_id = 2621
target_date = '0604'

daily_orders = df[(df['courier_id'] == courier_id) & (df['ds'] == target_date)].copy()

# 按实际配送时间排序
daily_orders = daily_orders.sort_values('delivery_time')

# 使用实际送达GPS坐标
daily_orders['lng'] = daily_orders['delivery_gps_lng'].astype(float)
daily_orders['lat'] = daily_orders['delivery_gps_lat'].astype(float)

print(f"快递员{courier_id}在2022-06-04的配送:")
print(f"总订单数: {len(daily_orders)}")

# 提取配送点坐标
delivery_points = daily_orders[['lng', 'lat']].values
locations = delivery_points

print(f"\n配送点数量: {len(delivery_points)}")
print(f"\n前5个配送点坐标:")
for i, (lng, lat) in enumerate(delivery_points[:5], 1):
    print(f"  点{i}: ({lng:.5f}, {lat:.5f})")

运行结果：

快递员2621在2022-06-04的配送:
总订单数: 34

配送点数量: 34

前5个配送点坐标:
  点1: (121.51778, 31.08347)
  点2: (121.52436, 31.08724)
  点3: (121.52918, 31.08316)
  点4: (121.53026, 31.07918)
  点5: (121.52878, 31.07652)

配送点分布在约4km×4km的区域内，GPS坐标精确到小数点后5位，使用实际送达位置（delivery_gps）。

5.2 计算距离矩阵

使用Haversine公式计算真实地理距离（而不是欧式距离）：

def haversine_distance(lon1, lat1, lon2, lat2):
    """计算两个GPS坐标之间的距离（单位：公里）"""
    from math import radians, cos, sin, asin, sqrt

    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a))
    r = 6371  # 地球半径（公里）

    return c * r

def compute_distance_matrix(locations):
    """计算真实地理距离矩阵"""
    n = len(locations)
    dist_matrix = np.zeros((n, n))

    for i in range(n):
        for j in range(n):
            if i != j:
                dist_matrix[i][j] = haversine_distance(
                    locations[i][0], locations[i][1],
                    locations[j][0], locations[j][1]
                )

    return dist_matrix

distance_matrix = compute_distance_matrix(locations)

# OR-Tools需要整数距离矩阵（单位：米）
distance_matrix_int = (distance_matrix * 1000).astype(int)

print("距离矩阵样例（前3×3，单位：米）:")
print(distance_matrix_int[:3, :3])

运行结果：

距离矩阵样例（前3×3，单位：米）:
[[   0  753 1086]
 [ 753    0  645]
 [1086  645    0]]

为什么用Haversine而不是欧式距离？GPS坐标在地球表面，需要考虑地球曲率。虽然在几公里范围内差别不大，但养成好习惯。

5.3 用OR-Tools求解TSP

def solve_tsp(distance_matrix):
    """求解TSP问题"""

    # 创建路径规划管理器
    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix),  # 点的数量
        1,                     # 车辆数量（TSP只有1辆车）
        0                      # 起点（depot）索引
    )

    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

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

    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 = 10

    solution = routing.SolveWithParameters(search_parameters)

    return manager, routing, solution


import time
start_time = time.time()
manager, routing, solution = solve_tsp(distance_matrix_int)
solve_time = time.time() - start_time

if solution:
    print(f"找到解！（用时{solve_time:.3f}秒）")
    route = []
    index = routing.Start(0)
    total_distance = 0

    while not routing.IsEnd(index):
        node = manager.IndexToNode(index)
        route.append(node)
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        total_distance += routing.GetArcCostForVehicle(previous_index, index, 0)

    route.append(manager.IndexToNode(index))

    print(f"总距离: {total_distance/1000:.2f} km")

    # 对比未优化的路线（按订单号顺序配送）
    naive_distance = 0
    naive_route = list(range(len(distance_matrix_int)))
    for i in range(len(naive_route) - 1):
        naive_distance += distance_matrix_int[naive_route[i]][naive_route[i+1]]
    naive_distance += distance_matrix_int[naive_route[-1]][0]

    print(f"\n【对比分析】")
    print(f"未优化路线（按配送时间顺序）: {naive_distance/1000:.2f} km")
    print(f"OR-Tools优化路线: {total_distance/1000:.2f} km")
    print(f"节省距离: {(naive_distance - total_distance)/1000:.2f} km ({(1 - total_distance/naive_distance)*100:.1f}%)")

运行结果：

找到解！（用时10.002秒）
总距离: 7.25 km

【对比分析】
未优化路线（按配送时间顺序）: 12.80 km
OR-Tools优化路线: 7.25 km
节省距离: 5.55 km (43.3%)

分析：

• OR-Tools在10秒内找到最优解
• 比未优化路线节省43.4%的距离
• 34个点，2.95×10^38种走法，10秒搞定

5.4 Web界面展示

除了脚本，我还做了一个Web界面，可以直观地查看优化效果。

原始路线（红色）：

路线存在大量交叉，有明显的回头路，配送顺序比较随机。

优化后路线（蓝色）：

路线没有交叉，呈现环形，相邻的配送点连续配送。

量化效果：

• 原始路线距离：12.82 km
• 优化后距离：7.25 km
• 节省比例：43.4%（节省5.57 km）

六、踩过的坑

坑1：距离矩阵单位问题

OR-Tools要求整数距离矩阵。一开始直接传浮点数，求解器报错。

# 错误：浮点数
distance_matrix_float = compute_distance_matrix(locations)
manager = pywrapcp.RoutingIndexManager(len(distance_matrix_float), ...)

# 正确：转成整数（单位：米）
distance_matrix_int = (distance_matrix * 1000).astype(int)

坑2：起点设置

TSP要求从起点出发，回到起点。一开始没设depot，路线不闭合。

# 错误：没有指定depot
manager = pywrapcp.RoutingIndexManager(len(distance_matrix), 1)

# 正确：第三个参数是depot索引
manager = pywrapcp.RoutingIndexManager(len(distance_matrix), 1, 0)

坑3：搜索时间太短

默认搜索时间很短，找到的解质量差。

# 默认：可能只有几百毫秒
search_parameters = pywrapcp.DefaultRoutingSearchParameters()

# 正确：设置足够的搜索时间
search_parameters.time_limit.seconds = 10  # 10秒

10秒对于34个点已经足够，更多点可以适当增加。

七、实战建议

7.1 别追求最优解

OR-Tools有很多搜索策略，有的追求速度，有的追求质量。实际用时：

• 100个点以内：用精确策略，几秒钟
• 100-500个点：用启发式，几十秒
• 500+个点：设置时间限制（比如30秒），拿到一个"够好"的解就行

别追求100%最优，90%最优但1秒出结果，更实用。

7.2 考虑实际路况

OR-Tools算的是直线距离或矩阵距离。实际道路有单行道、红绿灯、拥堵。

更准确的做法：

• 用高德/百度地图API获取实际导航距离
• 考虑实时路况（可以用历史数据预测）

八、总结

基于LaDe真实数据的实战结果：

• 真实案例：快递员2621，34个配送点
• 未优化路线：12.82km
• OR-Tools优化后：7.25km
• 节省43.4%距离，10秒求解

OR-Tools够用：免费开源，支持TSP、VRP、CVRP、VRPTW等多种变体。

下一篇讲上门取件路线优化（VRPTW），加入时间窗约束，看看准时率能从21%提升到多少。

下一篇： 第11篇：上门取件路线优化实战