Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : Algorithms for the Heterogeneous Dial-a-Ride Problem
CONFÉRENCIÈRE : Sophie Parragh, University of Vienna
DATE et ENDROIT : 1 octobre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Jean-François Cordeau (514-343-7307)
RÉSUMÉ : This research is motivated by the problem faced by the Austrian Red Cross (RK), Austria’s major ambulance dispatcher. The RK has to devise routing plans for their ambulances for all those requests that are known ahead of time. This problem can be defined as a Heterogeneous Dial-A-Ride-Problem (HDARP). The term heterogeneous refers to the additional heterogeneity that has to be considered, which is usually not present in standard DARP applications. The RK disposes over several different types of vehicles, each type providing a different amount of space for several different modes of transportation. Each patient may demand to be transported either seated or on a stretcher or in a wheelchair. An accompanying person may also be present, and room for them has to be provided on the vehicle. The aim is to construct a routing plan that is of minimum routing cost while respecting service related criteria, expressed in terms of time windows, as well as driver labor regulations, in terms of maximum route duration limits and mandatory lunch breaks. We design a column generation based algorithm to compute lower bounds. These bounds will serve to assess the solution quality obtained by means of heuristic algorithms.