TSP和VRP到底有啥区别？用Python代码实例带你搞懂优化问题的本质

TSP和VRP到底有啥区别？用Python代码实例带你搞懂优化问题的本质

在物流配送、外卖调度等实际场景中，路径优化算法扮演着关键角色。作为运筹学领域的经典问题，旅行商问题(TSP)和车辆路径问题(VRP)常被相提并论，但两者的核心差异和应用场景却大有不同。本文将通过Python代码实例，带你从算法实现层面深入理解这两种优化问题的本质区别。

1. 基础概念与问题定义

1.1 旅行商问题(TSP)的本质

TSP问题可以形象地描述为：一个旅行商需要访问n个城市，每个城市只能访问一次，最后返回起点，如何规划路线使总行程最短？这看似简单的问题背后，却隐藏着惊人的复杂度。

用数学语言描述，TSP的输入是：

• n个节点的完全图
• 图中每条边(i,j)都有对应的权重c_ij表示距离或成本

约束条件为：

• 每个节点只能被访问一次
• 路径必须形成单个环路(hamiltonian cycle)

目标函数是最小化总路径长度。

# TSP问题的简单数学表示 import numpy as np # 示例：4个城市之间的距离矩阵 distance_matrix = np.array([ [0, 2, 9, 10], [1, 0, 6, 4], [15, 7, 0, 8], [6, 3, 12, 0] ])

1.2 车辆路径问题(VRP)的扩展

VRP是TSP的泛化形式，增加了更多现实约束。典型场景如：某物流公司有k辆卡车，需要服务n个客户点，每辆车有容量限制，如何规划路线使总运输成本最低？

VRP相比TSP新增的关键要素：

• 多车辆(多旅行商)
• 车辆容量约束
• 客户点需求差异
• 可能的其他约束(时间窗、车辆类型等)

# VRP问题的基本数据结构示例 customers = [ {'id': 0, 'demand': 0}, # 仓库 {'id': 1, 'demand': 5}, {'id': 2, 'demand': 3}, {'id': 3, 'demand': 7} ] vehicles = [ {'id': 1, 'capacity': 10}, {'id': 2, 'capacity': 15} ]

关键区别：TSP是单环路优化，VRP是多环路优化且带有资源约束。这种差异导致两者在解空间和算法设计上有根本不同。

2. 解空间复杂度对比

2.1 TSP的解空间特性

对于n个城市的TSP问题，其解空间大小为(n-1)!/2。这是因为：

1. 固定起点城市，剩下(n-1)个城市的排列组合
2. 顺时针和逆时针是同一条路线，所以除以2

from math import factorial def tsp_solution_space(n): return factorial(n-1) // 2 print(f"5个城市的TSP解空间大小: {tsp_solution_space(5)}") print(f"10个城市的TSP解空间大小: {tsp_solution_space(10)}")

输出结果：

5个城市的TSP解空间大小: 12 10个城市的TSP解空间大小: 181440

2.2 VRP的解空间爆炸

VRP的解空间不仅包含城市排列，还涉及车辆分配，复杂度呈指数级增长。考虑最简化的场景：

• n个客户点
• k辆同质车辆
• 每辆车至少服务1个点

解空间下限为：k! * S(n,k)，其中S(n,k)是第二类Stirling数

def vrp_solution_space(n, k): from math import factorial def stirling(n, k): if n == k or k == 1: return 1 return k * stirling(n-1, k) + stirling(n-1, k-1) return factorial(k) * stirling(n, k) print(f"5个客户2辆车的VRP解空间: {vrp_solution_space(5, 2)}") print(f"10个客户3辆车的VRP解空间: {vrp_solution_space(10, 3)}")

输出结果：

5个客户2辆车的VRP解空间: 30 10个客户3辆车的VRP解空间: 55980

实际VRP问题中考虑容量约束后，可行解空间会更小，但搜索难度反而更大，这看似矛盾的现象正是组合优化的特点。

3. 算法实现对比

3.1 TSP的精确解法实现

虽然TSP是NP难问题，但对于小规模实例，我们可以用动态规划精确求解。下面是Held-Karp算法的Python实现：

def held_karp_tsp(dists): n = len(dists) memo = {} # 从起点0出发，经过所有城市最后到达k的最短路径 def dp(mask, k): if (mask, k) in memo: return memo[(mask, k)] if mask == (1 << n) - 1: # 所有城市已访问 return dists[k][0] # 返回起点 res = float('inf') for i in range(n): if not (mask & (1 << i)): # 城市i未被访问 cost = dists[k][i] + dp(mask | (1 << i), i) if cost < res: res = cost memo[(mask, k)] = res return res return dp(1, 0) # 从起点0开始，mask=000...001 # 测试 dist_matrix = [ [0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0] ] print(f"最优路径长度: {held_karp_tsp(dist_matrix)}")

3.2 VRP的启发式解法实现

由于VRP复杂度更高，我们实现一个简单的节约算法(Clarke-Wright算法)：

