Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE: Dealing with time windows in routing problems: Application to the dial-a-ride problem

CONFÉRENCIER: Roberto Wolfler-Calvo, Maître de conférences, Laboratoire des Systèmes Industriels, Université de Technologie, Troyes

DATE et ENDROIT: lundi 11 février 2002, 11h00, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE: Gilbert Laporte (343-6143)

RÉSUMÉ: The Dial-a-Ride is an emerging transport system alternative to traditional ones. A fleet of vehicles, without fixed routes and fixed time schedules, are used to transport people (each passenger from a pickup point to a delivery point) during a pre-specified time interval. It can be modelled as a mixed integer linear programming problem; the derived model is classified in the literature as a routing and scheduling problem and it is NP-hard. The exact approaches to solve this kind of problem are useless to solve real-life instances (hundred of trips), then heuristics are needed. This paper proposes a new fast approximation algorithm to solve the problem. The algorithm is based on the idea of clustering customers (to assign each customer to a vehicle) and routing (to define feasible sequence of pickup and delivery nodes) at the same time. The algorithm reduces the problem to an assignment problem on a particular matrix whose dimension is the number of customers (n) plus the number of vehicles (m). The solution is a set of m paths (a sequence of pickup nodes), which represent a very good starting point to obtain a set of m routes. The interesting idea is the method used to build the assignment cost function, moreover the paper presents two different simple methods to obtain a route. The algorithms proposed have been tested on instances created ad hoc using the network of Milan.