کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476219 | 699429 | 2006 | 22 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Aggregation for the probabilistic traveling salesman problem Aggregation for the probabilistic traveling salesman problem](/preview/png/476219.png)
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.
Journal: Computers & Operations Research - Volume 33, Issue 9, September 2006, Pages 2703–2724