Nayak Abhishek, Rathinam Sivakumar
Mechanical Engineering, Texas A&M University, College Station, TX 77843, USA.
Sensors (Basel). 2023 Jul 15;23(14):6432. doi: 10.3390/s23146432.
This paper addresses a MinMax variant of the Dubins multiple traveling salesman problem (mTSP). This routing problem arises naturally in mission planning applications involving fixed-wing unmanned vehicles and ground robots. We first formulate the routing problem, referred to as the one-in-a-set Dubins mTSP problem (MD-GmTSP), as a mixed-integer linear program (MILP). We then develop heuristic-based search methods for the MD-GmTSP using tour construction algorithms to generate initial feasible solutions relatively fast and then improve on these solutions using variants of the variable neighborhood search (VNS) metaheuristic. Finally, we also explore a graph neural network to implicitly learn policies for the MD-GmTSP using a learning-based approach; specifically, we employ an S-sample batch reinforcement learning method on a shared graph neural network architecture and distributed policy networks to solve the MD-GMTSP. All the proposed algorithms are implemented on modified TSPLIB instances, and the performance of all the proposed algorithms is corroborated. The results show that learning based approaches work well for smaller sized instances, while the VNS based heuristics find the best solutions for larger instances.
本文探讨了杜宾斯多旅行商问题（mTSP）的一种极小极大变体。这个路由问题自然出现在涉及固定翼无人飞行器和地面机器人的任务规划应用中。我们首先将该路由问题，即集合中选一的杜宾斯mTSP问题（MD-GmTSP），表述为一个混合整数线性规划（MILP）。然后，我们为MD-GmTSP开发基于启发式的搜索方法，使用巡回构造算法相对快速地生成初始可行解，接着使用可变邻域搜索（VNS）元启发式的变体对这些解进行改进。最后，我们还探索了一种图神经网络，使用基于学习的方法为MD-GmTSP隐式学习策略；具体来说，我们在共享图神经网络架构和分布式策略网络上采用S样本批量强化学习方法来解决MD-GMTSP。所有提出的算法都在修改后的TSPLIB实例上实现，并且所有提出算法的性能都得到了证实。结果表明，基于学习的方法在较小规模的实例上效果良好，而基于VNS的启发式算法在较大规模的实例上能找到最佳解。
