IE-OPIM Joint Graduate Seminar: Gilbert Laporte (HEC Montreal)
“The Fascinating History of the Vehicle Routing Problem”
Date: Wednesday, November 18, 2015
Time: 13:40 – 14:30
Location: FENS G032
Abstract: The Vehicle Routing Problem (VRP), introduced in 1959 by Dantzig and Ramser, plays a central role in distribution management. It consists of designing a set least cost delivery or collection routes for a set of vehicles based at a depot and visiting a set of geographically scattered customers, subject to a variety of constraints. The most common constraints are capacity constraints, duration constraints and time windows. This talk will concentrate on the so-called classical VRP with capacity constraints only. The VRP is ubiquitous and highly important from an economic point of view. From a research perspective, it occupies a central role in operations research. Its study by the scientific community has fueled the development and growth of several families of exact and approximate algorithms. Exact algorithms such as branch-and-cut, column generation and branch-and-cut-and-price owe part of their evolution to the study of the VRP. Similarly, the most common classical heuristics and most of the more recent metaheuristics have been developed through the study of the VRP. In this talk I will highlight several of these developments. In spite of all the attention the VRP has received over the past 55 years, it can still only be solved exactly for relatively small instances (with slightly more than 100 customers) and the corresponding algorithms are rather intricate. Over the past 10 years or so, several powerful metaheuristics have been put forward for the approximate solutions of the VRP. The best ones combine concepts borrowed from local search and genetic search. Nowadays, the best metaheuristics can generate rather quickly solutions whose value lies within 1% of the best known solution values on a set of benchmark instances. This talk will also review these developments. It will close with some research outlooks.
Bio: Gilbert Laporte obtained his Ph.D. in Operations Research at the London School of Economics in 1975. He is professor of Operations Research at HEC Montréal, Canada Research Chair in Distribution Management, adjunct Professor at Molde University College, Bilkent University and the University of Alberta, visiting professor at the University of Southampton, and guest professor at the University of Science and Technology of China. He is also a member of the Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT) and founding member of the Group for Research in Decision Analysis (GERAD). He has been Editor of Transportation Science, Computers & Operations Research and INFOR. He has authored or coauthored 19 books, as well as more than 475 scientific articles in combinatorial optimization, mostly in the areas of vehicle routing, location and timetabling.
Gilbert Laporte has received many scientific awards including the Pergamon Prize (United Kingdom) in 1987, the 1994 Award of Merit from the Canadian Operational Research Society (CORS), and the CORS Practice Prize on three occasions. In 1999, he obtained the Jacques-Rousseau Prize for Interdisciplinarity from the Association canadienne-française pour l’avancement des sciences (Acfas), and the President’s Medal from the Operational Research Society (United Kingdom). In 2001, he was awarded the Grand Prize for Teaching Excellence by HEC Montréal. He has been a Fellow of the Royal Society of Canada since 1998, and a Fellow of the Institute for Operations Research and the Management Sciences (INFORMS) since 2005. In 2005, he was the co-winner of the Glover-Klingman Prize. In 2007 he was awarded the Innis-Gérin Medal from the Royal Society of Canada. In 2009 he received the Gérard-Parizeau Award, he was inducted as the 42nd Honorary Member of the INFORMS International Omega Rho Society, and he received the Robert Herman Lifetime Achievement Award in Transportation Science from the Transportation Science and Logistics Section of INFORMS. In 2012, he won the Pierre-Laurin Award from HEC Montréal for his overall career research achievements. In 2014, he was the co-winner of the FICO Global “Optimize the Real World” contest and he received the Lifetime Achievement in Location Analysis Award from the INFORMS Section on Location Analysis.