2016/04/14 by Mayank Baranwal, Baranwal, Mayank, Brian Roehl +3
Computer Science · Engineering · #Advanced Multi-Objective Optimization Algorithms #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1604.04169
openalex publication_date 2016/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a novel and efficient heuristic framework for approximating the solutions to the multiple traveling salesmen problem (m-TSP) and other variants on the TSP. The approach adopted in this paper is an extension of the Maximum-Entropy-Principle (MEP) and the Deterministic Annealing (DA) algorithm. The framework is presented as a general tool that can be suitably adapted to a number of variants on the basic TSP. Additionally, unlike most other heuristics for the TSP, the framework presented in this paper is independent of the edges defined between any two pairs of nodes. This makes the algorithm particularly suited for variants such as the close-enough traveling salesman problem (CETSP) which are challenging due to added computational complexity. The examples presented in this paper illustrate the effectiveness of this new framework for use in TSP and many variants thereof.