Cheung, Raymond K.; Xu, Dongsheng; Guan, Yongpei A solution method for a two-dispatch delivery problem with stochastic customers. (English) Zbl 1145.90323 J. Math. Model. Algorithms 6, No. 1, 87-107 (2007). Summary: We study a vehicle routing problem in which vehicles are dispatched multiple times a day for product delivery. In this problem, some customer orders are known in advance while others are uncertain but are progressively realized during the day. The key decisions include determining which known orders should be delivered in the first dispatch and which should be delivered in a later dispatch, and finding the routes and schedules for customer orders. This problem is formulated as a two-stage stochastic programming problem with the objective of minimizing the expected total cost. A worst-case analysis is performed to evaluate the potential benefit of the stochastic approach against a deterministic approach. Furthermore, a sample-based heuristic is proposed. Computational experiments are conducted to assess the effectiveness of the model and the heuristic. Cited in 1 Document MSC: 90B06 Transportation, logistics and supply chain management 90C15 Stochastic programming 90C59 Approximation methods and heuristics in mathematical programming 90C10 Integer programming Keywords:vehicle routing; stochastic customers; stochastic programming Software:VRP PDFBibTeX XMLCite \textit{R. K. Cheung} et al., J. Math. Model. Algorithms 6, No. 1, 87--107 (2007; Zbl 1145.90323) Full Text: DOI References: [1] Bertsimas, D.J., Simchi-Levi, D.: A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Oper. Res. 44, 216–304 (1996) · Zbl 0855.90053 [2] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, Berlin Heidelberg New York (1997) · Zbl 0892.90142 [3] Cheung, R.K., Powell, W.: SHAPE: a stochastic hybrid approximation procedure for two-stage stochastic programs. Oper. Res. 48, 73–79 (2000) · Zbl 1106.90361 [4] Cheung, R.K., Hang, D.D.: A time-window sliding procedure for driver-task assignment with random service times. IIE Trans. 35, 433–444 (2003) [5] Dror, M.: Vehicle routing with stochastic demands: models & computational methods. In: Dror, M., L’Ecuyer, P., Szidarouszky, F. (eds.) Modeling Uncertainty: An Examination of Stochastic Theory, Methods and Applications. International Series in Operations Research and Management Science, vol. 46, Kluwer, Boston, Massachussetts (2002) [6] Dror, M., Laporte, G., Trudeau, P.: Vehicle routing with stochastic demands: properties and solution frameworks. Transp. Sci. 23, 166–176 (1989) · Zbl 0689.90025 [7] Ermoliev, Y.: Stochastic quasigradient methods. In: Ermoliev, Y., Wets, R. (eds.) Numerical Methods in Stochastic Programming, pp. 143–185. Springer, Berlin Heidelberg New York (1988) · Zbl 0666.90072 [8] Gendreau, M., Laporte, G., Seguin, R.: An exact algorithm for the vehicle-routing problem with stochastic demands and customers. Transp. Sci. 29, 143–155 (1995) · Zbl 0860.90051 [9] Gendreau, M., Laporte, G., Seguin, R.: A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Oper. Res. 44, 469–477 (1996) · Zbl 0864.90043 [10] Haughton, M.A.: Quantifying the benefits of route reoptimisation under stochastic customer demands. J. Oper. Res. Soc. 51, 320–332 (2000) · Zbl 1055.90520 [11] Kleywegt, A.J., Shapiro, A., Homem-de-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12, 479–502 (2001) · Zbl 0991.90090 [12] Laporte, G., Louveaux, F.V.: Formulations and bounds for the stochastic capacitated vehicle routing with uncertain supplies. Economic Decision-Making: Games, Econometrics and Optimization, pp. 443–455. North Holland, Amsterdam, The Netherlands (1990) [13] Laporte, G., Louveaux, F.V., Mercure, H.: Models and exact-solutions for a class of stochastic location-routing problems. Eur. J. Oper. Res. 39, 71–78 (1989) · Zbl 0676.90019 [14] 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, 415–423 (2002) · Zbl 1163.90773 [15] Larsen, A., Madsen, O., Solomon, M.: Partially dynamic vehicle routing – models and algorithms. J. Oper. Res. Soc. 53, 637–646 (2002) · Zbl 1059.90024 [16] Powell, W.B., Jaillet, P., Odoni, A.: Stochastic and dynamic networks and routing. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Network Routing, Handbooks in Operations Research and Management Science, vol. 8, Elsevier, Amsterdam, The Netherlands (1995) · Zbl 0870.90059 [17] Psaraftis, N.: Dynamic vehicle routing: status and prospects. Ann. Oper. Res. 61, 143–164 (1995) · Zbl 0839.90037 [18] Savelsbergh, M.W.P., Goetschalckx, M.: A comparison of the efficiency of fixed versus variable vehicle routes. J. Bus. Logist. 16, 163–187 (1995) [19] Secomandi, N.: A rollout policy for the vehicle routing problem with stochastic demands. Oper. Res. 49, 796–802 (2001) · Zbl 1163.90373 [20] Secomandi, N.: Analysis of a rollout approach to sequencing problems with stochastic routing applications. J. Heuristics 9, 321–352 (2003) · Zbl 1043.90032 [21] Solomon, M.: Algorithms for the vehicle routing and scheduling problems with time windows. Oper. Res. 35, 254–265 (1987) · Zbl 0625.90047 [22] Stewart, W.R., Golden, B.L.: Stochastic vehicle-routing: a comprehensive approach. Eur. J. Oper. Res. 14, 371–385 (1983) · Zbl 0519.90031 [23] Toth, P., Vigo, D.: The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania (2002) · Zbl 0979.00026 [24] Verweij, B., Ahmed, S., Kleywegt, A., Nemhauser, G.L., Shapiro, A.: The sample average approximation method applied to stochastic routing problems: a computational study. Comput. Optim. Appl. 24, 289–333 (2003) · Zbl 1094.90029 [25] Waters, C.D.J.: Vehicle-scheduling problems with uncertainty and omitted customers. J. Oper. Res. Soc. 40, 1099–1108 (1989) · Zbl 0687.90050 [26] Yang, W.H., Mathur, K., Ballou, R.H.: Stochastic vehicle routing problem with restocking. Transp. Sci. 34, 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.