CIISE Distinguished Seminar: New Exact and Heuristic Algorithms for the Multiple-Vehicle Production Routing Problem

Dr. Jean-Francois Cordeau,
HEC Montréal

Date: Oct. 17 (4:00 pm)
Location: EV3.309

Abstract

The purpose of this talk is to introduce new solution algorithms for the Production Routing Problem (PRP), a generalization of the Inventory Routing Problem (IRP) obtained by considering production decisions related to setups (i.e., when to produce) and production quantities (i.e., how much to produce). As in the classical IRP, we consider a single plant and multiple customers facing dynamic but deterministic demand over a discrete and finite planning horizon. In each period, the plant must decide whether or not to make the product and determine the corresponding lot size. In addition, one must plan vehicle routes to deliver the product from the plant to the customers by a limited number of capacitated vehicles. We consider two inventory replenishment policies: maximum level and order-up-to level. For each case, we propose formulations based either on vehicle-indexed flow variables or on vehicle-independent variables. Both types of formulations are strengthened by the addition of valid inequalities. These formulations are then used inside branch-and-cut algorithms that can solve some instances with up to 40 customers. To handle larger instances, we also introduce a new heuristic based on Adaptive Large Neighborhood Search (ALNS). ALNS repeatedly destroys a part of the current solution and reconstructs it in the hope of achieving an improvement. This heuristic has obtained improved results on a large number of instances from the literature involving up to 200 customers and 20 time periods.

Biography

Jean-François Cordeau obtained his Ph.D. in Applied Mathematics at the École Polytechnique de Montréal in 1999. He is now Professor of Logistics and Operations Management at HEC Montréal, where he also holds the Canada Research Chair in Logistics and Transportation. Since 2000, he has been responsible for the Master’s Degree Program in Logistics and Supply Chain Management at HEC. He is a member of the Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT) and of the Groupe d’études et de recherche en analyse des décisions (GERAD). He is Assistant Director of the CIRRELT since 2008. He has authored or coauthored more than 100 scientific articles in combinatorial optimization and mathematical decomposition, mostly in the fields of vehicle routing and network design. He has also supervised more than 50 M.Sc. and Ph.D. students. He is an Associate Editor of the Asia-Pacific Journal of Operational Research, IIE Transactions, INFOR and OR Insight, and a member of the Editorial Board of Computers & Operations Research. Dr. Cordeau has also acted as a consultant for several Canadian and European organizations in the private and public sectors.