Probabilistic Bounds on the k -Traveling Salesman Problem and the Traveling Repairman Problem

Moïse Blanchard (), Alexandre Jacquillat () and Patrick Jaillet ()
Additional contact information
Moïse Blanchard: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Alexandre Jacquillat: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Patrick Jaillet: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Mathematics of Operations Research, 2024, vol. 49, issue 2, 1169-1191

Abstract: The k - traveling salesman problem ( k -TSP) seeks a tour of minimal length that visits a subset of k ≤ n points. The traveling repairman problem (TRP) seeks a complete tour with minimal latency. This paper provides constant-factor probabilistic approximations of both problems. We first show that the optimal length of the k -TSP path grows at a rate of Θ ( k / n k / ( 2 ( k − 1 ) ) ) . The proof provides a constant-factor approximation scheme, which solves a TSP in a high-concentration zone, leveraging large deviations of local concentrations. Then, we show that the optimal TRP latency grows at a rate of Θ ( n n ) . This result extends the classic Beardwood–Halton–Hammersley theorem to the TRP. Again, the proof provides a constant-factor approximation scheme, which visits zones by decreasing order of probability density. We discuss practical implications of this result in the design of transportation and logistics systems. Finally, we propose dedicated notions of fairness—randomized population-based fairness for the k -TSP and geographic fairness for the TRP—and give algorithms to balance efficiency and fairness.

Keywords: Primary: 90C27; 90B15; secondary: 60C05; 90B06; traveling salesman; stochastic model applications; suboptimal algorithms (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0286 (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:ormoor:v:49:y:2024:i:2:p:1169-1191

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().