A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling

Anirudh Subramanyam () and Chrysanthos E. Gounaris ()
Additional contact information
Anirudh Subramanyam: Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Chrysanthos E. Gounaris: Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Transportation Science, 2018, vol. 52, issue 2, 386-401

Abstract: The consistent traveling salesman problem aims to identify minimum-cost routes to be followed by a single vehicle so as to provide a set of customers with service that adheres to arrival-time consistency across the multiple time periods of a planning horizon. In this paper, we address this problem via a new, exact algorithm that decomposes the problem into a sequence of single-period traveling salesman problems with time windows within a branch-and-bound search procedure. The new algorithm is highly competitive, as it is able to solve to guaranteed optimality instances with up to 100 customers requiring service over a five-period horizon, effectively doubling the size of instances that were solvable by the previous state of the art. Furthermore, and in contrast to all previous approaches, the new algorithm accounts for route duration limits, whenever applicable, as well as incorporates the flexibility for the vehicle to idle before providing service to a customer. We in fact show that, for the benchmark instances we considered, the cost of implementing consistent routes can be reduced significantly if the vehicle is allowed to idle en route, further motivating the need for algorithmic schemes to incorporate this realistic option.

Keywords: traveling salesman problem; service consistency; decomposition-based search (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0741 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:2:p:386-401

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().