IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v129y2019icp263-286.html
   My bibliography  Save this article

Rich vehicle routing problem with last-mile outsourcing decisions

Author

Listed:
  • Alcaraz, Juan J.
  • Caballero-Arnaldos, Luis
  • Vales-Alonso, Javier

Abstract

This paper addresses a Rich Vehicle Routing Problem (RVRP) characterized by the following attributes: long-haul transport, driver hours regulation, incompatibility among goods, multiple depots and pickup locations, heterogeneous vehicles, time windows, and outsourcing decisions for last-mile delivery. Addressing the latter aspect is especially challenging, since it requires substantial changes in the algorithms for generating initial feasible solutions (construction heuristic) and for modifying existing solutions (improvement heuristics). Our work develops new heuristics adapted to the above attributes, and evaluates their performance in combination with common solving metaheuristics. We also assess the impact and the cost-effectiveness of the outsourcing attribute.

Suggested Citation

  • Alcaraz, Juan J. & Caballero-Arnaldos, Luis & Vales-Alonso, Javier, 2019. "Rich vehicle routing problem with last-mile outsourcing decisions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 129(C), pages 263-286.
    • Handle: RePEc:eee:transe:v:129:y:2019:i:c:p:263-286
    DOI: 10.1016/j.tre.2019.08.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554519302339
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2019.08.004?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    2. Rahma Lahyani & Anne-Lise Gouguenheim & Leandro C. Coelho, 2019. "A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems," International Journal of Production Research, Taylor & Francis Journals, vol. 57(22), pages 6963-6976, November.
    3. Andreas Stenger & Daniele Vigo & Steffen Enz & Michael Schwind, 2013. "An Adaptive Variable Neighborhood Search Algorithm for a Vehicle Routing Problem Arising in Small Package Shipping," Transportation Science, INFORMS, vol. 47(1), pages 64-80, February.
    4. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    5. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    6. Sotiris P. Gayialis & Grigorios D. Konstantakopoulos & Ilias P. Tatsiopoulos, 2019. "Vehicle Routing Problem for Urban Freight Transportation: A Review of the Recent Literature," Springer Proceedings in Business and Economics, in: Angelo Sifaleras & Konstantinos Petridis (ed.), Operational Research in the Digital Era – ICT Challenges, pages 89-104, Springer.
    7. A. L. Kok & C. M. Meyer & H. Kopfer & J. M. J. Schutten, 2010. "A Dynamic Programming Heuristic for the Vehicle Routing Problem with Time Windows and European Community Social Legislation," Transportation Science, INFORMS, vol. 44(4), pages 442-454, November.
    8. Hanson, Robin & Finnsgård, Christian, 2014. "Impact of unit load size on in-plant materials supply efficiency," International Journal of Production Economics, Elsevier, vol. 147(PA), pages 46-52.
    9. Asvin Goel, 2009. "Vehicle Scheduling and Routing with Drivers' Working Hours," Transportation Science, INFORMS, vol. 43(1), pages 17-26, February.
    10. Irnich, S. & Schneider, M. & Vigo, D., 2014. "Four Variants of the Vehicle Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63514, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    11. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    12. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    13. Belfiore, PatrI´cia & Yoshida Yoshizaki, Hugo Tsugunobu, 2009. "Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil," European Journal of Operational Research, Elsevier, vol. 199(3), pages 750-758, December.
    14. Alberto Ceselli & Giovanni Righini & Matteo Salani, 2009. "A Column Generation Algorithm for a Rich Vehicle-Routing Problem," Transportation Science, INFORMS, vol. 43(1), pages 56-69, February.
    15. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    16. Atefi, Reza & Salari, Majid & C. Coelho, Leandro & Renaud, Jacques, 2018. "The open vehicle routing problem with decoupling points," European Journal of Operational Research, Elsevier, vol. 265(1), pages 316-327.
    17. Eric Prescott-Gagnon & Guy Desaulniers & Michael Drexl & Louis-Martin Rousseau, 2010. "European Driver Rules in Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 44(4), pages 455-473, November.
    18. Uchoa, Eduardo & Pecin, Diego & Pessoa, Artur & Poggi, Marcus & Vidal, Thibaut & Subramanian, Anand, 2017. "New benchmark instances for the Capacitated Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 257(3), pages 845-858.
    19. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    20. Gahm, Christian & Brabänder, Christian & Tuma, Axel, 2017. "Vehicle routing with private fleet, multiple common carriers offering volume discounts, and rental options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 192-216.
    21. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "A comparison of three idling options in long-haul truck scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 631-647.
    22. Goel, Asvin, 2018. "Legal aspects in road transport optimization in Europe," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 144-162.
    23. Paolo Toth & Daniele Vigo, 2003. "The Granular Tabu Search and Its Application to the Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 333-346, November.
    24. Rabbani, M. & Heidari, R. & Yazdanparast, R., 2019. "A stochastic multi-period industrial hazardous waste location-routing problem: Integrating NSGA-II and Monte Carlo simulation," European Journal of Operational Research, Elsevier, vol. 272(3), pages 945-961.
    25. Goel, Asvin & Gruhn, Volker, 2008. "A General Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 650-660, December.
    26. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    27. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mayerle, Sérgio Fernando & De Genaro Chiroli, Daiane Maria & Neiva de Figueiredo, João & Rodrigues, Hidelbrando Ferreira, 2020. "The long-haul full-load vehicle routing and truck driver scheduling problem with intermediate stops: An economic impact evaluation of Brazilian policy," Transportation Research Part A: Policy and Practice, Elsevier, vol. 140(C), pages 36-51.
    2. Amira Saker & Amr Eltawil & Islam Ali, 2023. "Adaptive Large Neighborhood Search Metaheuristic for the Capacitated Vehicle Routing Problem with Parcel Lockers," Logistics, MDPI, vol. 7(4), pages 1-27, October.
    3. Naihui Wang & Yulong Pei & Hao Fu, 2022. "Public Acceptance of Last-Mile Shuttle Bus Services with Automation and Electrification in Cold-Climate Environments," Sustainability, MDPI, vol. 14(21), pages 1-16, November.
    4. Nadia Giuffrida & Jenny Fajardo-Calderin & Antonio D. Masegosa & Frank Werner & Margarete Steudter & Francesco Pilla, 2022. "Optimization and Machine Learning Applied to Last-Mile Logistics: A Review," Sustainability, MDPI, vol. 14(9), pages 1-16, April.
    5. Hess, Alexander & Spinler, Stefan & Winkenbach, Matthias, 2021. "Real-time demand forecasting for an urban delivery platform," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    6. Alcaraz, Juan J. & Losilla, Fernando & Caballero-Arnaldos, Luis, 2022. "Online model-based reinforcement learning for decision-making in long distance routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    7. Daiane Maria Genaro Chiroli & Sérgio Fernando Mayerle & João Neiva Figueiredo, 2022. "Using state-space shortest-path heuristics to solve the long-haul point-to-point vehicle routing and driver scheduling problem subject to hours-of-service regulatory constraints," Journal of Heuristics, Springer, vol. 28(1), pages 23-59, February.
    8. Sun, Yanshuo & Kirtonia, Sajeeb & Chen, Zhi-Long, 2021. "A survey of finished vehicle distribution and related problems from an optimization perspective," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    9. Yang, Fei & Dai, Ying & Ma, Zu-Jun, 2020. "A cooperative rich vehicle routing problem in the last-mile logistics industry in rural areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    10. Su, E. & Qin, Hu & Li, Jiliu & Pan, Kai, 2023. "An exact algorithm for the pickup and delivery problem with crowdsourced bids and transshipment," Transportation Research Part B: Methodological, Elsevier, vol. 177(C).
    11. Subrat Sarangi & Sudipta Sarangi & Nasim S. Sabounchi, 2023. "How managerial perspectives affect the optimal fleet size and mix model: a multi-objective approach," OPSEARCH, Springer;Operational Research Society of India, vol. 60(1), pages 1-23, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Schneider, Michael, 2016. "The vehicle-routing problem with time windows and driver-specific times," European Journal of Operational Research, Elsevier, vol. 250(1), pages 101-119.
    2. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    3. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    4. Puca Huachi Vaz Penna & Anand Subramanian & Luiz Satoru Ochi & Thibaut Vidal & Christian Prins, 2019. "A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet," Annals of Operations Research, Springer, vol. 273(1), pages 5-74, February.
    5. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    6. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    7. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    8. Tilk, Christian & Goel, Asvin, 2020. "Bidirectional labeling for solving vehicle routing and truck driver scheduling problems," European Journal of Operational Research, Elsevier, vol. 283(1), pages 108-124.
    9. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    10. Schneider, Michael & Schwahn, Fabian & Vigo, Daniele, 2017. "Designing granular solution methods for routing problems with time windows," European Journal of Operational Research, Elsevier, vol. 263(2), pages 493-509.
    11. Daiane Maria Genaro Chiroli & Sérgio Fernando Mayerle & João Neiva Figueiredo, 2022. "Using state-space shortest-path heuristics to solve the long-haul point-to-point vehicle routing and driver scheduling problem subject to hours-of-service regulatory constraints," Journal of Heuristics, Springer, vol. 28(1), pages 23-59, February.
    12. Asvin Goel & Thibaut Vidal & Adrianus Leendert Kok, 2021. "To team up or not: single versus team driving in European road freight transport," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 879-913, December.
    13. Ostermeier, Manuel, 2024. "The supply of convenience stores: Challenges of short-distance routing within the constraints of working time regulations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 997-1012.
    14. Maaike Hoogeboom & Wout Dullaert & David Lai & Daniele Vigo, 2020. "Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 54(2), pages 400-416, March.
    15. Christian Tilk & Asvin Goel, 2019. "Bidirectional labeling for solving vehicle routing and truck driver scheduling problems," Working Papers 1914, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. Goel, Asvin, 2018. "Legal aspects in road transport optimization in Europe," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 144-162.
    17. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    18. Ehmke, Jan Fabian & Campbell, Ann Melissa & Urban, Timothy L., 2015. "Ensuring service levels in routing problems with time windows and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 240(2), pages 539-550.
    19. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    20. Asvin Goel & Stefan Irnich, 2017. "An Exact Method for Vehicle Routing and Truck Driver Scheduling Problems," Transportation Science, INFORMS, vol. 51(2), pages 737-754, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:129:y:2019:i:c:p:263-286. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.