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

TITRE : Feasibility checking in the Dial-a-Ride Problem using Constraint Programming

CONFÉRENCIER : Gerardo Berbeglia, HEC Montréal

DATE et ENDROIT : 15 février, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Jean-François Cordeau (514-340-6278)

RÉSUMÉ : The Dial-a-Ride Problem (DARP) consists of routing a fleet of vehicles in order to satisfy user transportation requests. The problem has several constraints such as time windows, maximum transportation times, precedence constraints, and other quality-of-service related restrictions. We have developed a constraint programming algorithm for detecting if a given instance of the DARP is feasible or not and in case the instance is feasible, it finds a solution. For this, we have studied the complexity of determining whether a partial solution for the DARP can be extended into a feasible solution taking into account different sets of constraints. For some relaxations of the DARP a polynomial algorithm for detecting feasibility was developed, while for others the problems were proved to be NP-Complete. The program could be used as a tool in a dynamic context for determining whether a given set of new requests received during operations could be satisfied or not by updating the actual routes. Partial results will be presented.