旅行商问题是车辆路径问题(VRP)的特例,又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。
问题原型：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。当城市特别多的时候，求解极其复杂，由于计算机模型及算法的进步，现阶段求解方法较多。粒子算法、遗传算法、蚁群算法、神经网络等启发式方法在运筹优化求解方面都可取得较好的结果。
1.暴力法求解
暴力法：城市顺序全排列，找到最短距离。7个城市的距离矩阵如下表，现需要从第一个城市开始，最后回到第一个城市，其可能的组合有6！=720个。若城市再增加4个，其组合为10！=3628800种组合，暴力求解速度极慢，只能尝试用其他办。
暴力求解需要把720条路径都计算出来，找到最短的路径即可。
import itertools import pandas as pd data1=pd.read_excel('distancecity.xlsx') datanew=[0]*7 for i in range(0,7): datanew[i]=list(data1.iloc[i,1:8]) distance_matrix=datanew#导入数据 array = [i for i in range(1,len(distance_matrix)+1)] pailie=list(itertools.permutations(array)) pailie_back=[list(i)+list(i)[:1] for i in pailie] #开始和结束都是一个点 pailie_back=pailie_back[:720] #取前720个，前720个为开始和结束都为第一个点的路径 def distance_all(q): m=0 for i in range(len(q)-1): m+=distance_matrix[q[i]-1][q[i+1]-1] return q,m min_distance=min([list(map(distance_all,pailie_back))[i][1] for i in range(len(pailie_back))])#搜索最小的距离路径 for i,j in map(distance_all,pailie_back): if j==min_distance and i[0]==1: print('路径：'+str([q-1 for q in i]),'总路程:'+str(j))#找到最小距离对应的路径
2.ortools求解
谷歌ortools已经搭建好了各类运输问题求解的轮子，我们只需要对数据及参数进行调整即可求解，非常方便。
from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): data = {} data['distance_matrix'] = datanew # 导入刚才用到的距离矩阵 data['num_vehicles'] = 1#车辆个数，暂时设置成一辆车 data['depot'] = 0 #起点，0是第一个为起点 return data def print_solution(manager, routing, solution): """Prints solution on console.""" print('Objective: {} miles'.format(solution.ObjectiveValue())) index = routing.Start(0) plan_output = 'Route for vehicle 0:\n' route_distance = 0 while not routing.IsEnd(index): plan_output += ' {} ->'.format(manager.IndexToNode(index)) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle(previous_index, index, 0) plan_output += ' {}\n'.format(manager.IndexToNode(index)) print(plan_output) plan_output += 'Route distance: {}miles\n'.format(route_distance) def main(): """Entry point of the program.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. 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) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(manager, routing, solution) if __name__ == '__main__': main()
与暴力法相比，ortools速度要快很多。
3.遗传算法
遗传算法是非常经典的启发式算法，在运筹优化、经济预测、投资组合等方面都有较广泛的使用。
遗传算法其原理是：借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。
对于本例，先随机生成母体，由母体进行交叉、变异形成新的一代，新的一代根据其适应度（总距离）择优选择繁殖进化，最终迭代多次选择较优解。本例可用scikit-opt的算法包直接求解。
4.其他求解办法
本例除了用以上方法，还可以用经典的求解器Cplex、Gurobi等，这些求解器可进行大型案例的求解。因这两个求解器需学术申请或在校学生才可获得使用权限，若商业使用收费较高，暂无法在此展示。
