VeRoLog PhD School
Owing to the presence in Cagliari of many brilliant researchers attending Odysseus 2018, VeRoLog will organize a two-day school just before the beginning of the workshop: Friday 1st and Saturday 2nd of June 2018. Four lectures will be given by Teodor Gabriel Crainic, Guy Desaulniers, Ola Jabali, Thibaut Vidal on different methodologies for Vehicle Routing Problems. The school will be held in the red room of the “Citadel of Museums” and introduced by Daniele Vigo. Titles and abstracts are reported below:
Friday June 1 in the morning
Thibaut Vidal: Heuristics for vehicle routing problems: Structural problem decompositions and unified search
Vehicle Routing Problems (VRP) involve designing least-cost delivery routes to visit a geographically-dispersed set of customers. Over the past 60 years, this class of problems has been the subject of considerable work, summing up to thousands of articles. In 2017, we can reasonably say that the classical “capacitated” VRP (with only capacity constraints) is fairly well solved by metaheuristic techniques. Yet, the research on VRPs keeps on expanding even further, as a consequence of the increasing diversity of applications, which bring forth new difficult constraints, objectives, and combined decisions to account for customer’s needs, vehicle and network restrictions, and to better integrate VRP optimization in the decision chains. Moreover, with the advent of collaborative logistics, green initiatives, smart cities, multi-modal transport, in contexts where multiples stakeholders and conflicting objectives have to be considered jointly, or in the presence of dynamic problems with a short response time, the efficient resolution of these problems becomes even more critical. In this mini-course, we will review some challenging VRP variants and examine the heuristic solution techniques which are developed to tackle them. We will study the close connections between the structure of the problem decision sets, and the associated solution methods, showing how modern heuristics can effectively perform a search in a reduced space, defined by fewer groups of decision variables, while a decoder is in charge of producing complete solutions. Finally, a key challenge is to progress towards “unified” solution methods, which are not tailored for one single problem, but instead designed to solve a wide collection of problem variants with different constraints and objectives. For this purpose, we expose some of the main principles of the Unified Hybrid Genetic Search (UHGS), which has obtained state-of-the-art results –in a single code base– for more than 50 difficult variants of vehicle routing and arc routing problems.
Vehicle Routing Problems (VRP) involve designing least-cost delivery routes to visit a geographically-dispersed set of customers. Over the past 60 years, this class of problems has been the subject of considerable work, summing up to thousands of articles. In 2017, we can reasonably say that the classical “capacitated” VRP (with only capacity constraints) is fairly well solved by metaheuristic techniques. Yet, the research on VRPs keeps on expanding even further, as a consequence of the increasing diversity of applications, which bring forth new difficult constraints, objectives, and combined decisions to account for customer’s needs, vehicle and network restrictions, and to better integrate VRP optimization in the decision chains. Moreover, with the advent of collaborative logistics, green initiatives, smart cities, multi-modal transport, in contexts where multiples stakeholders and conflicting objectives have to be considered jointly, or in the presence of dynamic problems with a short response time, the efficient resolution of these problems becomes even more critical. In this mini-course, we will review some challenging VRP variants and examine the heuristic solution techniques which are developed to tackle them. We will study the close connections between the structure of the problem decision sets, and the associated solution methods, showing how modern heuristics can effectively perform a search in a reduced space, defined by fewer groups of decision variables, while a decoder is in charge of producing complete solutions. Finally, a key challenge is to progress towards “unified” solution methods, which are not tailored for one single problem, but instead designed to solve a wide collection of problem variants with different constraints and objectives. For this purpose, we expose some of the main principles of the Unified Hybrid Genetic Search (UHGS), which has obtained state-of-the-art results –in a single code base– for more than 50 difficult variants of vehicle routing and arc routing problems.
Friday June 1 in the afternoon
In recent years there has been a notable interest in both formulating and solving stochastic vehicle routing problems. This interest stems from the fact that the majority of vehicle routing problem (VRP) models, used to plan fundamental logistics operations, are subject to various uncertainties when applied in practice. In particular, in VRP models it is assumed that the problem parameters are deterministic. Uncertainties in these parameters entail additional feasibility and cost considerations, and therefore necessitate models and solution methods that explicitly handle uncertainty rather than simply react to it. In this talk, we will cover uncertainty in three sets of parameters commonly considered in the literature: stochastic demands, stochastic customers and stochastic times. These parameters are typically modeled using suitable random variables or through the use of scenarios. We will review the main modeling paradigms that have been used to formulate the related problems, and present the main existing exact and approximate solution methods that have been proposed to tackle them. In particular, we will use the VRP with stochastic demands as an example to present state-of-the-art solution algorithms. Finally, we will conclude with a discussion of how the expression of stochastic phenomena can be improved in light of the ever growing availability of data in the VRP context.
Saturday June 2 in the morning
Branch-price-and-cut is one of the leading methodologies for solving a wide variety of vehicle routing problems. In this talk, we will go through the basics of this solution method as well as some of its most recent enhancements: Dantzig-Wolfe decomposition, lower bounds, column generation, elementary shortest path pricing problem with resource constraints, labeling algorithms (mono-directional, bidirectional, with decremental state space relaxation), ng-route relaxation, branching, capacity cuts, limited-memory subset row cuts, variable fixing, and route enumeration. We will use throughout the talk the vehicle routing problem with time windows as a typical example and present the most recent computational results for this problem.
Saturday June 2 in the afternoon
Parallel computing speeds up algorithmic work. When meta and matheuristics are involved, which is quite often the case for vehicle routing problems, parallel-computing strategies may also yield a more thorough exploration of the search space and better solutions compared to those of sequential methods. The lecture will present an overview of the main parallel-computing strategies for combinatorial optimization, with illustrations from the vehicle-routing problem class, identifying algorithmic concepts and discussing behaviour and performance.
The school will be offered free of charge to Phd Students attending Odysseus 2018. Moreover, it is also possible to attend only the school by a registration fee of €150.00. Participants have to be enrolled in a PhD program and, preferably, in an early stage of their studies.
Didactic material, lunches and coffee breaks will be provided during the PhD school. Financial support will be provided by VeRoLog. If required, a certificate of attendance will be provided to participants.