An a priori route is a route which specifies an ordering of all possible customers that a particular driver may need to visit. The driver may then skip those customers on the route who do not receive a delivery. Despite the prevalence of a priori routing, construction of these routes still presents considerable challenges. Exact methods are limited to small problem sizes, and even heuristic methods are intractable in the face of real-world-sized instances. In this chapter, we will review some of the ideas that have emerged in recent years to help solve these larger instances. We focus on the probabilistic traveling salesman problem and the recently introduced probabilistic traveling salesman problem with deadlines and discuss how objective-function approximations can reduce computation time without significantly impacting solution quality. We will also present several open research questions in a priori routing.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Key words
References
J.J. Bartholdi, L.K. Platzman, R.L. Collins, and W.H. Warden. A minimal technology routing system for meals on wheels.Interfaces, 13:1–8, 1983.
J.J. Bartholdi and L.K. Platzman. An o(n log n) planar traveling salesman heuristic based on spacefilling curves.Operations Research Letters, 1:121–125, 1982.
C. Bastian and A.H.G. Rinnooy Kan. The stochastic vehicle routing problem revisited.European Journal of Operational Research, 56:407–412, 1992.
J.E. Beasley and N.Christofides. Vehicle routing with a sparse feasibility graph.European Journal of Operational Research, 98:499–511, 1997.
W.C. Benton and M.D. Rosetti. The vehicle scheduling problem with intermittent customer demands.Computers and Operations Research, 19:521–531, 1992.
P.Beraldi, G.Ghiani, G.Laporte, and R.Musmanno. Efficient neighborhood search for the probabilistic pickup and delivery travelling salesman problem.Networks, 45 (4):195–198, 2005.
D.Simchi-Levi. Finding optimal a priori tour and location of traveling salesman with nonhomogenous customers.Transportation Science, 22:148–154, 1988.
D.J. Bertsimas.Probabilistic Combinatorial Optimizations Problems. PhD thesis, Massachusetts Institute of Technology, 1988.
D.J. Bertsimas and L.H. Howell. Further results on the probabilistic traveling salesman problem.European Journal of Operational Research, 65:68–95,1993.
D.J. Bertsimas, P.Jaillet, and A.R. Odoni. A priori optimization.Operations Research, 38:1019–1033, 1990.
D.J. Bertsimas, P. Chervi, and M. Peterson. Computational approaches to stochastic vehicle routing problems.Transportation Science, 29:342–352, 1995.
L. Bianchi and A.M. Campbell. Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem.European Journal of Operational Research, 176: 131–144, 2007.
L. Bianchi, L.M. Gambardella, and M. Dorigo. Solving the homogeneous probabilistic traveling salesman problem by the aco metaheuristic. In M. Dorigo, G. DiCaro, and M. Sampels, editors,Proceedings of ANTS 2002: Third International Workshop, volume 2463/2002 ofLecture Notes in Computer Science, pages 176–187, Berlin, 2002. Springer.
L. Bianchi, L.M. Gambardella, and M. Dorigo. An ant colony optimization approach to the probabilistic traveling salesman problem. In G. Goos, J. Hartmanis, and J. van Leeuwen, editors,Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, volume 2439/2002 ofLecture Notes in Computer Science, pages 883–892, Berlin, 2002. Springer.
Leonora Bianchi, Joshua Knowles, and Neil Bowler. 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.
J.R. Birge and F.Louveaux.Introduction to Stochastic Programming. Springer-Verlag, New York, 1997.
N.E. Bowler, T.M.A. Fink, and R.C. Ball. Characterization of the probabilistic traveling salesman problem.Physical Review E, 68:036703, 2003.
J. Bramel, E.G. Coffman, P.W. Shor, and D.Simchi-Levi. Probabilistic analysis of the capacitated vehicle routing problem with unsplit demands.Operations Research, 340:1095–1106, 1992.
J. Branke and M. Guntsch. Solving the probabilistic tsp with ant colony optimization.Journal of Mathematical Modelling and Algorithms, 3 (4):403–425, 2004.
M.L. Braun and J.M. Buhmann. The noisy euclidean traveling salesman problem and learning. In T.Dietterich, S.Becker, and Z.Ghahramani, editors,Advances in Neural Information Processing Systems, volume14, pages 251–258. MIT Press, 2002.
A.M. Campbell. Aggregation for the probabilistic traveling salesman problem.Computers & Operations Research, 33:2703–2724, 2006.
A.M. Campbell and B.W. Thomas. The probabilistic traveling salesman problem with deadlines. forthcoming inTransportation Science, 2007
A.M. Campbell and B.W. Thomas. Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Submitted to Computers and Operations Research, 2007
A.M. Campbell and B.W. Thomas. The stochastic vehicle routing problem with deadlines. Working Paper, 2007.
B.Carey. Expedited grows on the surface.Traffic World, page1, January 2, 2006.
A. Charnes and W.W. Cooper. Chance-constrained programming.Management Science, 6:73–79, 1959.
A. Charnes and W.W. Cooper. Deterministic equivalents for optimizing and satisficing under chance constraints.Operations Research, 11:18–39, 1963.
P.Chervi. A computational approach to probabilistic vehicle routing problems. Master’s thesis, Massachusetts Institute of Technology, 1988.
M.S. Daskin, A. Haghani, M. Khanal, and C. Malandraki. Aggregation effects in maximum covering models.Annals of Operations Research, 18:115–139, 1989.
M.deBerg, O.Schwarzkopf, M.van Kreveld, and M.Overmars.Computational Geometry: Algorithms and Applications. Springer-Verlag, 2000.
M. Dror. Modeling vehicle routing with uncertain demands as stochastic programs: Properties of the corresponding solution.European Journal of Operational Research, 64: 432–441, 1993.
M. Dror and P. Trudeau. Stochastic vehicle routing with modified savings algorithm.European Journal of Operational Research, 23:228–235, 1986.
M. Dror, G. Laporte, and P. Trudeau. Vehicle routing with stochastic demands: Properties and solution frameworks.Transportation Science, 23:166–176, 1989.
R. L. Francis and T. J. Lowe. On worst-case aggregation analysis for network location problems.Annals of Operations Research, 40:229–246, 1992.
M. Gendreau, G. Laporte, and R. Séguin. An exact algorithm for the vehicle routing problem with stochastic demands and customers.Transportation Science, 29:143–155, 1995.
M. Gendreau, G. Laporte, and R. Séguin. Stochastic vehicle routing.European Journal of Operational Research, 88:3–12, 1996.
M. Gendreau, G. Laporte, and R. Séguin. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers.Operations Research, 44:469–477, 1996.
J. Grefenstette, R. Gopal, B. Rosmaita, , and D. Van Gucht. Genetic algorithms for the traveling salesman problem. In J.Grefenstette, editor,Proceedings of the First International Conference on Genetic Algorithms, Hillsdale, New York, 1985. Lawrence Erlbaum Associates.
M. A. Haughton. Quantifying the benefits of route reoptimisation under stochastic customer demand.Journal of the Operational Research Society, 51:320–332, 2000.
M. A. Haughton. Route reoptimization’s impact on delivery efficiency.Transportation Research - Part E, 38:53–63, 2002.
P.Jaillet.Probabilistic Traveling Salesman Problems. PhD thesis, Massachusetts Institute of Technology, 1985.
P. Jaillet. A priori solution of the traveling salesman problem in which a random subset of customers are visited.Operations Research, 36:929–936, 1988.
G. Laporte, F.V. Louveaux, and H. Mercure. Models and exact solutions for a class of stochastic location-routing problems.European Journal of Operational Research, 39:71–78, 1989.
G. Laporte, F. V. Louveaux, and H. Mercure. A priori optimization of the probabilistic traveling salesman problem.Operations Research, 42:543–549, 1994.
F.Li, B.Golden, and E.Wasil. The noisy euclidean traveling salesman problem: A computational analysis. In F.Alt, M.Fu, and B.Golden, editors,Perspectives in Operations Research: Papers in Honor of Saul Gass’80th Birthday, pages 247–270. Springer, 2006.
S. Lin. Computer solution of the traveling salesman problem.Bell System Technical Journal, 44:2245–2269, 1965.
Y.-H. Liu. A scatter search based approach with approximate evaluation for the heterogeneous probabilistic traveling salesman problem. InProceedings of the 2006 IEEE Congress on Evolutionary Computation, pages 1603–1609, 2006.
J. Mercenier and P. Michel. Discrete-time finite horizon approximation of infinite horizon optimization problems with steady-state variance.Econometrica, 62 (3):635–656, 1994.
A. M. Newman and M. Kuchta. Using aggregation to optimize long-term production planning at an underground mine.European Journal of Operational Research, 176: 1205–1218, 2007.
M. B. Rayco, R. L. Francis, and A. Tamir. A p-center grid-positioning aggregation procedure.Computers and Operations Research, 26:1113–1124, 1999.
S. Rosenow. A heuristic for the probabilistic TSP. In H.Schwarze, editor,Operations Research Proceedings 1996. Springer Verlag, 1997.
S.Rosenow. Comparison of an exact branch-and-bound and an approximative evolutionary algorithm for the probabilistic traveling salesman problem. working paper, available at urlhttp://www2.hsu-hh.de/uebe/paper-engl-SOR98.pdf, 1998.
F.Rossi and I.Gavioli. Aspects of heuristic methods in the probabilistic traveling salesman problem. InAdvanced School on Stochastics in Combinatorial Optimization, pages 214–227. World Scientific, 1987.
Martin W.P. Savelsbergh and M. Goetschalckx. A comparison of the efficiency of fixed versus variable vehicle routes.Journal of Business Logistics, 46:474–490, 1995.
W. R. Stewart and Bruce L. Golden. Stochastic vehicle routing: A comprehensive approach.European Journal of Operational Research, 14: 371–385, 1983.
Hao Tang and Elise Miller-Hooks. Approximate procedures for the probabilistic traveling salesman problem.Transportation Research Record, 1882:27–36, 2004.
S. Y. Teng, H. L. Ong, and H. C. Huang. An integer L-shaped algorithm for the time-constrained traveling salesman problem with stochastic travel times and service times.Asia-Pacific Journal of Operational Research, 21: 241–257, 2004.
F. Tillman. The multiple terminal delivery problem with probabilistic demands.Transportation Science, 3:192–204, 1969.
United Parcel Service. About UPS. urlhttp://www.corporate-ir.net/ireye/ir_site.zhtml?ticker=UPS&script=2100& layout=7, 2002. Accessed on November 30, 2006.
C. D.J. Waters. Vehicle scheduling problems with uncertainty and omitted customers.Journal of the Operational Research Society, 40: 1099–1108, 1989.
Jacky C.F. Wong, Janny M.Y. Leung, and C.H. Cheng. On a vehicle routing problem with time windows and stochastic travel times: Models, algorithms, and heuristics. Technical Report SEEM2003-03, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, 2003.
Wen-Huei Yang, Kamlesh Mather, and RonaldH. Ballou. Stochastic vehicle routing problem with restocking.Transportation Science, 34:99–112, 2000.
H. Zhong, R. W. Hall, and M. Dessouky. Territory planning and driver learning in vehicle dispatching.Transportation Science, to appear.
Hongsheng Zhong.Territory Planning and Vehicle Dispatching with Stochastic Customers and Demand. PhD thesis, University of Southern California, 2001.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Campbell, A.M., Thomas, B.W. (2008). Challenges and Advances in A Priori Routing. In: Golden, B., Raghavan, S., Wasil, E. (eds) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, vol 43. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-77778-8_6
Download citation
DOI: https://doi.org/10.1007/978-0-387-77778-8_6
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-77777-1
Online ISBN: 978-0-387-77778-8
eBook Packages: Business and EconomicsBusiness and Management (R0)