Secomandi, Nicola Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. (English) Zbl 0962.90010 Comput. Oper. Res. 27, No. 11-12, 1201-1225 (2000). Summary: The paper considers a version of the vehicle routing problem where customers’ demands are uncertain. The focus is on dynamically routing a single vehicle to serve the demands of a known set of geographically dispersed customers during real-time operations. The goal consists of minimizing the expected distance traveled in order to serve all customers’ demands. Since actual demand is revealed upon arrival of the vehicle at the location of each customer, fully exploiting this feature requires a dynamic approach. This work studies the suitability of the emerging field of neuro-dynamic programming (NDP) in providing approximate solutions to this difficult stochastic combinatorial optimization problem. The paper compares the performance of two NDP algorithms: optimistic approximate policy iteration and a rollout policy. While the former improves the performance of a nearest-neighbor policy by \(2.3\%\), the computational results indicate that the rollout policy generates higher quality solutions. The implication for the practitioner is that the rollout policy is a promising candidate for vehicle routing applications where a dynamic approach is required. Cited in 28 Documents MSC: 90B20 Traffic problems in operations research 90C27 Combinatorial optimization 90C39 Dynamic programming 90C15 Stochastic programming Keywords:vehicle routing problem; neuro-dynamic programming; stochastic combinatorial optimization problem PDFBibTeX XMLCite \textit{N. Secomandi}, Comput. Oper. Res. 27, No. 11--12, 1201--1225 (2000; Zbl 0962.90010) Full Text: DOI References: [1] Powell WB, Jaillet P, Odoni A. Stochastic and Dynamic Networks and Routing. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL, editors. Network routing, vol. 8, Handbooks in Operations Research and Management Science. Amsterdam: Elsevier, 1995 [chapter 3].; Powell WB, Jaillet P, Odoni A. Stochastic and Dynamic Networks and Routing. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL, editors. Network routing, vol. 8, Handbooks in Operations Research and Management Science. Amsterdam: Elsevier, 1995 [chapter 3]. [2] Psaraftis, H. N., Dynamic vehicle routing, Annals of Operations Research, 61, 143-164 (1995) · Zbl 0839.90037 [3] Bertsimas, D. J.; Simchi-Levi, D., A new generation of vehicle routing research: robust algorithms, addressing uncertainty, Operations Research, 44, 286-304 (1996) · Zbl 0855.90053 [4] Bertsekas, D. P., Dynamic programming and optimal control (1995), Athena Scientific: Athena Scientific Belmont, MA · Zbl 0935.90037 [5] Bertsekas, D. P.; Tsitsiklis, J. N., Neuro-dynamic programming (1996), Athena Scientific: Athena Scientific Belmont, MA · Zbl 0924.68163 [6] Sutton, R. S.; Barto, A. G., Reinforcement learning (1998), MIT Press: MIT Press Cambridge, MA [7] Golden BL, Assad AA, editors. Vehicle routing: methods and studies. Amsterdam: Elsevier, 1988.; Golden BL, Assad AA, editors. Vehicle routing: methods and studies. Amsterdam: Elsevier, 1988. · Zbl 0638.00043 [8] Fisher M. Vehicle routing. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL, editors. Network routing, Vol. 8, Handbooks in Operations Research and Management Science. Amsterdam: Elsevier, 1995 [Chapter 1].; Fisher M. Vehicle routing. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL, editors. Network routing, Vol. 8, Handbooks in Operations Research and Management Science. Amsterdam: Elsevier, 1995 [Chapter 1]. [9] Crainic, T. G.; Laporte, G., Planning models for freight transportation, European Journal of Operational Research, 97, 409-438 (1997) · Zbl 0919.90055 [10] Bramel, J.; Simchi-Levi, D., The logic of logistics (1997), Springer: Springer New York · Zbl 0931.90002 [11] Dror, M.; Laporte, G.; Trudeau, P., Vehicle routing with stochastic demands: properties and solution frameworks, Transportation Science, 23, 166-176 (1989) · Zbl 0689.90025 [12] Bertsimas, D. J., A vehicle routing problem with stochastic demands, Operations Research, 40, 574-585 (1992) · Zbl 0764.90030 [13] Bertsimas, D. J.; Chervi, P.; Peterson, M., Computational approaches to stochastic vehicle routing problems, Transportation Science, 29, 342-352 (1995) · Zbl 0853.90037 [14] Gendreau, M.; Laporte, G.; Séguin, R., Stochastic vehicle routing, European Journal of Operational Research, 88, 3-12 (1996) · Zbl 0913.90094 [15] Gendreau, M.; Laporte, G.; Séguin, R., An exact algorithm for the vehicle routing problem with stochastic demands and customers, Transportation Science, 29, 143-155 (1995) · Zbl 0860.90051 [16] Gendreau, M.; Laporte, G.; Séguin, R., A tabu search heuristic for the vehicle routing problem with stochastic demands and customers, Operations Research, 44, 469-477 (1996) · Zbl 0864.90043 [17] Lambert, V.; Laporte, G.; Louveaux, F. V., Designing collection routes through bank branches, Computers and Operations Research, 20, 783-791 (1993) [18] Dror, M.; Ball, M. O.; Golden, B. L., Computational comparison of algorithms for inventory routing, Annals of Operations Research, 4, 3-23 (1985) [19] Larson, R. C., Transportation of sludge to the 106-mile site: an inventory routing algorithm for fleet sizing and logistic system design, Transportation Science, 22, 186-198 (1988) [20] Bartholdi, J. J.; Platzman, L. K.; Collins, R. L.; Warden, W. H., A minimal technology routing system for meals on wheels, Interfaces, 13, 1-8 (1983) [21] Dror, M., Modeling vehicle routing with uncertain demands as a stochastic program: properties of the corresponding solution, European Journal of Operational Research, 64, 432-441 (1993) · Zbl 0776.90017 [22] Bastian, C.; Rinnooy Kan, A. H.G., The stochastic vehicle routing problem revisited, European Journal of Operational Research, 56, 407-412 (1992) · Zbl 0769.90032 [23] Yang WH, Mathur K, Ballou RH. Stochastic vehicle routing with restocking. Transportation Science, to appear.; Yang WH, Mathur K, Ballou RH. Stochastic vehicle routing with restocking. Transportation Science, to appear. · Zbl 1014.90020 [24] Secomandi N. Exact and heuristic dynamic programming algorithms for the vehicle routing problem with stochastic demands. Dissertation, University of Houston, USA, 1998.; Secomandi N. Exact and heuristic dynamic programming algorithms for the vehicle routing problem with stochastic demands. Dissertation, University of Houston, USA, 1998. [25] Teodorović, D.; Pavković, G., A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand, Transportation Planning and Technology, 16, 261-273 (1992) [26] Dror, M.; Trudeau, P., Stochastic vehicle routing with modified savings algorithm, European Journal of Operational Research, 23, 228-235 (1986) · Zbl 0577.90058 [27] Dror, M.; Laporte, G.; Louveaux, F. V., Vehicle routing with stochastic demands and restricted failures, Zeitschrift für Operations Research, 37, 273-283 (1993) · Zbl 0804.90040 [28] Bouzaı̈ene-Ayari, B.; Dror, M.; Laporte, G., Vehicle routing with stochastic demands and split deliveries, Foundations of Computing and Decision Sciences, 18, 63-69 (1993) · Zbl 0799.90049 [29] Laporte, G.; Louveaux, F. V., The integer L-shaped method for stochastic integer programs with complete recourse, Operations Research Letters, 13, 133-142 (1993) · Zbl 0793.90043 [30] Golden, B. L.; Yee, J. R., A framework for probabilistic vehicle routing, AIIE Transactions, 11, 109-112 (1979) [31] Stewart, W. R.; Golden, B. L., Stochastic vehicle routing: a comprehensive approach, European Journal of Operational Research, 14, 371-385 (1983) · Zbl 0519.90031 [32] Laporte, G.; Louveaux, F. V.; Mercure, H., Models and exact solutions for a class of stochastic location-routing problems, European Journal of Operational Research, 39, 71-78 (1989) · Zbl 0676.90019 [33] Bertsimas, D. J.; van Ryzin, G., A stochastic and dynamic vehicle routing problem in the Euclidean plane, Operations Research, 39, 601-615 (1991) · Zbl 0736.90027 [34] Bertsimas, D. J.; van Ryzin, G., Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles, Operations Research, 41, 60-76 (1993) · Zbl 0776.90018 [35] Bertsimas, D. J.; van Ryzin, G., Stochastic and dynamic vehicle routing with general demand and interarrival time distributions, Advances in Applied Probability, 25, 947-978 (1993) · Zbl 0784.60016 [36] Bertsekas, D. P.; Tsitsiklis, J. N.; Wu, C., Rollout algorithms for combinatorial optimization, Journal of Heuristics, 3, 245-262 (1997) · Zbl 1071.90571 [37] Bertsekas DP, Castanon DA. Rollout algorithms for stochastic scheduling problems. Journal of Heuristics, to appear.; Bertsekas DP, Castanon DA. Rollout algorithms for stochastic scheduling problems. Journal of Heuristics, to appear. · Zbl 0997.90037 [38] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1988), Wiley: Wiley New York · Zbl 0469.90052 [39] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, 1276-1290 (1994) · Zbl 0822.90053 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.