zbMATH — the first resource for mathematics

Aggregation for the probabilistic traveling salesman problem. (English) Zbl 1086.90047
Summary: 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.

90C27 Combinatorial optimization
Full Text: DOI
[1] Bartholdi, J.J.; Platzman, L.K.; Lee Collins, R.; Warden, W.H., A minimal technology routing system for meals on wheels, Interfaces, 13, 1-8, (1983)
[2] Jaillet P, Odoni A. The probabilistic vehicle routing problem. In: Vehicle routing: methods and studies. Amsterdam: North-Holland; 1988. p. 293-318.
[3] Campbell A, Savelsbergh M. Decision support for consumer direct grocery initiatives. Transportation Science; 2004, forthcoming.
[4] Campbell A, Savelsbergh M. Incentive schemes for attended home delivery services. Transportation Science; 2004, under review.
[5] Jaillet P. The probabilistic traveling salesman problems. PhD thesis. Cambridge, MA: Massachusetts Institute of Technology; 1985.
[6] Jaillet, P., A priori solution of a traveling salesman problem in which a random subset of the customers are visited, Operations research, 36, 6, 929-936, (1988) · Zbl 0665.90096
[7] Berman, O.; Simchi-Levi, D., Finding optimal a priori tour and location of traveling salesman with nonhomogenous customers, Transportation science, 22, 148-154, (1988) · Zbl 0653.90082
[8] Rossi, F.; Gavioli, I., Aspects of heuristic methods in the probabilistic traveling salesman problem, () · Zbl 0646.90081
[9] Bertsimas, D.; Howell, L., Further results on the probabilistic traveling salesman problem, European journal of operational research, 65, 68-95, (1993) · Zbl 0776.90082
[10] Bartholdi, J.J.; Platzman, L.K., An \(o(n \log n)\) planar traveling salesman heuristic based on spacefilling curves, Operations research letters, 1, 121-125, (1982) · Zbl 0488.90072
[11] Lin, S., Computer solution of the traveling salesman problem, Bell system technical journal, 44, 2245-2269, (1965) · Zbl 0136.14705
[12] Bianchi, L.; Knowles, J.; Bowler, N., Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms, European journal of operational research, 162, 206-219, (2005) · Zbl 1132.90364
[13] Tang H, Miller-Hooks E. Approximate procedures for the probabilistic traveling salesperson problem. Transportation Research Record; 2004, forthcoming.
[14] Beraldi P, Ghiani G, Laporte G, Musmanno R. Efficient neighborhood search for the probabilistic pickup and delivery travelling salesman problem. Networks; 2004, forthcoming. · Zbl 1068.90085
[15] S. Rosenow, A heuristic for the probabilistic TSP. In: Schwarze H, et al., editors. Operations research proceedings 1996. Berlin: Springer; 1997.
[16] Bowler NE, Fink TM, Ball RC. Characterization of the probabilistic traveling salesman problem. Physical Review E 2003; 68.
[17] Bianchi, L.; Gambardella, L.M.; Dorigo, M., Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic, (), 176-187
[18] Branke, J.; Guntsch, M., New ideas for applying ant colony optimization to the probabilistic tsp, (), 166-175 · Zbl 1033.90516
[19] Laporte, G.; Louveaux, F.; Mercure, H., A priori optimization of the probabilistic traveling salesman problem, Operations research, 42, 3, 543-549, (1994) · Zbl 0810.90124
[20] Bertsimas D. Probabilistic combinatorial optimization problems. PhD thesis. Cambridge, MA: Massachusetts Institute of Technology.
[21] Bertsimas, D., A vehicle-routing problem with stochastic demand, Operations research, 40, 3, 574-585, (1992) · Zbl 0764.90030
[22] Bertsimas, D.; Jaillet, P.; Odoni, A., A priori optimization, Operations research, 38, 6, 1019-1033, (1990) · Zbl 0721.90062
[23] Gendreau, M.; Laporte, G.; Seguin, R., An exact algorithm for the vehicle routing problem with stochastic demands and customers, Transportation science, 29, 2, 143-155, (1995) · Zbl 0860.90051
[24] Daskin, M.S.; Haghani, A.; Khanal, M.; Malandraki, C., Aggregation effects in maximum covering models, Annals of operations research, 18, 115-139, (1989) · Zbl 0707.90067
[25] Francis, R.L.; Lowe, T.J., On worst-case aggregation analysis for network location problems, Annals of operations research, 40, 229-246, (1992) · Zbl 0787.90046
[26] Rayco, M.B.; Francis, R.L.; Tamir, A., A p-center grid-positioning aggregation procedure, Computers and operations research, 26, 1113-1124, (1999) · Zbl 0940.90064
[27] Current, J.R.; Schilling, D.A., Elimination of source \(a\) and \(b\) errors in \(p\)-Median location problems, Geographical analysis, 19, 2, 95-110, (1987)
[28] Zhao, P.; Batta, R., Analysis of centroid aggregation for euclidean distance \(p\)-Median problem, European journal of operational research, 113, 147-168, (1999) · Zbl 0933.90044
[29] Beasley, J.E.; Christofides, N., Vehicle routing with a sparse feasibility graph, European journal of operational research, 98, 499-511, (1997) · Zbl 0930.90008
[30] de Berg, M.; Schwarzkopf, O.; van Kreveld, M.; Overmars, M., Computational geometry: algorithms and applications, (2000), Springer Berlin · Zbl 0939.68134
[31] Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Carnegie Mellon University, Graduate School of Industrial Administration; 1976.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.