This workshop is about the state-of-the-art in vehicle routing. Five prominent international researchers in this field, will give a lecture in which they discuss recent advances and relevant applications. The workshop is aimed at any researcher in operations research, PhD or senior, with an interest in vehicle routing.
- Date
- Thursday 14 Nov 2019, 08:30 - 14:30
- Type
- Workshop
- Spoken Language
- English
- Room
- Athene (M1-19)
- Building
- Van der Goot Building
- Location
- Campus Woudestein
Speakers
- Prof. Guy Desaulniers, Polytechnique Montréal & GERAD
- Prof. Jan Ehmke, Otto-von-Guericke-Universität Magdeburg
- Prof. Stefan Irnich, Johannes Gutenberg University Mainz
- Prof. Martin Savelsbergh, Georgia Tech
- Prof. Daniele Vigo, Alma Mater Università di Bologna
| Time | Programme |
|---|---|
| 08:30-09:00 | Walk-in |
| 09:00-09:10 | Opening |
| 09:10-09:55 | Enhancing Local Search Through Machine Learning: a Case Study on the Vehicle Routing Problem |
| 09:55-10:15 | Coffee Break |
| 10:15-11:00 | The value of historical data for customer acceptance in attended home deliveries |
| 11:00-11:15 | Coffee Break |
| 11:15-12:00 | Column selection and aggregated row generation in column generation algorithms for vehicle routing |
| 12:00-12:40 | Lunch break |
| 12:40-13:25` | Branch-Cut-and-Price for the VRP with Time Windows and Convex Node Costs Prof. Stefan Irnich(Gutenberg School of Management & Economics, Johannes Gutenberg University Mainz, Germany) |
| 13:25-13:40 | Coffee break |
| 13:40-14:25 | Dynamic Discretization Discovery Algorithms for Solving Time-Dependent Shortest Path Problems |
| 14:25-14:30 | Closing |
| 14:30 | Walk-out |
Column selection and aggregated row generation in column generation algorithms for vehicle routing
Column generation is part of most state-of-the-art algorithms for solving vehicle routing problems. For large instances, it may suffer from degeneracy in the master problem and dual variable instability, yielding slow convergence. In this talk, we introduce two new techniques to avoid these issues. First, column selection by machine learning selects at each iteration a subset of the columns generated by the pricing problem to reduce degeneracy. Second, aggregated row generation initially replaces all set partitioning constraints by a very small subset of aggregated constraints and generates additional ones as needed, increasing dual variable stability. Computational results will be reported for both techniques.
The value of historical data for customer acceptance in attended home deliveries
Home delivery services require the attendance of the customer during tight delivery time windows, which makes these services challenging and expensive. We consider the example of an online supermarket that dynamically accepts customers during a booking process. Here, information about future demand and its consequences on the acceptance decision is usually derived from artificial data sets. We propose an online sampling approach which includes large amounts of historical order data to assess the impact of the current request on route efficiency and future requests. In particular, we investigate how much and what type of historical order data can improve the number of accepted customers.
Branch-Cut-and-Price for the VRP with Time Windows and Convex Node Costs
In the vehicle routing problem with time windows and convex node costs (VRPTW-CNC), each customer has convex cost function defined over the time window describing his/her preferred service time. The VRPTW-CNC combines and extends both the standard vehicle routing problem with time windows and some previous results on the optimal service scheduling problem over a fixed route. We propose a branch-and-cut-and-price algorithm to solve the VRPTW-CNC with general convex inconvenience cost functions. To solve the pricing problem, our labeling algorithm only generates labels that possibly lead to optimal schedule times over a route, which significantly improves the effectiveness of pricing.
(joint work with Qie He and Yongjia Song, see https://doi.org/10.1287/trsc.2019.0891)
Dynamic Discretization Discovery Algorithms for Solving Time-Dependent Shortest Path Problems
Finding a shortest path in a network is a fundamental optimization problem. We focus on settings in which the travel time on an arc in the network depends on the time at which traversal of the arc begins. In such settings, reaching the sink as early as possible is not the only objective of interest. Minimizing the duration of the path, i.e., the difference between the arrival time at the sink and the departure from the depot, and minimizing the travel time along the path from source to sink, are also of interest. We introduce dynamic discretization discovery algorithms to efficiently solve such time-dependent shortest path problems with piecewise linear arc travel time functions.
Enhancing Local Search Through Machine Learning: a Case Study on the Vehicle Routing Problem
Local search is one of most popular optimization techniques used to effectively solve hard combinatorial optimization problems (COPs) being the main component of all modern meta-heuristics which perform hundreds of thousands of iterations exploring the neighborhoods of given solutions. Practical algorithms typically exploit a relatively small set of simple local search operators and use them to optimize a solution until a local optimum is reached. Up to now, little attention has been given to the orderings in which operators are examined; common orderings usually consists in prefixed static or dynamic randomly ordered operators examination. This work we study whether in a Variable Neighbourhood Descent (VND) setting, using Machine Learning techniques to identify the most promising operator enables computational savings that could be used to perform a more fruitful search. In particular, as a case study, we focused on the (capacitated) vehicle routing problem, and we train an Artificial Neural Network for raking operators at search time.
(joint work with L. Accorsi, M. Lombardi and M. Milano)
Guy Desaulniers
(Department of Mathematics and Industrial Engineering & GERAD, Polytechnique Montréal, Canada)
Guy Desaulniers received the B.Sc. and M.Sc. degrees in mathematics from University of Montreal, Montreal, Canada, and the Ph.D. degree in mathematics from Polytechnique Montreal. He is a full Professor with the Department of Mathematics and Industrial Engineering, Polytechnique Montreal, since 2000 and was the Director of the GERAD Research Center between 2015 and 2019. Before becoming a Professor at Polytechnique Montreal, he was a Professor at the Royal Military College (Saint-Jean-sur-Richelieu) and at Laval University (Quebec City), and also held researcher positions at Polytechnique Montreal. His main research interests are in mathematical programming decomposition algorithms, integer programming, and dynamic programming, with applications in transportation and personnel scheduling among others. He has published more than 100 scientific papers in international journals and participated in many industrial projects.
Jan Fabian Ehmke
(Faculty of Economics and Management, Otto-von-Guericke-Universität Magdeburg, Germany)
Jan Fabian Ehmke graduated at the University of Braunschweig in 2011. After a PostDoc stay at the Management Sciences Department of the University of Iowa, he became an assistant professor at Freie Universität Berlin in 2012 and has been a full professor of Management Science at the University of Magdeburg since 2017.
Jan’s research interests are the analysis of large amounts of transportation data and their usage in the optimization of dynamic and stochastic transportation problems. Current research deals with making home deliveries more profitable and reliable, improving multi-modal travel planning, and developing smart trip management policies for future autonomous transportation and mobility systems.
Stefan Irnich
(Gutenberg School of Management & Economics, Johannes Gutenberg University Mainz, 55128 Mainz, Germany)
Stefan Irnich is a full professor in logistics management at the Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Germany. His research interests include the development and application of optimization methods to solve problems in logistics and transportation, network design, algorithmic graph theory, and revenue management. In recent years, he has mainly published papers on mathematical programming decomposition methods and also on modeling and solving rich vehicle-routing problems.
Martin Savelsbergh
(H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech, United States)
Martin Savelsbergh is a logistics and optimization specialist with over 25 years of experience in mathematical modeling, operations research, optimization methods, algorithm design, performance analysis, transport, supply chain management, and production planning. He has published over 170 research papers in many of the top operations research and optimization journals and has supervised more than 30 Ph.D. students. Martin has a track record of creating innovative techniques for solving large-scale optimization problems in a variety of areas, ranging from service network design, to last-mile and crowdsourced delivery, to ridesharing.
Daniele Vigo
(DEI - Dept. of Electrical, Electronic and Information Engineering "Gugliemo Marconi” , Alma Mater Università di Bologna, Italy)
Daniele Vigo is Professor of Operations Research at the Department of Electrical, Electronic and Information Engineering of the University of Bologna. He is interested in the design of innovative algorithms for the solution of difficult decision and optimization problems arising in several applications fields ranging from Logistics to Energy Production and to Smart Cities. He is author of more than 130 scientific papers and coeditor of some highly cited books on Vehicle Routing. He is president of the Italian OR society 2016-19 and coordinator of the EURO working group on Vehicle Routing and Logistics optimization.
Registration
Registration for this workshop is closed.
Payment method
Bank Transfer: reference: 12020001.002.701 Ectrie – Workshop Vehicle Routing-Advances and Applications and your name.
Entity | ABN AMRO |
Account Name | Erasmus Universiteit, Erasmus School of Economics |
Address | P.O. Box 949, 3000 DD Rotterdam, the Netherlands |
Account number | 42.85.81.676 |
IBAN number | NL43ABNA0428581676 |
Swift/BIC code | ABNANL2A |
Organiser
- More information
Secretariat Econometrics
room: EB-06
phone: +31 (0)10 408 12 59
email: eb-secr@ese.eur.nl
