A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited

Patrick Jaillet
Additional contact information
Patrick Jaillet: Ecole Nationale des Ponts et Chaussees, Paris, France

Operations Research, 1988, vol. 36, issue 6, 929-936

Abstract: Consider a problem of routing through a set of n points. On any given instance of the problem, only a subset consisting of k out of n points (0 ≤ k ≤ n ) has to be visited, with the number k random with known probability distribution. We wish to find a priori a tour through all n points. On any given instance, the k points present will then be visited in the same order as they appear in the a priori tour. The problem of finding such a tour of minimum length in the expected value sense is defined as a Probabilistic Traveling Salesman Problem (PTSP). What distinguishes one PTSP from another is the probability distribution (or more generally, the probability “law”) that specifies the number k and the identity of the points that need to be visited on any given instance of the problem. After motivating the problem by applications, we first derive closed form expressions for computing efficiently the expected length of any given tour under very general probabilistic assumptions. We then provide, in a unified way, an analysis of these expressions and derive several interesting properties of the problem.

Keywords: networks/graphs: traveling salesman; probabilistic version (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (65)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.6.929 (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:oropre:v:36:y:1988:i:6:p:929-936

Access Statistics for this article

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