Abstract
This paper addresses the vehicle routing problem with time windows and multiple deliverymen in which the customer demands are uncertain and belong to a predetermined polytope. In addition to the routing decisions, this problem attempts to define the number of deliverymen used to service to the customers on each route. A new mathematical formulation is presented for the deterministic counterpart based on auxiliary variables that define the assignment of customers to routes. Building on this formulation, we apply a static robust optimization approach to obtain a robust counterpart formulation that captures the random nature of customer demand. Due to the difficulty in solving this formulation, we propose a constructive heuristic to generate a robust solution, which is used as a starting point for solving the robust counterpart formulation. The heuristic is an extension of Solomon’s heuristic I1. Computational results using problem instances from the literature and risk analysis via Monte-Carlo simulation indicate the potential of static robust optimization to address the trade-off between cost and risk. The results also reveal that the proposed approach provides good results even without exact knowledge of some probabilistic measure of the customer demand.
Similar content being viewed by others
References
Álvarez A, Munari P (2016) Metaheuristic approaches for the vehicle routing problem with time windows and multiple deliverymen. Gest Prod 23(2):279–293
Álvarez A, Munari P (2017) An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Comput Oper Res 83:1–12
Belfiore PP, Fávero LPL (2007) Scatter search for the fleet size and mix vehicle routing problem with time windows. Cent Eur J Oper Res 15(4):351–368
Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math Program Ser A 88:411–424
Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math Program 99(2):351–376
Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton series in applied mathematics. Princeton University Press, Princeton
Bertsimas D (1992) A vehicle routing problem with stochastic demand. Oper Res 40(3):574–585. https://doi.org/10.1287/opre.40.3.574
Bertsimas D, Goyal V (2012) On the power and limitations of affine policies in two-stage adaptive optimization. Math Program 134(2):491–531
Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35–53
Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev 53(3):464–501. https://doi.org/10.1137/080734510
Bertsimas D, Goyal V, Lu B (2015) A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization. Math Program 150(2):281–319
Birge JR, Louveaux F (2011) Introduction to stochastic programming. Springer, New York
Christiansen CH, Lysgaard J (2007) A branch-and-price algorithm for the capacited vehicle routig problem with stochastic demands. Oper Res Lett 35(6):773–781
De La Vega J, Alem D (2015) Energy rationalization in water supply networks via stochastic programming. Lat Am Trans, IEEE (Revista IEEE America Latina) 13(8):2742–2756. https://doi.org/10.1109/TLA.2015.7332158
Ferreira V, Pureza V (2012) Some experiments with a savings heuristic and a tabu search approach for the vehicle routing problem with multiple deliverymen. Pesq Oper 32:443–463
Gauvin C, Desaulniers G, Gendreau M (2014) A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Comput Oper Res 50:141–153
Gounaris CE, Wiesemann W, Floudas CA (2013) The robust capacitated vehicle routing problem under demand uncertainty. Oper Res 61(3):677–693
Hanasusanto GA, Kuhn D, Wiesemann W (2015) K-adaptability in two-stage robust binary programming. Oper Res 63(4):877–891. https://doi.org/10.1287/opre.2015.1392
Jabali O, Rei W, Gendreau M, Laporte G (2014) Partial-route inequalities for the multi-vehicle routing problem with stochastic demands. Discrete Appl Math 177:121–136
Laporte G, Louveaux F, Hamme L (2002) An integer L-shaped algorithm for the capacited vehicle routing problem with sotchastic demands. Oper Res 50(3):415–423
Lee C, Lee K, Park S (2012) Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J Oper Res Soc 63(9):1294–1306
Munari P, Morabito R (2016) A branch-price-and-cut for the vehicle routing problem with time windows and multiple deliverymen. Tech. rep., Production Engineering Dept., Federal University of São Carlos, Brazil
Ordóñez F (2010) Robust vehicle routing. INFORMS Tutorials in Operations Research, chap 7:153–178
Prékopa A (1995) Stochastic programming, vol 324. Springer, Netherlands
Pureza V, Morabito R, Reimann M (2012) Vehicle routing with multiple deliverymen: modeling and heuristic approaches for the VRPTW. Eur J Oper Res 218(3):636–647
Senarclens de Grancy G (2015) An adaptive metaheuristic for vehicle routing problems with time windows and multiple service workers. J Univer Comput Sci 21(9):1143–1167
Senarclens de Grancy G, Reimann M (2015) Evaluating two new heuristics for constructing customer clusters in a VRPTW with multiple service workers. CEJOR 23(2):479–500
Senarclens de Grancy G, Reimann M (2016) Vehicle routing problems with time windows and multiple service workers: a systematic comparison between ACO and GRASP. CEJOR 24(1):29–48
Shapiro A, Dentcheva D, Ruszczynski A (2014) Lectures on stochastic programming: modeling and theory, 2nd edn. MOS-SIAM series on optimization. SIAM, Philadelphia
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265
Soyster AL (1973) Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper Res 21(5):1154–1157
Sungur I, Ordóñez F, Dessouky M (2008) A robust optimization approach for the capacited vehicle routing problem with demand uncertainty. IIE Trans 40:509–523
Thiele A, Terry T, Epelman M (2009) Robust linear optimization with recourse. Technical report pp 4–37
Zeng B, Zhao L (2013) Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper Res Lett 41(5):457–461
Acknowledgements
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions of revision, and CNPq and FAPESP - São Paulo Research Foundation (Projects 2015/14582-7 and 2013/07375-0) for the financial support provided to develop this study.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
De La Vega, J., Munari, P. & Morabito, R. Robust optimization for the vehicle routing problem with multiple deliverymen. Cent Eur J Oper Res 27, 905–936 (2019). https://doi.org/10.1007/s10100-017-0511-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-017-0511-x