2018 in Cagliari (Italy), 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 introduced by Daniele
Vigo. Titles and abstracts are reported below:
Teodor Gabriel Crainic: Parallel Computing and Vehicle Routing
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.
Guy Desaulniers: Branch-price-and-cut for vehicle routing
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.
Ola Jabali: Stochastic Vehicle Routing Problems
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.
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.
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. A
maximum number of 20 participants will be accepted.
Didactic material and coffee breaks will be provided during the PhD
school. If required, a certificate of attendance will be provided to
participants.
VeRoLog will also give partial financial support in the registration fee
for some PhD students selected by the organizers.
To apply, students are requested to send their CV to mdifrance@unica.it
within January 31st, 2018.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
