Towards Solving TSPN with Arbitrary Neighborhoods: A Hybrid Solution

详细信息    查看全文

• 关键词：TSP ; TSPN ; Neighborhood ; Hybrid ; Metaheuristic
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10142
• 期：1
• 页码：204-215
• 丛书名：Artificial Life and Computational Intelligence
• ISBN：978-3-319-51691-2
• 卷排序：10142

文摘

As the generalization of TSP (Travelling Salesman Problem), TSPN (TSP with Neighborhoods) is closely related to several important real-world applications. However, TSPN is significantly more challenging than TSP as it is inherently a mixed optimization task containing both combinatorial and continuous components. Different from previous studies where TSPN is either tackled by approximation algorithms or formulated as a mixed integer problem, we present a hybrid framework in which metaheuristics and classical TSP solvers are combined strategically to produce high quality solutions for TSPN with arbitrary neighborhoods. The most distinctive feature of our solution is that it imposes no explicit restriction on the shape and size of neighborhoods, while many existing TSPN solutions require the neighborhoods to be disks or ellipses. Furthermore, various continuous optimization algorithms and TSP solvers can be conveniently adopted as necessary. Experiment results show that, using two off-the-shelf routines and without any specific performance tuning efforts, our method can efficiently solve TSPN instances with up to 25 regions, which are represented by both convex and concave random polygons.