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

Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching

Author

Listed:
  • Michel Gendreau

    (Centre de recherche sur les transports and Département d'informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succ. Centre-ville, Montréal, Québec H3C 3J7, Canada)

  • François Guertin

    (Centre de recherche sur les transports, Université de Montréal, C.P. 6128, succ. Centre-ville, Montréal, Québec H3C 3J7, Canada)

  • Jean-Yves Potvin

    (Centre de recherche sur les transports and Département d'informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succ. Centre-ville, Montréal, Québec H3C 3J7, Canada)

  • Éric Taillard

    (Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), Corso Elvezia 36, CH-6900 Lugano, Switzerland)

Abstract

An abundant literature about vehicle routing and scheduling problems is available in the scientific community. However, a large fraction of this work deals with static problems where all data are known before the routes are constructed. Recent technological advances now create environments where decisions are taken quickly, using new or updated information about the current routing situation. This paper describes such a dynamic problem, motivated from courier service applications, where customer requests with soft time windows must be dispatched in real time to a fleet of vehicles in movement. A tabu search heuristic, initially designed for the static version of the problem, has been adapted to the dynamic case and implemented on a parallel platform to increase the computational effort. Numerical results are reported using different request arrival rates, and comparisons are established with other heuristic methods.

Suggested Citation

  • Michel Gendreau & François Guertin & Jean-Yves Potvin & Éric Taillard, 1999. "Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching," Transportation Science, INFORMS, vol. 33(4), pages 381-390, November.
    • Handle: RePEc:inm:ortrsc:v:33:y:1999:i:4:p:381-390
    DOI: 10.1287/trsc.33.4.381
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.33.4.381
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.33.4.381?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. Moshe Dror & Warren Powell, 1993. "Stochastic and Dynamic Models in Transportation," Operations Research, INFORMS, vol. 41(1), pages 11-14, February.
    2. Éric Taillard & Philippe Badeau & Michel Gendreau & François Guertin & Jean-Yves Potvin, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 31(2), pages 170-186, May.
    3. 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)

    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. Sébastien Mouthuy & Florence Massen & Yves Deville & Pascal Van Hentenryck, 2015. "A Multistage Very Large-Scale Neighborhood Search for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 49(2), pages 223-238, May.
    2. Ioannou, George & Kritikos, Manolis & Prastacos, Gregory, 2003. "A problem generator-solver heuristic for vehicle routing with soft time windows," Omega, Elsevier, vol. 31(1), pages 41-53, February.
    3. Hideki Hashimoto & Mutsunori Yagiura & Shinji Imahori & Toshihide Ibaraki, 2013. "Recent progress of local search in handling the time window constraints of the vehicle routing problem," Annals of Operations Research, Springer, vol. 204(1), pages 171-187, April.
    4. Surya Sahoo & Seongbae Kim & Byung-In Kim & Bob Kraas & Alexander Popov, 2005. "Routing Optimization for Waste Management," Interfaces, INFORMS, vol. 35(1), pages 24-36, February.
    5. Lagos, Felipe & Pereira, Jordi, 2024. "Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 312(1), pages 70-91.
    6. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    7. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    8. 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.
    9. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    10. Cruijssen, F. & Braysy, O. & Dullaert, W. & Fleuren, H.A. & Salomon, M., 2006. "Joint Route Planning under Varying Market Conditions," Discussion Paper 2006-49, Tilburg University, Center for Economic Research.
    11. Sana Jawarneh & Salwani Abdullah, 2015. "Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-23, July.
    12. Tung, Dang Vu & Pinnoi, Anulark, 2000. "Vehicle routing-scheduling for waste collection in Hanoi," European Journal of Operational Research, Elsevier, vol. 125(3), pages 449-468, September.
    13. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    14. Z Fu & R Eglese & L Y O Li, 2008. "A unified tabu search algorithm for vehicle routing problems with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 663-673, May.
    15. Lau, Hoong Chuin & Sim, Melvyn & Teo, Kwong Meng, 2003. "Vehicle routing problem with time windows and a limited number of vehicles," European Journal of Operational Research, Elsevier, vol. 148(3), pages 559-569, August.
    16. Okitonyumbe Y.F., Joseph & Ulungu, Berthold E.-L. & Kapiamba Nt., Joel, 2015. "Cobweb Heuristic for solving Multi-Objective Vehicle Routing Problem," MPRA Paper 66121, University Library of Munich, Germany.
    17. 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.
    18. José Brandão, 2017. "Iterated Local Search Algorithm for the Vehicle Routing Problem with Backhauls and Soft Time Windows," Working Papers REM 2017/10, ISEG - Lisbon School of Economics and Management, REM, Universidade de Lisboa.
    19. Schneider, M., 2016. "The vehicle-routing problem with time windows and driver-specific times," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65941, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    20. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.

    More about this item

    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:inm:ortrsc:v:33:y:1999:i:4:p:381-390. 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.