Perturbation Analysis for Maximum Scatter TSP

MaxScatterTSP++ presents six practical algorithms for the Maximum Scatter TSP and performs perturbation studies to analyze trade-offs among the runtime, quality and stability of these algorithms.

ALENEX 2022 Paper View Code and Data

About

The Maximum Scatter Traveling Salesman Problem (MSTSP) is a variant of the famous Traveling Salesman Problem (TSP) and finds its use in several real-world applications including manufacturing, imaging and laser melting processes. The objective of this problem is to maximize the cost of the least cost edge in a tour of an input graph. Akin to the TSP and several of its variants, the MSTSP is an NP-hard problem. While several approximation algorithms have been proposed for this problem, many of them suffer from bad worst-case complexities and present challenges in scalability and practical use.

In this work, we describe six algorithms for MSTSP inspired by prior work in the area, along with improved formulations that enhance their utility in real-world scenarios. Further, we perform experimental studies motivated by smoothed analysis to comprehensively evaluate these algorithms from the perspective of run-time, quality and stability.

The six algorithms that we describe in this work are:

• Naive Greedy Algorithm
• Naive Weave Algorithm
• Hoffmann Weave Algorithm
• Dirac Algorithm
• Pure 2-opt Algorithm
• Randomized 2-opt Algorithm

Our benchmarking experiments can be broadly split into three categories:

• Closeness of algorithm predictions to the scatter bound
• Deviation of maximum scatter predictions under perturbation
• Variation in the runtime of algorithms

Key Contributions

1. We present the Naive Greedy algorithm as a fast and easy-to-implement baseline for MSTSP.
2. We present the Naive Weave and Hoffmann Weave algorithms which introduce an improved formulation of the work by Arkin et al. and Hoffmann et al. to extend their usability to non-regular grids.
3. We extend the work in Johnson et al. to introduce Pure 2-opt and Randomised 2-opt as very close approximation algorithms for the MSTSP.
4. We use a real-world dataset augmented using five graph perturbations and evaluated with three edge cost metrics to perform a comprehensive perturba- tion analysis of the algorithms and compare results on three critical performance measures, namely, the quality, runtime and stability of the algorithms.

Publication

Our paper on this work titled “Perturbation Analysis of Practical Algorithms for the Maximum Scatter Travelling Salesman Problem” has been accepted as a conference paper at the ALENEX workshop as part of the Symposium on Discrete Algorithms (SODA), 2022 to be held at Alexandria, Virginia, U.S.A.

People

This work has been developed by Emil Biju and Sundar Raman from the Indian Institute of Technology, Madras. Ask us your questions at emilbiju7@gmail.com or sundarramanp2000@gmail.com.

Learnings and Further Work

Through this paper, we have presented a comprehensive study of different approximation methods for the MSTSP that highlight critical factors that must influence the choice of an algorithm in practical settings. Our procedural philosophy can further be extended to the study of other NP-hard problems of practical importance.