def clarke_wright_vrp(distance_matrix, demands, vehicle_capacity): n = len(distance_matrix) depot = 0 # 初始解：每个客户单独一辆车 routes = [[depot, i, depot] for i in range(1, n)] # 计算节约值 savings = [] for i in range(1, n): for j in range(i+1, n): s = distance_matrix[i][depot] + distance_matrix[depot][j] - distance_matrix[i][j] savings.append((s, i, j)) # 按节约值降序排序 savings.sort(reverse=True, key=lambda x: x[0]) # 合并路线 for s, i, j in savings: route_i = next((r for r in routes if i in r), None) route_j = next((r for r in routes if j in r), None) if route_i is None or route_j is None or route_i == route_j: continue # 检查容量约束 total_demand = sum(demands[node] for node in route_i if node != depot) + \ sum(demands[node] for node in route_j if node != depot) if total_demand > vehicle_capacity: continue # 合并路线 if route_i[-2] == i and route_j[1] == j: new_route = route_i[:-1] + route_j[1:] elif route_i[1] == i and route_j[-2] == j: new_route = route_j[:-1] + route_i[1:] else: continue routes.remove(route_i) routes.remove(route_j) routes.append(new_route) return routes # 测试 dist_matrix = [ [0, 10, 15, 20, 25], [10, 0, 35, 25, 30], [15, 35, 0, 30, 40], [20, 25, 30, 0, 35], [25, 30, 40, 35, 0] ] demands = [0, 3, 5, 2, 4] capacity = 10 print(f"优化后的路线: {clarke_wright_vrp(dist_matrix, demands, capacity)}")

4. 实际应用场景分析

4.1 典型应用对照

4.2 算法选择策略

针对不同规模问题，推荐算法选择：

TSP问题：

• 精确算法：动态规划(20节点内)
• 启发式算法：模拟退火、遗传算法(50-100节点)
• 商业求解器：Concorde(100+节点)

VRP问题：

• 精确算法：分支定价(极小规模)
• 启发式算法：节约算法、禁忌搜索
• 元启发式：自适应大邻域搜索(ALNS)
• 商业方案：OR-Tools、LKH-3

# 使用OR-Tools求解CVRP的示例代码片段 from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def solve_cvrp_with_ortools(distance_matrix, demands, vehicle_capacities): # 创建路由模型 manager = pywrapcp.RoutingIndexManager(len(distance_matrix), len(vehicle_capacities), 0) routing = pywrapcp.RoutingModel(manager) # 定义距离回调 def distance_callback(from_index, to_index): return distance_matrix[manager.IndexToNode(from_index)][manager.IndexToNode(to_index)] transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 添加容量约束 def demand_callback(from_index): return demands[manager.IndexToNode(from_index)] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null slack vehicle_capacities, True, 'Capacity' ) # 设置搜索参数 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 = 30 # 求解问题 solution = routing.SolveWithParameters(search_parameters) # 解析并返回结果 if solution: return format_solution(manager, routing, solution) return None

实际工程中，VRP问题往往需要结合业务特点进行定制化建模。例如外卖配送需要考虑时间窗约束，物流配送可能需要处理混合车队问题。

5. 进阶讨论：问题转化与扩展

5.1 从TSP到VRP的转化思路

当面对VRP问题时，一种简化思路是将其分解为多个TSP子问题：

1. 先进行客户点聚类（按地理位置/需求相似性）
2. 为每个聚类分配车辆
3. 在每个聚类内部求解TSP问题

from sklearn.cluster import KMeans import numpy as np def cluster_first_tsp_second(coordinates, demands, vehicle_capacity): # 根据需求确定车辆数 total_demand = sum(demands) num_vehicles = int(np.ceil(total_demand / vehicle_capacity)) # 使用K-means聚类 kmeans = KMeans(n_clusters=num_vehicles) clusters = kmeans.fit_predict(coordinates) # 为每个聚类求解TSP routes = [] for cluster_id in range(num_vehicles): cluster_points = [i for i, c in enumerate(clusters) if c == cluster_id] if not cluster_points: continue # 提取子距离矩阵 sub_dist = [[distance_matrix[i][j] for j in cluster_points] for i in cluster_points] # 调用TSP求解器(此处简化为随机排列) tsp_route = np.random.permutation(cluster_points).tolist() routes.append([0] + tsp_route + [0]) # 添加仓库 return routes

5.2 常见变体问题

现代应用中，TSP和VRP发展出多种变体：

TSP家族：

• 带时间窗的TSP(TSPTW)
• 多人TSP(mTSP)
• 概率TSP(PTSP)
• 带利润的TSP(TSP with Profits)

VRP家族：

• 带容量约束的VRP(CVRP)
• 带时间窗的VRP(VRPTW)
• 动态VRP(DVRP)
• 绿色VRP(GVRP)考虑能耗

# VRPTW的简单数据结构示例 customers = [ { 'id': 0, # 仓库 'demand': 0, 'time_window': (0, 1000) }, { 'id': 1, 'demand': 5, 'time_window': (10, 20), 'service_time': 3 } # 更多客户点... ]

在解决实际问题时，选择合适的问题模型比算法本身更重要。一个经验法则是：当不确定时，先从简单模型(TSP)开始，逐步增加约束条件，直到符合实际场景需求。