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。这是因为固定起点城市剩下(n-1)个城市的排列组合顺时针和逆时针是同一条路线所以除以2from math import factorial def tsp_solution_space(n): return factorial(n-1) // 2 print(f5个城市的TSP解空间大小: {tsp_solution_space(5)}) print(f10个城市的TSP解空间大小: {tsp_solution_space(10)})输出结果5个城市的TSP解空间大小: 12 10个城市的TSP解空间大小: 1814402.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(f5个客户2辆车的VRP解空间: {vrp_solution_space(5, 2)}) print(f10个客户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开始mask000...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(i1, n): s distance_matrix[i][depot] distance_matrix[depot][j] - distance_matrix[i][j] savings.append((s, i, j)) # 按节约值降序排序 savings.sort(reverseTrue, keylambda 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 典型应用对照应用场景适用问题类型原因分析电路板钻孔路径TSP单钻头需访问所有孔位后返回起点外卖骑手单配送TSP单个骑手完成所有订单配送物流中心配送VRP多车辆容量约束不同客户需求共享单车调度VRP多调度车载运量限制不均衡需求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子问题先进行客户点聚类按地理位置/需求相似性为每个聚类分配车辆在每个聚类内部求解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_clustersnum_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 routes5.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)开始逐步增加约束条件直到符合实际场景需求。
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。这是因为固定起点城市剩下(n-1)个城市的排列组合顺时针和逆时针是同一条路线所以除以2from math import factorial def tsp_solution_space(n): return factorial(n-1) // 2 print(f5个城市的TSP解空间大小: {tsp_solution_space(5)}) print(f10个城市的TSP解空间大小: {tsp_solution_space(10)})输出结果5个城市的TSP解空间大小: 12 10个城市的TSP解空间大小: 1814402.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(f5个客户2辆车的VRP解空间: {vrp_solution_space(5, 2)}) print(f10个客户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开始mask000...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(i1, n): s distance_matrix[i][depot] distance_matrix[depot][j] - distance_matrix[i][j] savings.append((s, i, j)) # 按节约值降序排序 savings.sort(reverseTrue, keylambda 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 典型应用对照应用场景适用问题类型原因分析电路板钻孔路径TSP单钻头需访问所有孔位后返回起点外卖骑手单配送TSP单个骑手完成所有订单配送物流中心配送VRP多车辆容量约束不同客户需求共享单车调度VRP多调度车载运量限制不均衡需求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子问题先进行客户点聚类按地理位置/需求相似性为每个聚类分配车辆在每个聚类内部求解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_clustersnum_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 routes5.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)开始逐步增加约束条件直到符合实际场景需求。
