旅行商问题的一个优化包
tsp的Python项目详细描述
tspy：旅行商问题的一个优化包。
tspy包提供了一个python框架，用于研究著名的Traveling Salesman Problem（tsp）。在这个包中，可以处理tsp的特定实例。默认情况下包括近似方法和下界。包的结构使创建和包含您自己的方法变得容易。
安装
可以使用pip安装tspy包：
pip install tspy
如何使用tspy
创建实例
要创建TSP实例，请使用：
fromtspyimportTSPtsp=TSP()
目前，数据可以通过两种方式提供给实例：给它nxn距离矩阵d或者，在欧几里得tsp的情况下，给它一个nxp数据矩阵x和一个距离函数。
# Using the distance matrixtsp.read_mat(D)# Using the data matrix and a distance functiontsp.read_data(X,dist)< H3>计算近似解< EH3>
模块^ {CD1>}包含几种提供TSP实例近似解的算法。例如，2-opt算法很快就能给出好的解决方案。下面是如何在tspy包中使用它的方法：
fromtspy.solversimportTwoOpt_solvertwo_opt=TwoOpt_solver(initial_tour='NN',iter_num=100)two_opt_tour=tsp.get_approx_solution(two_opt)
其他解算器也同样使用。
当前的解决方案存储在字典中。如果已向实例提供数据矩阵，则可以显示解决方案的绘图：
tsp.plot_solution('TwoOpt_solver')
在任何时候，都可以检索已计算的最佳解决方案：
best_tour=tsp.get_best_solution()
计算下限
由于tsp是np-hard，很难得到大型实例的精确解。然而，通过计算下界，我们可以知道我们的近似值有多好。tspy包提供了几个下界方法。一个例子由Simple_LP_bound给出tsp的LP relaxation的最优解：
fromtspy.lower_boundsimportSimple_LP_boundlower_bound=tsp.get_lower_bound(Simple_LP_bound())
在任何时候，都可以检索已计算的最佳下限：
best_lower_bound=tsp.get_best_lower_bound()
未来
将很快添加以下功能：
- 遗传规划
- 蚁群优化
- lin–kernighan启发式
- 更好的lp下限
如果你愿意帮忙，请随时与我联系。
作者
tspy由william borgeaud（williamborgeaud[at]gmail.com）撰写。
欢迎加入QQ群-->： 979659372
