A transformation for a Multiple Depot, Multiple Traveling Salesman Problem
A transformation for a Multiple Depot, Multiple Traveling Salesman Problem
复制标题
多仓库、多旅行商问题的转换
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Darbha
中科院分区：
文献类型：
--
作者：
Paul Oberlin;S. Rathinam;S. Darbha
本文将一个多仓库多旅行商问题转化为一个单非对称旅行商问题，如果边的费用满足三角不等式。这改进了以前已知的2-仓库，多个旅行商问题的文献中的转换。为了测试转换的有效性，一些计算结果应用著名的LKH启发式转换的问题的实例涉及Dubins车辆。结果表明，该转换是有效的，高质量的解决方案，可以找到大的实例在相对较短的时间。
In this paper, a Multiple Depot, Multiple Traveling Salesman Problem is transformed into a Single, Asymmetric Traveling Salesman Problem if the cost of the edges satisfy the triangle inequality. This improves on the previously known transformation for a 2-Depot, Multiple Traveling Salesman Problem in the literature. To test the effectiveness of the transformation, some computational results are presented by applying the well known LKH heuristic on the transformed problem for instances involving Dubins vehicles. Results show that the transformation is effective and high quality solutions can be found for large instances in a relatively short time.