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

TITRE: An exact approach for the symmetric capacitated vehicle routing problem with two-dimensional loading constraints

CONFÉRENCIER: Manuel Iori, Università di Bologna, Italie

DATE et ENDROIT: Mercredi 3 décembre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

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

RÉSUMÉ: In the classical Capacitated Vehicle Routing Problem, the demands of the clients are simply expressed by a positive integer, usually representing the weight. This can represent a too strong approximation for many practical routing applications, where the demands are composed by objects of a given size, and the loading of the vehicles must be explicitly considered. We consider the practical case in which the demand of each customer is defined by a set of rectangular items, each with a given weight and base dimensions. Thus, loading a set of items into a vehicle requires both checking that the maximum weight capacity is respected, and that the two-dimensional loading is feasible. The problem is composed by a routing part, which we solved through a branch and cut technique, and by a loading part, which we solved through a branch and bound. Preliminary computational results show the effectiveness of the algorithm.