×

Partial-route inequalities for the multi-vehicle routing problem with stochastic demands. (English) Zbl 1302.90022

Summary: This paper describes an exact algorithm for a variant of the vehicle routing problem in which customer demands to be collected are stochastic. Demands are revealed upon the vehicle arrival at customer locations. As a result, a vehicle may reach a customer and does not have sufficient capacity to collect the realized demand. Such a situation is referred to as a failure. In this paper the following recourse action is then applied when failure occurs: the vehicle returns to the depot to unload and resumes its planned route at the point of failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) consists of minimizing the sum of the planned routes cost and of the expected recourse cost. The VRPSD is formulated as a two-stage stochastic programming model and solved by means of an integer \(L\)-shaped algorithm. This paper introduces three lower bounding functionals based on the generation of general partial routes, as well as an exact separation procedure to identify violated cuts. Extensive computational results confirm the effectiveness of the proposed algorithm, as measured by a substantial reduction in the number of feasible solutions that have to be explicitly eliminated. This translates into a higher proportion of instances solved to optimality, reduced optimality gaps, and lower computing times.

MSC:

90B06 Transportation, logistics and supply chain management
90C15 Stochastic programming

Software:

CVRPSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ak, A.; Erera, A., A paired-vehicle recourse strategy for the vehicle-routing problem with stochastic demands, Transp. Sci., 41, 2, 222-237 (2007)
[2] Baldacci, R.; Mingozzi, A.; Roberti, R., New route relaxation and pricing strategies for the vehicle routing problem, Oper. Res., 59, 5, 1269-1283 (2011) · Zbl 1233.90059
[3] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 238-252 (1962) · Zbl 0109.38302
[4] Bertsimas, D. J., A vehicle routing problem with stochastic demand, Oper. Res., 40, 3, 574-585 (1992) · Zbl 0764.90030
[5] Bertsimas, D. J., Probabilistic combinatorial optimization problems (1988), Operations Research Center, Massachusetts Institute of Technology, (Ph.D. thesis)
[6] Bertsimas, D. J.; Jaillet, P.; Odoni, A. R., A priori optimization, Oper. Res., 38, 6, 1019-1033 (1999) · Zbl 0721.90062
[7] Christiansen, C. H.; Lysgaard, J., A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands, Oper. Res. Lett., 35, 6, 773-781 (2007) · Zbl 1180.90050
[8] Cordeau, J.-F.; Laporte, G.; Potvin, J.-Y.; Savelsbergh, M. W.P, Transportation, (Handbooks in Operations Research and Management Science (2007), Elsevier: Elsevier Amsterdam), 367-428
[9] Gendreau, M.; Laporte, G.; Séguin, R., An exact algorithm for the vehicle routing problem with stochastic demands and customers, Transp. Sci., 29, 2, 143-155 (1995) · Zbl 0860.90051
[10] Gendreau, M.; Laporte, G.; Séguin, R., A tabu search heuristic for the vehicle routing problem with stochastic demands and customers, Oper. Res., 44, 3, 469-477 (1996) · Zbl 0864.90043
[11] Golden, B. L.; Raghavan, S.; Wasil, E. A., The Vehicle Routing Problem: Latest Advances and New Challenges (2008), Springer: Springer New York · Zbl 1142.90004
[12] Goodson, J. C.; Ohlmann, J. W.; Thomas, B. W., Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand, European J. Oper. Res., 217, 2, 312-323 (2012) · Zbl 1244.90034
[13] Hjorring, C.; Holt, J., New optimality cuts for a single-vehicle stochastic routing problem, Ann. Oper. Res., 86, 569-584 (1999) · Zbl 0922.90058
[14] Jaillet, P., A priori solution of a traveling salesman problem in which a random subset of the customers are visited, Oper. Res., 36, 6, 929-936 (1978) · Zbl 0665.90096
[15] Juan, A.; Faulin, J.; Grasman, S.; Riera, D.; Marull, J.; Mendez, C., Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands, Transp. Res. C, 19, 5, 751-765 (2011)
[16] Lambert, V.; Laporte, G.; Louveaux, F. V., Designing collection routes through bank branches, Comput. Oper. Res., 20, 7, 783-791 (1993)
[17] Laporte, G., Fifty years of vehicle routing, Transp. Sci., 43, 4, 408-416 (2009)
[18] Laporte, G.; Louveaux, F. V., The integer \(L\)-shaped method for stochastic integer programs with complete recourse, Oper. Res. Lett., 13, 3, 133-142 (1993) · Zbl 0793.90043
[19] Laporte, G.; Louveaux, F. V.; Van hamme, L., An integer \(L\)-shaped algorithm for the capacitated vehicle routing problem with stochastic demands, Oper. Res., 50, 3, 415-423 (2002) · Zbl 1163.90773
[20] Lei, H.; Laporte, G.; Guo, B., The capacitated vehicle routing problem with stochastic demands and time windows, Comput. Oper. Res., 38, 12, 1775-1783 (2011) · Zbl 1215.90013
[21] Louveaux, F. V., An introduction to stochastic transportation models, (Labbé, M.; Laporte, G.; Tanczos, K.; Toint, P., Operations Research and Decision Aid Methodologies in Traffic and Transportation Management. Operations Research and Decision Aid Methodologies in Traffic and Transportation Management, NATO ASI Series, Series F: Computer and Systems Sciences (1998), Springer-Verlag: Springer-Verlag Berlin and Heidelberg), 244-263
[22] Lysgaard, J.; Letchford, A. N.; Eglese, R. W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math. Program., 100, 2, 423-445 (2004) · Zbl 1073.90068
[23] Chepuri, K.; Homem de Mello, T., Solving the vehicle routing problem with stochastic demands using the cross entropy method, Ann. Oper. Res., 134, 153-181 (2005) · Zbl 1074.90004
[24] Rei, W.; Gendreau, M.; Soriano, P., A hybrid monte carlo local branching algorithm for the single vehicle routing problem with stochastic demands, Transp. Sci., 44, 1, 136-146 (2010)
[25] Secomandi, N.; Margot, F., Reoptimization approaches for the vehicle-routing problem with stochastic demands, Oper. Res., 57, 1, 214-230 (2009) · Zbl 1181.90043
[26] Sungur, I.; Ordóñez, F.; Dessouky, M., A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty, IIE Trans., 40, 509-523 (2008)
[27] (Toth, P.; Vigo, D., The vehicle routing problem (2002), SIAM Monographs on Discrete Mathematics and Applications: SIAM Monographs on Discrete Mathematics and Applications Philadelphia) · Zbl 0979.00026
[28] Van Slyke, R. M.; Wets, R., \(L\)-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math., 17, 4, 638-663 (1969) · Zbl 0197.45602
[29] Yang, W.-H; Mathur, K.; Ballou, R. H., Stochastic vehicle routing problem with restocking, Transp. Sci., 34, 3, 99-112 (2000) · Zbl 1014.90020
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.