Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem

Area of Science:

• Operations Research
• Robotics
• Artificial Intelligence

Background:

• The Dubins multiple traveling salesman problem (mTSP) is crucial for mission planning with unmanned vehicles and ground robots.
• A specific variant, the one-in-a-set Dubins mTSP (MD-GmTSP), requires efficient routing solutions.

Purpose of the Study:

• To formulate and solve the MD-GmTSP.
• To compare the effectiveness of heuristic and learning-based approaches for this routing problem.

Main Methods:

• Formulation of the MD-GmTSP as a mixed-integer linear program (MILP).
• Development of heuristic-based search methods using tour construction and variable neighborhood search (VNS).
• Exploration of a graph neural network with reinforcement learning for policy learning.

Main Results:

• Heuristic-based VNS methods effectively solve larger MD-GmTSP instances.
• Learning-based approaches, utilizing graph neural networks, demonstrate strong performance on smaller instances.
• Algorithm performance was validated on modified TSPLIB instances.

Conclusions:

• Both VNS heuristics and learning-based methods offer viable solutions for the MD-GmTSP.
• The choice of algorithm depends on the scale of the problem instance.
• This research contributes to optimized mission planning for autonomous systems.