Séminaire conjoint GERAD-Chaire de recherche du Canada en distributique-Chaire en logistique et en transport
TITRE : The vehicle routing problem with release and due dates
CONFÉRENCIER : Benjamin C. Shelbourne, HEC Montréal, Canada
DATE et ENDOIT : 15 février 2017, 10h30, salle 4488, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Gilbert Laporte
RÉSUMÉ : A novel extension of the classical vehicle routing and scheduling problem is proposed that integrates aspects of machine scheduling into vehicle routing. Associated to each customer is a release date that defines the earliest time that the order is available to leave the depot for delivery, and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimise a convex combination of the operational costs and customer service level, measured as total distance travelled and total weighted tardiness, respectively. We present a mixed integer programming formulation and discuss results obtained using a commercial solver. To achieve a tighter lower bound, a Dantzig-Wolfe reformulation and efficient column generation algorithm are proposed. The resulting pricing problem is an elementary shortest path problem with resource constraints, and release and due dates, which is NP-hard. Two dynamic programming formulations of the pricing problem are developed that use different approaches to model the dependency between the time that a vehicle departs from the depot and the weighted tardiness of the assigned customers. To obtain good-quality upper bounds, we propose a path-relinking algorithm, which is based on a hybrid evolutionary framework rooted in scatter search and techniques for more intelligent solution recombination. Extensive computational experiments on a proposed set of benchmark instances show that the newly defined features have a significant and varied impact on the problem. It is also noted that although tight upper bounds can be found in acceptable computational time, finding tight lower bounds and eventually optimal solutions is complex, and careful implementation is required to achieve acceptable computational times.