User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

A Constraint Programming Approach for Solving Patient Transportation Problems

Primary tabs

download
  • Open access
  • PDF
  • 854.21 K
Cappart, Quentin Thomas, Charles [UCL] Schaus, Pierre [UCL] Rousseau, Louis-Martin

The Patient Transportation Problem (PTP) aims to bring patients to health centers and to take them back home once the care has been delivered. All the requests are known beforehand and a schedule is built the day before its use. It is a variant of the well-known Dial-a-Ride Problem (DARP) but it has nevertheless some characteristics that complicate the decision process. Three levels of decisions are considered: selecting which requests to service, assigning vehicles to requests and routing properly the vehicles. In this paper, we propose a Constraint Programming approach to solve the Patient Transportation Problem. The model is designed to be flexible enough to accommodate new constraints and objective functions. Furthermore, we introduce a generic search strategy to maximize efficiently the number of selected requests. Our results show that the model can solve real life instances and outperforms greedy strategies typically performed by human schedulers.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès libre
Publication date 2018
Language Anglais
Conference "CP: International Conference on Principles and Practice of Constraint Programming", Lille (du 27/08/2018 au 31/08/2018)
Peer reviewed yes
Host document "Lecture Notes in Computer Science : Principles and Practice of Constraint Programming"- p. 490-506 (ISBN : 9783319983332)
Collection Principles and Practice of Constraint Programming, 24th International Conference, CP 2018, Lille, France, August 27-31, 2018 - 11008 (ISSN : 1611-3349)
Publisher John Hooker
Publication status Publié
Affiliation UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Links
  1. Cordeau Jean-François, Laporte Gilbert, The dial-a-ride problem: models and algorithms, 10.1007/s10479-007-0170-8
  2. Melachrinoudis Emanuel, Min Hokey, A tabu search heuristic for solving the multi-depot, multi-vehicle, double request dial-a-ride problem faced by a healthcare organisation, 10.1504/ijor.2011.038585
  3. Liu Ran, Xie Xiaolan, Augusto Vincent, Rodriguez Carlos, Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, 10.1016/j.ejor.2013.04.044
  4. Detti Paolo, Papalini Francesco, Lara Garazi Zabalo Manrique de, A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare, 10.1016/j.omega.2016.08.008
  5. Cordeau Jean-François, Laporte Gilbert, A tabu search heuristic for the static multi-vehicle dial-a-ride problem, 10.1016/s0191-2615(02)00045-0
  6. Parragh Sophie N., Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem, 10.1016/j.trc.2010.06.002
  7. Parragh Sophie N., Cordeau Jean-François, Doerner Karl F., Hartl Richard F., Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints, 10.1007/s00291-010-0229-9
  8. Psaraftis Harilaos N., An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows, 10.1287/trsc.17.3.351
  9. Melachrinoudis Emanuel, Ilhan Ahmet B., Min Hokey, A dial-a-ride problem for client transportation in a health-care organization, 10.1016/j.cor.2005.03.024
  10. Cordeau Jean-Fran�ois, Gendreau Michel, Laporte Gilbert, A tabu search heuristic for periodic and multi-depot vehicle routing problems, 10.1002/(sici)1097-0037(199709)30:2<105::aid-net5>3.0.co;2-g
  11. Parragh Sophie N., Doerner Karl F., Hartl Richard F., Gandibleux Xavier, A heuristic two-phase solution approach for the multi-objective dial-a-ride problem, 10.1002/net.20335
  12. Berbeglia Gerardo, Cordeau Jean-François, Gribkovskaia Irina, Laporte Gilbert, Static pickup and delivery problems: a classification scheme and survey, 10.1007/s11750-007-0009-0
  13. Attanasio Andrea, Cordeau Jean-François, Ghiani Gianpaolo, Laporte Gilbert, Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem, 10.1016/j.parco.2003.12.001
  14. Berbeglia Gerardo, Pesant Gilles, Rousseau Louis-Martin, Checking the Feasibility of Dial-a-Ride Instances Using Constraint Programming, 10.1287/trsc.1100.0336
  15. Berbeglia Gerardo, Cordeau Jean-François, Laporte Gilbert, A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem, 10.1287/ijoc.1110.0454
  16. Parragh Sophie N., Schmid Verena, Hybrid column generation and large neighborhood search for the dial-a-ride problem, 10.1016/j.cor.2012.08.004
  17. Jain Siddhartha, Van Hentenryck Pascal, Large Neighborhood Search for Dial-a-Ride Problems, Principles and Practice of Constraint Programming – CP 2011 (2011) ISBN:9783642237850 p.400-413, 10.1007/978-3-642-23786-7_31
  18. Liu Chang, Aleman Dionne M., Beck J. Christopher, Modelling and Solving the Senior Transportation Problem, Integration of Constraint Programming, Artificial Intelligence, and Operations Research (2018) ISBN:9783319930305 p.412-428, 10.1007/978-3-319-93031-2_30
  19. Beldiceanu, N., Carlsson, M., Rampon, J.X.: Global constraint catalog, (revision a) (2012)
  20. Gay Steven, Hartert Renaud, Schaus Pierre, Simple and Scalable Time-Table Filtering for the Cumulative Constraint, Lecture Notes in Computer Science (2015) ISBN:9783319232188 p.149-157, 10.1007/978-3-319-23219-5_11
  21. Vilím Petr, Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2011) ISBN:9783642213106 p.230-245, 10.1007/978-3-642-21311-3_22
  22. Gay Steven, Hartert Renaud, Schaus Pierre, Time-Table Disjunctive Reasoning for the Cumulative Constraint, Integration of AI and OR Techniques in Constraint Programming (2015) ISBN:9783319180076 p.157-172, 10.1007/978-3-319-18008-3_11
  23. Ouellet Pierre, Quimper Claude-Guy, Time-Table Extended-Edge-Finding for the Cumulative Constraint, Lecture Notes in Computer Science (2013) ISBN:9783642406263 p.562-577, 10.1007/978-3-642-40627-0_42
  24. Schutt Andreas, Feydy Thibaut, Stuckey Peter J., Wallace Mark G., Explaining the cumulative propagator, 10.1007/s10601-010-9103-2
  25. Simonis Helmut, Cornelissens Trijntje, Modelling producer/consumer constraints, Principles and Practice of Constraint Programming — CP '95 (1995) ISBN:9783540602996 p.449-462, 10.1007/3-540-60299-2_27
  26. Laborie, P., Rogerie, J.: Reasoning with conditional time-intervals. In: FLAIRS Conference, pp. 555–560 (2008)
  27. Laborie, P., Rogerie, J., Shaw, P., Vilím, P.: Reasoning with conditional time-intervals. Part II: an algebraical model for resources. In: FLAIRS Conference, pp. 201–206 (2009)
  28. Laborie Philippe, Rogerie Jérôme, Shaw Paul, Vilím Petr, IBM ILOG CP optimizer for scheduling : 20+ years of scheduling with constraints at IBM/ILOG, 10.1007/s10601-018-9281-x
  29. Dejemeppe Cyrille, Van Cauwelaert Sascha, Schaus Pierre, The Unary Resource with Transition Times, Lecture Notes in Computer Science (2015) ISBN:9783319232188 p.89-104, 10.1007/978-3-319-23219-5_7
  30. Ngatchou P., Zarei A., El-Sharkawi A., Pareto Multi Objective Optimization, 10.1109/isap.2005.1599245
  31. Gay Steven, Hartert Renaud, Lecoutre Christophe, Schaus Pierre, Conflict Ordering Search for Scheduling Problems, Lecture Notes in Computer Science (2015) ISBN:9783319232188 p.140-148, 10.1007/978-3-319-23219-5_10
  32. Shaw Paul, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, Principles and Practice of Constraint Programming — CP98 (1998) ISBN:9783540652243 p.417-431, 10.1007/3-540-49481-2_30
  33. Lauriere Jena-Lonis, A language and a program for stating and solving combinatorial problems, 10.1016/0004-3702(78)90029-2
  34. Vilím Petr, Laborie Philippe, Shaw Paul, Failure-Directed Search for Constraint-Based Scheduling, Integration of AI and OR Techniques in Constraint Programming (2015) ISBN:9783319180076 p.437-453, 10.1007/978-3-319-18008-3_30
  35. OscaR Team: OscaR: Scala in OR (2012). https://bitbucket.org/oscarlib/oscar
  36. Thomas, C., Cappart, Q., Schaus, P., Rousseau, L.M.: CSPLib problem 082: Patient transportation problem. http://www.csplib.org/Problems/prob082
  37. Godard, D., Laborie, P., Nuijten, W.: Randomized large neighborhood search for cumulative scheduling. ICAPS 5, 81–89 (2005)
Bibliographic reference Cappart, Quentin ; Thomas, Charles ; Schaus, Pierre ; Rousseau, Louis-Martin. A Constraint Programming Approach for Solving Patient Transportation Problems.CP: International Conference on Principles and Practice of Constraint Programming (Lille, du 27/08/2018 au 31/08/2018). In: Lecture Notes in Computer Science : Principles and Practice of Constraint Programming, John Hooker2018, p. 490-506
Permanent URL http://hdl.handle.net/2078.1/202079