Multiple traveling salesmen and related problems: A maximum-entropy principle based approach

Mayank Baranwal, Brian Roehl, Srinivasa M. Salapaka

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper presents a new heuristic approach for multiple traveling salesmen problem (mTSP) and other variants of the TSP. In this approach, the TSP and its variants are seen as constrained resource allocation problems, where an ordered set of resources is associated to the cities, and the allocation is done through an iterative algorithm in such a way that eventually each city gets associated with a resource. The approach allows adding constraints on resources which translate to objectives such as minimum tour length (or multiple tour lengths as in mTSP) and other constraints that define the variants on the TSP problem. The algorithm for the associated resource allocation problem is based on maximum entropy principle (MEP) and the deterministic annealing algorithm. Besides mTSP, this article demonstrates this approach for close enough traveling salesman problem (CETSP), which is known to be computationally challenging since there is a continuum of possible edges between a pair of cities. The examples presented in this paper illustrate the effectiveness of this new framework for use in TSP and many variants thereof. Simulations demonstrate that the proposed MEP algorithm achieves significantly better solutions than the ones provided by the most commonly used simulated annealing algorithm with only marginal increase in run-time.

Original languageEnglish (US)
Title of host publication2017 American Control Conference, ACC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781509059928
StatePublished - Jun 29 2017
Event2017 American Control Conference, ACC 2017 - Seattle, United States
Duration: May 24 2017May 26 2017

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Other2017 American Control Conference, ACC 2017
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Multiple traveling salesmen and related problems: A maximum-entropy principle based approach'. Together they form a unique fingerprint.

Cite this