Séminaire conjoint CRT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : On Time-Dependent Models for Unit Demand Vehicle Routing Problems
CONFÉRENCIER : Luis Gouveia, DEIO, Universidade de Lisboa, Portugal
DATE et ENDROIT : 10 novembre 2006, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Gilbert Laporte (514-343-6143)
RÉSUMÉ : We study, in the context of the Unit-Demand Vehicle Routing Problem, the relationship between the linear programming relaxation of a single-commodity flow model and the linear programming relaxation of a pure time-dependent formulation that is closely related to a formulation. We show that a time-dependent formulation implies a new large class of upper bounding and lower bounding flow constraints that are not implied by the linear programming of the single commodity flow model. Furthermore, by using some well-known techniques for generating inequalities in the space of the design variables from the linear programming feasible set of single commodity flow models show how to generate new inequalities that are related to the well-known multistar constraints. As another example of the modeling strength of time-dependent formulations, we also consider a variation of the vehicle routing problem that is not easily modeled with the set of variables involved in the single-commodity flow model. Computational results show that the time dependent formulation can be used to easily solve instances with up to 80 nodes, when the vehicle capacity is reasonably small.