A branch-and-cut framework for the consistent traveling salesman problem

Anirudh Subramanyam, Chrysanthos E. Gounaris

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

We develop an exact solution framework for the Consistent Traveling Salesman Problem. This problem calls for identifying the minimum-cost set of routes that a single vehicle should follow during the multiple time periods of a planning horizon, in order to provide consistent service to a given set of customers. Each customer may require service in one or multiple time periods and the requirement for consistent service applies at each customer location that requires service in more than one time period. This requirement corresponds to restricting the difference between the earliest and latest vehicle arrival-times, across the multiple periods, to not exceed some given allowable limit. We present three mixed-integer linear programming formulations for this problem and introduce a new class of valid inequalities to strengthen these formulations. The new inequalities are used in conjunction with traditional traveling salesman inequalities in a branch-and-cut framework. We test our framework on a comprehensive set of benchmark instances, which we compiled by extending traveling salesman instances from the well-known TSPLIB library into multiple periods, and show that instances with up to 50 customers, requiring service over a 5-period horizon, can be solved to guaranteed optimality. Our computational experience suggests that enforcing arrival-time consistency in a multi-period setting can be achieved with merely a small increase in total routing costs.

Original languageEnglish (US)
Pages (from-to)384-395
Number of pages12
JournalEuropean Journal of Operational Research
Volume248
Issue number2
DOIs
StatePublished - Jan 16 2016

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'A branch-and-cut framework for the consistent traveling salesman problem'. Together they form a unique fingerprint.

Cite this