引言：为什么数学能帮外卖小哥？
想象一下，你是一位外卖小哥，手机上同时接到了5个订单，分别来自不同的餐厅和客户。你需要规划一条路线，既要取餐又要送餐，还要考虑交通状况、时间限制和订单优先级。如果凭经验随意选择路线，可能会绕远路、错过最佳配送时间，甚至导致客户投诉。
数学优化，特别是旅行商问题（TSP）和车辆路径问题（VRP）的变种，能帮助外卖小哥系统性地找到最优路线。这些算法不是科幻，而是实际应用在美团、饿了么等平台的智能调度系统中。本文将深入浅出地解释如何用数学方法优化送餐路线，并提供可操作的步骤和代码示例。
一、核心数学模型：从旅行商问题到外卖场景
1.1 旅行商问题（TSP）简介
旅行商问题是一个经典的组合优化问题：给定一系列城市和每对城市之间的距离，求访问每个城市恰好一次并返回起点的最短路径。外卖送餐可以看作TSP的变种：
- 城市 = 餐厅或客户位置
- 距离 = 实际路程（考虑交通、红绿灯等）
- 约束 = 订单时间窗口、取餐/送餐顺序
1.2 外卖场景的扩展：车辆路径问题（VRP）
外卖配送更接近带时间窗的车辆路径问题（VRPTW）：
- 多订单：同时处理多个订单
- 时间窗：每个订单有期望送达时间
- 取送顺序：必须先取餐再送餐
示例：假设外卖小哥在位置A，有3个订单：
- 订单1：餐厅B（取餐），客户C（送餐），时间窗12:00-12:30
- 订单2：餐厅D（取餐），客户E（送餐），时间窗12:15-12:45
- 订单3：餐厅F（取餐），客户G（送餐），时间窗12:30-13:00
目标：找到一条最短路径，满足所有时间窗约束。
二、数学优化方法详解
2.1 距离计算：欧氏距离 vs 实际距离
在城市中，两点间的直线距离（欧氏距离）与实际路程差异很大。我们需要更精确的距离模型。
Python示例：计算两点间的实际距离
import math
import requests # 用于调用地图API
def euclidean_distance(lat1, lon1, lat2, lon2):
"""计算欧氏距离（近似）"""
R = 6371 # 地球半径（公里）
dlat = math.radians(lat2 - lat1)
dlon = math.radians(lon2 - lon1)
a = (math.sin(dlat/2) * math.sin(dlat/2) +
math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) *
math.sin(dlon/2) * math.sin(dlon/2))
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
return R * c
def get_real_distance(api_key, origin, destination):
"""调用地图API获取实际距离（示例使用高德地图）"""
url = "https://restapi.amap.com/v3/direction/driving"
params = {
'key': api_key,
'origin': f"{origin[0]},{origin[1]}",
'destination': f"{destination[0]},{destination[1]}"
}
response = requests.get(url, params=params)
data = response.json()
if data['status'] == '1' and data['route']['paths']:
return float(data['route']['paths'][0]['distance']) / 1000 # 转换为公里
return None
# 示例：计算北京某两点间的实际距离
api_key = "YOUR_AMAP_KEY" # 替换为实际API密钥
origin = (39.9042, 116.4074) # 天安门
destination = (39.9897, 116.3972) # 故宫
real_dist = get_real_distance(api_key, origin, destination)
print(f"实际距离：{real_dist} 公里")
说明：在实际应用中，外卖平台会集成地图API（如高德、百度、Google Maps）获取实时路况和距离。对于离线计算，可以使用历史数据训练距离预测模型。
2.2 优化算法选择
由于TSP是NP-hard问题，对于大量订单（>10个），精确求解不可行。常用启发式算法：
2.2.1 贪心算法（Nearest Neighbor）
原理：从当前位置出发，每次选择最近的未访问点。 优点：简单快速 缺点：可能陷入局部最优
Python示例：贪心算法求解TSP
import numpy as np
def greedy_tsp(distance_matrix):
"""贪心算法求解TSP"""
n = len(distance_matrix)
visited = [False] * n
path = [0] # 假设从点0出发
visited[0] = True
for _ in range(n-1):
current = path[-1]
# 找到最近的未访问点
min_dist = float('inf')
next_city = -1
for i in range(n):
if not visited[i] and distance_matrix[current][i] < min_dist:
min_dist = distance_matrix[current][i]
next_city = i
path.append(next_city)
visited[next_city] = True
# 返回起点
path.append(0)
return path
# 示例：5个点的距离矩阵
dist_matrix = np.array([
[0, 10, 15, 20, 25],
[10, 0, 35, 25, 30],
[15, 35, 0, 30, 50],
[20, 25, 30, 0, 15],
[25, 30, 50, 15, 0]
])
path = greedy_tsp(dist_matrix)
print(f"贪心算法路径：{path}")
2.2.2 模拟退火（Simulated Annealing）
原理：模拟物理退火过程，允许暂时接受较差解以跳出局部最优。 优点：能获得较好解 缺点：参数调整复杂
Python示例：模拟退火求解TSP
import random
import math
def simulated_annealing_tsp(distance_matrix, initial_temp=1000, cooling_rate=0.95, iterations=10000):
"""模拟退火算法求解TSP"""
n = len(distance_matrix)
current_path = list(range(n))
random.shuffle(current_path)
current_cost = calculate_path_cost(current_path, distance_matrix)
best_path = current_path.copy()
best_cost = current_cost
temp = initial_temp
for i in range(iterations):
# 生成新路径（交换两个城市）
new_path = current_path.copy()
idx1, idx2 = random.sample(range(n), 2)
new_path[idx1], new_path[idx2] = new_path[idx2], new_path[idx1]
new_cost = calculate_path_cost(new_path, distance_matrix)
# 接受准则
delta = new_cost - current_cost
if delta < 0 or random.random() < math.exp(-delta / temp):
current_path = new_path
current_cost = new_cost
if current_cost < best_cost:
best_path = current_path.copy()
best_cost = current_cost
# 降温
temp *= cooling_rate
return best_path, best_cost
def calculate_path_cost(path, distance_matrix):
"""计算路径总距离"""
cost = 0
for i in range(len(path)-1):
cost += distance_matrix[path[i]][path[i+1]]
return cost
# 使用相同的距离矩阵
best_path, best_cost = simulated_annealing_tsp(dist_matrix)
print(f"模拟退火算法路径：{best_path}, 总距离：{best_cost}")
2.2.3 遗传算法（Genetic Algorithm）
原理：模拟生物进化，通过选择、交叉、变异操作优化种群。 优点：适合复杂约束 缺点：计算量大
Python示例：遗传算法求解TSP
import random
class GeneticAlgorithmTSP:
def __init__(self, distance_matrix, population_size=50, generations=100, mutation_rate=0.1):
self.distance_matrix = distance_matrix
self.n = len(distance_matrix)
self.population_size = population_size
self.generations = generations
self.mutation_rate = mutation_rate
def create_individual(self):
"""创建个体（随机路径）"""
individual = list(range(self.n))
random.shuffle(individual)
return individual
def fitness(self, individual):
"""适应度函数（距离越短越好）"""
cost = 0
for i in range(self.n-1):
cost += self.distance_matrix[individual[i]][individual[i+1]]
return 1 / (cost + 1) # 避免除零
def selection(self, population):
"""轮盘赌选择"""
fitnesses = [self.fitness(ind) for ind in population]
total_fitness = sum(fitnesses)
probs = [f/total_fitness for f in fitnesses]
selected = []
for _ in range(self.population_size):
r = random.random()
cumulative = 0
for i, prob in enumerate(probs):
cumulative += prob
if r <= cumulative:
selected.append(population[i])
break
return selected
def crossover(self, parent1, parent2):
"""顺序交叉（OX）"""
size = len(parent1)
start, end = sorted(random.sample(range(size), 2))
child = [-1] * size
child[start:end+1] = parent1[start:end+1]
# 填充剩余基因
pointer = (end + 1) % size
for gene in parent2:
if gene not in child:
child[pointer] = gene
pointer = (pointer + 1) % size
return child
def mutate(self, individual):
"""交换变异"""
if random.random() < self.mutation_rate:
idx1, idx2 = random.sample(range(self.n), 2)
individual[idx1], individual[idx2] = individual[idx2], individual[idx1]
return individual
def run(self):
"""运行遗传算法"""
# 初始化种群
population = [self.create_individual() for _ in range(self.population_size)]
best_individual = None
best_fitness = 0
for gen in range(self.generations):
# 选择
selected = self.selection(population)
# 交叉和变异
new_population = []
for i in range(0, len(selected), 2):
if i+1 < len(selected):
child1 = self.crossover(selected[i], selected[i+1])
child2 = self.crossover(selected[i+1], selected[i])
new_population.append(self.mutate(child1))
new_population.append(self.mutate(child2))
# 保留精英
population = new_population[:self.population_size]
# 更新最佳个体
for ind in population:
fit = self.fitness(ind)
if fit > best_fitness:
best_fitness = fit
best_individual = ind
return best_individual, 1/best_fitness - 1 # 返回路径和总距离
# 使用相同的距离矩阵
ga = GeneticAlgorithmTSP(dist_matrix, population_size=20, generations=50)
best_path, best_cost = ga.run()
print(f"遗传算法路径：{best_path}, 总距离：{best_cost}")
2.3 外卖场景的特殊约束处理
2.3.1 时间窗约束
每个订单有取餐时间窗和送餐时间窗。我们需要确保路径满足这些约束。
Python示例：带时间窗的路径验证
def check_time_window(path, locations, time_windows, travel_speed=30):
"""
验证路径是否满足时间窗约束
:param path: 路径顺序（点的索引）
:param locations: 位置坐标列表
:param time_windows: 每个点的时间窗 [(start, end), ...]
:param travel_speed: 平均速度（km/h）
:return: 是否满足，到达时间列表
"""
current_time = 0 # 从时间0开始
arrival_times = []
for i in range(len(path)-1):
# 计算两点间距离
idx1, idx2 = path[i], path[i+1]
dist = euclidean_distance(*locations[idx1], *locations[idx2])
# 计算旅行时间（小时）
travel_time = dist / travel_speed
# 到达下一个点的时间
current_time += travel_time
# 检查时间窗
start, end = time_windows[idx2]
if current_time < start:
current_time = start # 等待到时间窗开始
elif current_time > end:
return False, [] # 超出时间窗
arrival_times.append(current_time)
return True, arrival_times
# 示例：3个点的时间窗
locations = [(0, 0), (5, 5), (10, 10)] # 位置坐标
time_windows = [(0, 1), (0.5, 1.5), (1, 2)] # 时间窗（小时）
path = [0, 1, 2]
is_valid, times = check_time_window(path, locations, time_windows)
print(f"路径是否有效：{is_valid}")
print(f"到达时间：{times}")
2.3.2 取送顺序约束
外卖必须先取餐再送餐。这可以通过分层图模型解决：
- 将每个订单拆分为两个节点：取餐点（餐厅）和送餐点（客户）
- 添加约束：取餐点必须在送餐点之前访问
Python示例：处理取送顺序
def create_delivery_graph(orders):
"""
创建外卖配送图
:param orders: 订单列表，每个订单包含餐厅和客户位置
:return: 节点列表和距离矩阵
"""
nodes = []
node_info = [] # 存储节点类型和订单ID
for order_id, order in enumerate(orders):
# 取餐点（餐厅）
nodes.append(order['restaurant'])
node_info.append({'type': 'pickup', 'order_id': order_id})
# 送餐点（客户）
nodes.append(order['customer'])
node_info.append({'type': 'delivery', 'order_id': order_id})
# 计算距离矩阵
n = len(nodes)
dist_matrix = np.zeros((n, n))
for i in range(n):
for j in range(n):
if i != j:
dist_matrix[i][j] = euclidean_distance(*nodes[i], *nodes[j])
return nodes, node_info, dist_matrix
def validate_pickup_delivery_sequence(path, node_info):
"""
验证取送顺序：每个订单的取餐点必须在送餐点之前
"""
order_status = {} # 记录每个订单的状态
for node_idx in path:
node = node_info[node_idx]
order_id = node['order_id']
if node['type'] == 'pickup':
if order_id in order_status:
return False # 重复取餐
order_status[order_id] = 'picked'
elif node['type'] == 'delivery':
if order_id not in order_status or order_status[order_id] != 'picked':
return False # 未取餐先送餐
order_status[order_id] = 'delivered'
# 检查所有订单是否完成
return len(order_status) == len(set([o['order_id'] for o in node_info]))
# 示例：2个订单
orders = [
{'restaurant': (0, 0), 'customer': (5, 5)},
{'restaurant': (10, 10), 'customer': (15, 15)}
]
nodes, node_info, dist_matrix = create_delivery_graph(orders)
print(f"节点数：{len(nodes)}")
print(f"节点信息：{node_info}")
# 测试路径：先取订单1，再取订单2，再送订单1，再送订单2
path = [0, 2, 1, 3] # 节点索引
is_valid = validate_pickup_delivery_sequence(path, node_info)
print(f"取送顺序是否有效：{is_valid}")
三、实际应用案例：美团智能调度系统
3.1 系统架构
美团外卖的智能调度系统（”超脑”）采用分层优化：
- 订单分配层：将订单分配给骑手
- 路径规划层：为每个骑手规划最优路线
- 实时调整层：根据交通状况动态调整
3.2 算法实现
美团使用混合整数规划（MIP）和启发式算法结合：
- 对小规模问题（<10单）使用精确算法
- 对大规模问题使用蚁群算法和遗传算法
Python示例：简化版美团调度算法
class MeituanScheduler:
def __init__(self, riders, orders, distance_matrix):
self.riders = riders # 骑手列表
self.orders = orders # 订单列表
self.distance_matrix = distance_matrix # 距离矩阵
def assign_orders(self):
"""订单分配（简化版）"""
# 按骑手当前位置和订单位置分配
assignments = {}
for rider in self.riders:
rider_id = rider['id']
rider_pos = rider['position']
# 找到最近的未分配订单
min_dist = float('inf')
best_order = None
for order in self.orders:
if not order.get('assigned'):
# 计算骑手到餐厅的距离
dist = euclidean_distance(*rider_pos, *order['restaurant'])
if dist < min_dist:
min_dist = dist
best_order = order
if best_order:
best_order['assigned'] = True
assignments[rider_id] = best_order['id']
return assignments
def plan_route(self, rider_id, assigned_orders):
"""为骑手规划路线"""
# 获取骑手位置
rider_pos = self.riders[rider_id]['position']
# 构建路径点：骑手位置 -> 取餐点 -> 送餐点
path_points = [rider_pos]
for order_id in assigned_orders:
order = next(o for o in self.orders if o['id'] == order_id)
path_points.append(order['restaurant']) # 取餐
path_points.append(order['customer']) # 送餐
# 计算距离矩阵
n = len(path_points)
dist_matrix = np.zeros((n, n))
for i in range(n):
for j in range(n):
if i != j:
dist_matrix[i][j] = euclidean_distance(*path_points[i], *path_points[j])
# 使用模拟退火求解最优路径
best_path, best_cost = simulated_annealing_tsp(dist_matrix)
# 将路径索引转换为实际位置
actual_path = [path_points[i] for i in best_path]
return actual_path, best_cost
# 示例：美团调度
riders = [
{'id': 1, 'position': (0, 0)},
{'id': 2, 'position': (10, 10)}
]
orders = [
{'id': 101, 'restaurant': (2, 2), 'customer': (5, 5)},
{'id': 102, 'restaurant': (8, 8), 'customer': (12, 12)},
{'id': 103, 'restaurant': (15, 15), 'customer': (20, 20)}
]
scheduler = MeituanScheduler(riders, orders, None)
assignments = scheduler.assign_orders()
print(f"订单分配：{assignments}")
# 为骑手1规划路线
rider1_orders = [order_id for rid, order_id in assignments.items() if rid == 1]
if rider1_orders:
route, cost = scheduler.plan_route(1, rider1_orders)
print(f"骑手1路线：{route}")
print(f"总距离：{cost}")
四、实战技巧：外卖小哥的数学优化指南
4.1 数据收集与准备
- 记录历史数据：记录每次送餐的路线、时间、距离
- 建立个人数据库：使用Excel或简单数据库记录餐厅和客户位置
- 使用地图工具：高德、百度地图的API可以获取精确距离
4.2 简化算法选择
对于个人使用，不需要复杂算法，可以尝试：
- 贪心算法：每次选择最近的点
- 2-opt局部搜索：优化现有路径
- 聚类算法：将订单按区域分组
Python示例：2-opt优化
def two_opt(path, distance_matrix):
"""2-opt局部搜索优化路径"""
improved = True
best_path = path.copy()
best_cost = calculate_path_cost(path, distance_matrix)
while improved:
improved = False
for i in range(1, len(path)-2):
for j in range(i+1, len(path)-1):
# 交换边
new_path = best_path.copy()
new_path[i:j+1] = best_path[j:i-1:-1]
new_cost = calculate_path_cost(new_path, distance_matrix)
if new_cost < best_cost:
best_path = new_path
best_cost = new_cost
improved = True
break
if improved:
break
return best_path, best_cost
# 使用之前的距离矩阵
initial_path = [0, 1, 2, 3, 4, 0]
optimized_path, optimized_cost = two_opt(initial_path, dist_matrix)
print(f"2-opt优化前：{initial_path}, 成本：{calculate_path_cost(initial_path, dist_matrix)}")
print(f"2-opt优化后：{optimized_path}, 成本：{optimized_cost}")
4.3 考虑实际因素
- 交通状况：高峰期避开主干道
- 电梯等待：高层建筑增加时间成本
- 天气因素：雨天增加配送时间
- 订单优先级：紧急订单优先处理
Python示例：加权距离矩阵
def create_weighted_distance_matrix(locations, weights):
"""
创建加权距离矩阵
:param weights: 每个点的权重（如电梯等待时间）
"""
n = len(locations)
dist_matrix = np.zeros((n, n))
for i in range(n):
for j in range(n):
if i != j:
base_dist = euclidean_distance(*locations[i], *locations[j])
# 添加权重（如电梯等待时间）
weighted_dist = base_dist + weights[j] # 到达点j的额外时间
dist_matrix[i][j] = weighted_dist
return dist_matrix
# 示例：考虑电梯等待时间
locations = [(0, 0), (5, 5), (10, 10)]
weights = [0, 2, 5] # 点1无电梯，点2等2分钟，点3等5分钟
weighted_matrix = create_weighted_distance_matrix(locations, weights)
print("加权距离矩阵：")
print(weighted_matrix)
五、进阶：机器学习预测配送时间
5.1 特征工程
预测配送时间需要考虑：
- 距离
- 时间（小时、星期几）
- 天气
- 交通状况
- 餐厅类型
5.2 模型训练
使用历史数据训练回归模型。
Python示例：简单线性回归预测
import pandas as pd
from sklearn.linear_model import LinearRegression
from sklearn.model_selection import train_test_split
# 模拟历史数据
data = {
'distance': [1.2, 2.5, 3.1, 4.2, 5.0, 1.8, 2.9, 3.5],
'hour': [12, 13, 18, 19, 20, 12, 13, 18],
'weather': [0, 0, 1, 1, 1, 0, 0, 1], # 0:晴, 1:雨
'traffic': [1, 2, 3, 3, 3, 1, 2, 3], # 1:畅通, 2:一般, 3:拥堵
'delivery_time': [15, 25, 35, 45, 50, 18, 28, 38] # 分钟
}
df = pd.DataFrame(data)
# 分割数据
X = df[['distance', 'hour', 'weather', 'traffic']]
y = df['delivery_time']
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 训练模型
model = LinearRegression()
model.fit(X_train, y_train)
# 预测
predictions = model.predict(X_test)
print(f"预测时间：{predictions}")
print(f"实际时间：{y_test.values}")
# 特征重要性
print(f"系数：{model.coef_}")
print(f"截距：{model.intercept_}")
5.3 集成到路径优化
将预测时间作为距离矩阵的权重。
def predict_delivery_time(features, model):
"""预测配送时间"""
return model.predict([features])[0]
# 示例：为每个订单预测时间
orders_features = [
[1.5, 12, 0, 1], # 距离1.5km，12点，晴天，畅通
[2.0, 18, 1, 3], # 距离2.0km，18点，雨天，拥堵
]
predicted_times = [predict_delivery_time(f, model) for f in orders_features]
print(f"预测配送时间：{predicted_times} 分钟")
六、工具与资源推荐
6.1 开源工具
- OR-Tools（Google）：强大的运筹学工具包
pip install ortools - Pyomo：数学优化建模语言
- NetworkX：图论和网络分析
6.2 地图API
- 高德地图API：国内最准确
- 百度地图API：覆盖广
- Google Maps API：国际使用
6.3 学习资源
- 书籍：《运筹学导论》、《算法导论》
- 课程：Coursera “Discrete Optimization”
- 论文：搜索 “VRPTW”、”Delivery Routing”
七、总结与展望
数学优化能显著提升外卖配送效率。通过：
- 建立准确的距离模型
- 选择合适的优化算法
- 考虑实际约束条件
- 结合机器学习预测
外卖小哥可以系统性地优化路线，节省时间和体力，提高收入。
未来趋势：
- 实时动态优化：结合实时交通数据
- 多骑手协同：考虑骑手间的协作
- 个性化推荐：根据骑手习惯优化
行动建议：
- 从简单贪心算法开始
- 记录数据并分析
- 逐步引入更复杂算法
- 使用现有工具（如OR-Tools）加速开发
通过数学优化，每位外卖小哥都能成为”路线规划专家”，在激烈的竞争中脱颖而出。