IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v214y2011i2p442-452.html
   My bibliography  Save this article

A tabu search heuristic for the dynamic transportation of patients between care units

Author

Listed:
  • Kergosien, Y.
  • Lenté, Ch.
  • Piton, D.
  • Billaut, J.-C.

Abstract

The problem studied in this paper stems from a real application to the transportation of patients in the Hospital Complex of Tours (France). The ambulance central station of the Hospital Complex has to plan the transportation demands between care units which require a vehicle. Some demands are known in advance and the others arise dynamically. Each demand requires a specific type of vehicle and a vehicle can transport only one person at a time. The demands can be subcontracted to a private company which implies high cost. Moreover, transportations are subject to particular constraints, among them priority of urgent demands, disinfection of a vehicle after the transportation of a patient with contagious disease and respect of the type of vehicle needed. These characteristics involve a distinction between the vehicles and the crews during the modeling phase. We propose a modeling for solving this difficult problem and a tabu search algorithm inspired by Gendreau et al. (1999). This method supports an adaptive memory and a tabu search procedure. Computational experiments on a real-life instance and on randomly generated instances show that the method can provide high-quality solutions for this dynamic problem with a short computation time.

Suggested Citation

  • Kergosien, Y. & Lenté, Ch. & Piton, D. & Billaut, J.-C., 2011. "A tabu search heuristic for the dynamic transportation of patients between care units," European Journal of Operational Research, Elsevier, vol. 214(2), pages 442-452, October.
  • Handle: RePEc:eee:ejores:v:214:y:2011:i:2:p:442-452
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711003778
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 14(2), pages 130-154, May.
    2. 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.
    3. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    4. Irina Ioachim & Jacques Desrosiers & Yvan Dumas & Marius M. Solomon & Daniel Villeneuve, 1995. "A Request Clustering Algorithm for Door-to-Door Handicapped Transportation," Transportation Science, INFORMS, vol. 29(1), pages 63-78, February.
    5. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    6. David M. Stein, 1978. "An Asymptotic, Probabilistic Analysis of a Routing Problem," Mathematics of Operations Research, INFORMS, vol. 3(2), pages 89-101, May.
    7. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    8. Jaw, Jang-Jei & Odoni, Amedeo R. & Psaraftis, Harilaos N. & Wilson, Nigel H. M., 1986. "A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 20(3), pages 243-257, June.
    9. Ghiani, Gianpaolo & Guerriero, Francesca & Laporte, Gilbert & Musmanno, Roberto, 2003. "Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies," European Journal of Operational Research, Elsevier, vol. 151(1), pages 1-11, November.
    10. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2000. "Diversion Issues in Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 34(4), pages 426-438, November.
    11. Thomas Hanne & Teresa Melo & Stefan Nickel, 2009. "Bringing Robustness to Patient Flow Management Through Optimized Patient Transports in Hospitals," Interfaces, INFORMS, vol. 39(3), pages 241-255, June.
    12. Coslovich, Luca & Pesenti, Raffaele & Ukovich, Walter, 2006. "A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1605-1615, December.
    13. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2008. "The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments," European Journal of Operational Research, Elsevier, vol. 185(2), pages 534-551, March.
    14. É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.
    15. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    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. 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.
    2. Oscar Chávez-Bosquez & José Hernández-Torruco & Betania Hernández-Ocaña & Juana Canul-Reich, 2020. "Modeling and Solving a Latin American University Course Timetabling Problem Instance," Mathematics, MDPI, vol. 8(10), pages 1-29, October.
    3. Fröhlich von Elmbach, Alexander & Scholl, Armin & Walter, Rico, 2019. "Minimizing the maximal ergonomic burden in intra-hospital patient transportation," European Journal of Operational Research, Elsevier, vol. 276(3), pages 840-854.
    4. Ammann, Pia & Kolisch, Rainer & Schiffer, Maximilian, 2023. "Driver routing and scheduling with synchronization constraints," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    5. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    6. P. L. van den Berg & J. T. van Essen, 2019. "Scheduling Non-Urgent Patient Transportation While Maximizing Emergency Coverage," Transportation Science, INFORMS, vol. 53(2), pages 492-509, March.
    7. Farshad Majzoubi & Lihui Bai & Sunderesh S. Heragu, 2021. "The EMS vehicle patient transportation problem during a demand surge," Journal of Global Optimization, Springer, vol. 79(4), pages 989-1006, April.
    8. Farzaneh Karami & Wim Vancroonenburg & Greet Vanden Berghe, 2020. "A periodic optimization approach to dynamic pickup and delivery problems with time windows," Journal of Scheduling, Springer, vol. 23(6), pages 711-731, December.
    9. Luscombe, Ruth & Kozan, Erhan, 2016. "Dynamic resource allocation to improve emergency department efficiency in real time," European Journal of Operational Research, Elsevier, vol. 255(2), pages 593-603.
    10. Melo, Teresa, 2012. "A note on challenges and opportunities for Operations Research in hospital logistics," Technical Reports on Logistics of the Saarland Business School 2, Saarland University of Applied Sciences (htw saar), Saarland Business School.
    11. Ananya Christman & William Forcier & Aayam Poudel, 2018. "From theory to practice: maximizing revenues for on-line dial-a-ride," Journal of Combinatorial Optimization, Springer, vol. 35(2), pages 512-529, February.
    12. Christian Tilk & Nicola Bianchessi & Michael Drexl & Stefan Irnich & Frank Meisel, 2015. "Branch-and-Price for the Active-Passive Vehicle-Routing Problem," Working Papers 1513, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    13. Keyong Lin & S. Nurmaya Musa & Hwa Jen Yap, 2022. "Vehicle Routing Optimization for Pandemic Containment: A Systematic Review on Applications and Solution Approaches," Sustainability, MDPI, vol. 14(4), pages 1-27, February.
    14. Christian Tilk & Nicola Bianchessi & Michael Drexl & Stefan Irnich & Frank Meisel, 2018. "Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem," Transportation Science, INFORMS, vol. 52(2), pages 300-319, 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. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    2. Häme, Lauri, 2011. "An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows," European Journal of Operational Research, Elsevier, vol. 209(1), pages 11-22, February.
    3. 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.
    4. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    5. Hosni, Hadi & Naoum-Sawaya, Joe & Artail, Hassan, 2014. "The shared-taxi problem: Formulation and solution methods," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 303-318.
    6. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    7. Paquette, Julie & Cordeau, Jean-François & Laporte, Gilbert & Pascoal, Marta M.B., 2013. "Combining multicriteria analysis and tabu search for dial-a-ride problems," Transportation Research Part B: Methodological, Elsevier, vol. 52(C), pages 1-16.
    8. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    9. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    10. Sheridan, Patricia Kristine & Gluck, Erich & Guan, Qi & Pickles, Thomas & Balcıog˜lu, Barış & Benhabib, Beno, 2013. "The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 49(C), pages 178-194.
    11. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    12. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    13. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    14. Hua, Shijia & Zeng, Wenjia & Liu, Xinglu & Qi, Mingyao, 2022. "Optimality-guaranteed algorithms on the dynamic shared-taxi problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    15. Shangyao Yan & Chun-Ying Chen & Chuan-Che Wu, 2012. "Solution methods for the taxi pooling problem," Transportation, Springer, vol. 39(3), pages 723-748, May.
    16. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    17. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2008. "The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments," European Journal of Operational Research, Elsevier, vol. 185(2), pages 534-551, March.
    18. Lian, Ying & Lucas, Flavien & Sörensen, Kenneth, 2024. "Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system," European Journal of Operational Research, Elsevier, vol. 312(1), pages 338-356.
    19. Sharif Azadeh, Sh. & Atasoy, Bilge & Ben-Akiva, Moshe E. & Bierlaire, M. & Maknoon, M.Y., 2022. "Choice-driven dial-a-ride problem for demand responsive mobility service," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 128-149.
    20. Rui Yao & Shlomo Bekhor, 2021. "A Dynamic Tree Algorithm for Peer-to-Peer Ridesharing Matching," Networks and Spatial Economics, Springer, vol. 21(4), pages 801-837, December.

    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:ejores:v:214:y:2011:i:2:p:442-452. 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/locate/eor .

    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.