IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/100852.html
   My bibliography  Save this paper

Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems

Author

Listed:
  • Visser, T.R.
  • Spliet, R.

Abstract

In this paper we introduce several new methods for efficiently evaluating moves in neighborhood search heuristics for routing problems with time-dependent travel times. We consider both the case that route duration is constrained and the case that route duration appears in the objective. We observe that the composition of piecewise linear functions can be evaluated in various orders when computing the route duration. We use this to develop a new tree based data structure to improve the complexity of computations and memory usage. This also allows us to present methods that have the best known computational complexity, while they do not even require a lexicographic order of search. Our numerical experiments illustrate the trade-off between computation time and memory usage among the different methods. On 1000 customer instances, our methods are able to speed-up a construction heuristic by up to 8.89 times and an exchange neighborhood improvement heuristic by up to 3.94 times, without requiring excessive amounts of memory.

Suggested Citation

  • Visser, T.R. & Spliet, R., 2017. "Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems," Econometric Institute Research Papers EI2017-23, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    • Handle: RePEc:ems:eureir:100852
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/100852/EI2017-23.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Ann Melissa Campbell & Martin Savelsbergh, 2004. "Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems," Transportation Science, INFORMS, vol. 38(3), pages 369-378, August.
    2. 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.
    3. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    4. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    5. Kok, A.L. & Hans, E.W. & Schutten, J.M.J., 2011. "Optimizing departure times in vehicle routes," European Journal of Operational Research, Elsevier, vol. 210(3), pages 579-587, May.
    6. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    7. Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P., 2014. "A fast solution method for the time-dependent orienteering problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 419-432.
    8. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    9. Gianpaolo Ghiani & Emanuela Guerriero, 2014. "A Note on the Ichoua, Gendreau, and Potvin (2003) Travel Time Model," Transportation Science, INFORMS, vol. 48(3), pages 458-462, August.
    10. Donati, Alberto V. & Montemanni, Roberto & Casagrande, Norman & Rizzoli, Andrea E. & Gambardella, Luca M., 2008. "Time dependent vehicle routing problem with a multi ant colony system," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1174-1191, March.
    11. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.
    12. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    13. 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.
    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. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2020. "Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    2. Tom Woensel, 2019. "Comments on: Perspectives on integer programming for time-dependent models," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 180-183, July.
    3. Jean Bertrand Gauthier & Stefan Irnich, 2020. "Inter-Depot Moves and Dynamic-Radius Search for Multi-Depot Vehicle Routing Problems," Working Papers 2004, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. Bettinelli, Andrea & Cacchiani, Valentina & Crainic, Teodor Gabriel & Vigo, Daniele, 2019. "A Branch-and-Cut-and-Price algorithm for the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities," European Journal of Operational Research, Elsevier, vol. 279(3), pages 824-839.

    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. Thomas R. Visser & Remy Spliet, 2020. "Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems," Transportation Science, INFORMS, vol. 54(4), pages 1091-1112, July.
    2. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    3. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    4. Sun, Peng & Veelenturf, Lucas P. & Dabia, Said & Van Woensel, Tom, 2018. "The time-dependent capacitated profitable tour problem with time windows and precedence constraints," European Journal of Operational Research, Elsevier, vol. 264(3), pages 1058-1073.
    5. Hamza Ben Ticha & Nabil Absi & Dominique Feillet & Alain Quilliot & Tom Woensel, 2021. "The Time-Dependent Vehicle Routing Problem with Time Windows and Road-Network Information," SN Operations Research Forum, Springer, vol. 2(1), pages 1-25, March.
    6. 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.
    7. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    8. Gmira, Maha & Gendreau, Michel & Lodi, Andrea & Potvin, Jean-Yves, 2021. "Tabu search for the time-dependent vehicle routing problem with time windows on a road network," European Journal of Operational Research, Elsevier, vol. 288(1), pages 129-140.
    9. Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P., 2014. "A fast solution method for the time-dependent orienteering problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 419-432.
    10. 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.
    11. Rincon-Garcia, Nicolas & Waterson, Ben & Cherrett, Tom J. & Salazar-Arrieta, Fernando, 2020. "A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations – An application in city logistics," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 429-446.
    12. Cédric Verbeeck & Pieter Vansteenwegen & El-Houssaine Aghezzaf, 2017. "The time-dependent orienteering problem with time windows: a fast ant colony system," Annals of Operations Research, Springer, vol. 254(1), pages 481-505, July.
    13. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    14. Rifki, Omar & Chiabaut, Nicolas & Solnon, Christine, 2020. "On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    15. Aarabi, Fatemeh & Batta, Rajan, 2020. "Scheduling spatially distributed jobs with degradation: Application to pothole repair," Socio-Economic Planning Sciences, Elsevier, vol. 72(C).
    16. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    17. Thibaut Vidal & Rafael Martinelli & Tuan Anh Pham & Minh Hoàng Hà, 2021. "Arc Routing with Time-Dependent Travel Times and Paths," Transportation Science, INFORMS, vol. 55(3), pages 706-724, May.
    18. Markus Sinnl, 2021. "Mixed-integer programming approaches for the time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(2), pages 497-542, June.
    19. 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.
    20. Jan Mikula & Miroslav Kulich, 2022. "Solving the traveling delivery person problem with limited computational time," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(4), pages 1451-1481, December.

    More about this item

    Keywords

    Vehicle Routing Problems; Neighborhood Search; Feasibility Check; Time-dependent Travel; Times; First-in-first-out; Duration constraints;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:ems:eureir:100852. 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: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.