IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v54y2020i2p400-416.html
   My bibliography  Save this article

Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows

Author

Listed:
  • Maaike Hoogeboom

    (Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands)

  • Wout Dullaert

    (Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands)

  • David Lai

    (Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands)

  • Daniele Vigo

    (Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands; Department of Electrical, Electronic and Information Engineering “Guglielmo Marconi,” University of Bologna, 40136 Bologna, Italy)

Abstract

In the vehicle routing problem with multiple time windows (VRPMTW), a single time window must be selected for each customer from the multiple time windows provided. Compared with classical vehicle routing problems with only a single time window per customer, multiple time windows increase the complexity of the routing problem. To minimize the duration of any given route, we present an exact polynomial time algorithm to efficiently determine the optimal start time for servicing each customer. The proposed algorithm has a reduced worst-case and average complexity than existing exact algorithms. Furthermore, the proposed exact algorithm can be used to efficiently evaluate neighborhood operations during a local search resulting in significant acceleration. To examine the benefits of exact neighborhood evaluations and to solve the VRPMTW, the proposed algorithm is embedded in a simple metaheuristic framework generating numerous new best known solutions at competitive computation times.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:54:y:2020:i:2:p:400-416
    DOI: 10.1287/trsc.2019.0912
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2019.0912
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2019.0912?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
    ---><---

    References listed on IDEAS

    as
    1. Asvin Goel & Leendert Kok, 2012. "Truck Driver Scheduling in the United States," Transportation Science, INFORMS, vol. 46(3), pages 317-326, August.
    2. 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.
    3. 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.
    4. Pesant, Gilles & Gendreau, Michel & Potvin, Jean-Yves & Rousseau, Jean-Marc, 1999. "On the flexibility of constraint programming models: From single to multiple time windows for the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 117(2), pages 253-263, September.
    5. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    6. 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.
    7. 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.
    8. Maria Battarra & Güneş Erdoğan & Daniele Vigo, 2014. "Exact Algorithms for the Clustered Vehicle Routing Problem," Operations Research, INFORMS, vol. 62(1), pages 58-71, February.
    9. 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.
    10. Marie-Eve Rancourt & Jean-François Cordeau & Gilbert Laporte, 2013. "Long-Haul Vehicle Routing and Scheduling with Working Hour Rules," Transportation Science, INFORMS, vol. 47(1), pages 81-107, February.
    11. Hoogeboom, Maaike & Dullaert, Wout, 2019. "Vehicle routing with arrival time diversification," European Journal of Operational Research, Elsevier, vol. 275(1), pages 93-107.
    12. Wouter Souffriau & Pieter Vansteenwegen & Greet Vanden Berghe & Dirk Van Oudheusden, 2013. "The Multiconstraint Team Orienteering Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 47(1), pages 53-63, February.
    13. 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).
    14. 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.
    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. Fei Peng & Xian Fan & Puxin Wang & Mingan Sheng, 2022. "A Time-Space Network-Based Optimization Method for Scheduling Depot Drivers," Sustainability, MDPI, vol. 14(21), pages 1-19, November.
    2. Kangye Tan & Yihui Tian & Fang Xu & Chunsheng Li, 2023. "Research on Multi-Objective Optimal Scheduling for Power Battery Reverse Supply Chain," Mathematics, MDPI, vol. 11(4), pages 1-26, February.
    3. Arjun Paul & Ravi Shankar Kumar & Chayanika Rout & Adrijit Goswami, 2021. "A bi-objective two-echelon pollution routing problem with simultaneous pickup and delivery under multiple time windows constraint," OPSEARCH, Springer;Operational Research Society of India, vol. 58(4), pages 962-993, December.
    4. Tao Yang & Weixin Wang & Qiqi Wu, 2022. "Fuzzy Demand Vehicle Routing Problem with Soft Time Windows," Sustainability, MDPI, vol. 14(9), pages 1-14, May.
    5. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    6. Özarık, Sami Serkan & Veelenturf, Lucas P. & Woensel, Tom Van & Laporte, Gilbert, 2021. "Optimizing e-commerce last-mile vehicle routing and scheduling under uncertain customer presence," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 148(C).

    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. 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.
    2. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    3. 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.
    4. 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.
    5. 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.
    6. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    7. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    8. Jean-Yves Potvin, 2009. "State-of-the Art Review ---Evolutionary Algorithms for Vehicle Routing," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 518-548, November.
    9. 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.
    10. Özarık, Sami Serkan & Veelenturf, Lucas P. & Woensel, Tom Van & Laporte, Gilbert, 2021. "Optimizing e-commerce last-mile vehicle routing and scheduling under uncertain customer presence," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 148(C).
    11. Drexl, M. & Schneider, M., 2014. "A Survey of the Standard Location-Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65940, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    12. Hoogeboom, Maaike & Dullaert, Wout, 2019. "Vehicle routing with arrival time diversification," European Journal of Operational Research, Elsevier, vol. 275(1), pages 93-107.
    13. 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.
    14. 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.
    15. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    16. Zhenzhen Zhang & Zhixing Luo & Hu Qin & Andrew Lim, 2019. "Exact Algorithms for the Vehicle Routing Problem with Time Windows and Combinatorial Auction," Transportation Science, INFORMS, vol. 53(2), pages 427-441, March.
    17. S. Irnich, 2008. "A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 270-287, May.
    18. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    19. 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.
    20. 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.

    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:inm:ortrsc:v:54:y:2020:i:2:p:400-416. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.