Journal article
Aggregation for the probabilistic traveling salesman problem
Computers & operations research, Vol.33(9), pp.2703-2724
09/01/2006
DOI: 10.1016/j.cor.2005.02.024
Abstract
In the probabilistic traveling salesman problem (PTSP), customers require a visit with a given probability, and the best solution is the tour through all customers with the lowest expected final tour cost. The PTSP is an important problem, both operationally and strategically, but is quite difficult to solve with realistically sized problem instances. One alternative is to aggregate customers into regions and solve the PTSP on the reduced problem. This approach raises questions such as how to best divide customers into regions and what scale is necessary to represent the full objective. This paper addresses these questions and presents computational results from experiments with both uniformly distributed and clustered data sets. The focus is on large problem instances where customers have a low probability of requiring a visit and the CPU time available is quite limited. For this class of instances, aggregation can yield very tight estimates of the full objective very quickly, and solving an aggregated form of the problem first can often lead to full solutions with lower expected costs. © 2005 Elsevier Ltd. All rights reserved.
Details
- Title: Subtitle
- Aggregation for the probabilistic traveling salesman problem
- Creators
- Ann Melissa Campbell - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Computers & operations research, Vol.33(9), pp.2703-2724
- Publisher
- Elsevier Science
- DOI
- 10.1016/j.cor.2005.02.024
- ISSN
- 0305-0548
- eISSN
- 1873-765X
- Language
- English
- Date published
- 09/01/2006
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380377702771
Metrics
3 Record Views