The preliminary Scientific Program is now available.
Gilbert Laporte, CIRRELT, Montréal:
Scheduling issues in vehicle routing
Most vehicle routing problems are solved with a distance minimization objective, subject to side constraints, without any consideration for vehicle scheduling. Yet, there are many practical situations where scheduling plays an important role and cannot be dissociated from the routing decisions. In this talk I will describe five routing problems on which I have worked over the past few years, together with a variety of colleagues and students, and in which scheduling plays a crucial role. These problems arise in 1) pickup and delivery operations, including dial-a-ride problems; 2) ship routing and scheduling; 3) green vehicle routing; 4) long-haul vehicle routing with driver working rules; 5) synchronized arc routing for snow ploughing. The talk will be centered on problem descriptions and insights, as opposed to algorithms.
Richard F. Hartl, University of Vienna:
For np-hard combinatorial optimization problems that frequently arise in production, logistics, and transportation exact solution methods are only applicable up to a certain problem size. On the other hand, simple constructive heuristics and improvement heuristics can be used to obtain good solutions quickly. These heuristics are typically tailored to a certain application area and are likely to get stuck in a local optimum. Since a few decades researchers have tried to approach the global optimal solution by proposing some general purpose metaheuristics.
Many such metaheuristics have been developed. Some are nature inspired, some are population based, and most of them are stochastic. Some are constructive; others are based on local search. The talk will briefly mention the historical development and give an overview of the most popular and successful metaheuristics. It will be pointed out that the key success factor is to strike a proper balance between diversification (i.e. coverage of all regions of the search space) and intensification (i.e. more aggressive search for a close local optimum).
Paolo Toth, Professor in Operations Research - University of Bologna:
Models and Algorithms for Passenger Railway Optimization Problems
Passenger railway systems are highly complex systems requiring the solution of several planning problems that can be analyzed and solved through the application of mathematical models and optimization techniques, which generally lead to an improvement in the performance of the system, and as well to a reduction in the time required for solving these problems.
The planning process is generally divided into several phases: Line Planning, Train Timetabling, Train Platforming, Rolling Stock Circulation and Crew Planning. In this lecture, after a description of the whole planning process and of its main phases, the Platforming and Rolling Stock Circulation phases are considered in more detail.
In the Train Platforming Problem, which is the routing problem following the timetabling phase (where the timetable for each train has been fixed), we are given a set of timetabled trains, and the objective is to find the best assignment of the trains to the platforms (and to the routing paths connecting the arrival/departure tracks to the assigned platforms) in a railway station. We consider a general formulation of the problem, which contains as special cases all the versions previously considered in the literature, as well as a case study from the main Italian Infrastructure Manager. An Integer Linear Programming (ILP) formulation is presented, and a column generation procedure is proposed for the solution of the corresponding continuous relaxation. An effective heuristic algorithm, driven by the continuous relaxation of the ILP formulation, is proposed as well. Computational results on real-world instances are reported.
An important problem, arising in the Rolling Stock Circulation phase, is the Train-Unit Assignment Problem. A train unit consists of a self-contained train with an engine and a set of wagons with passenger seats. The Train-Unit Assignment Problem calls for the definition of the “best” train units to be assigned to a given set of timetabled trips, each with a given number of passenger seats requested. Heuristic algorithms based on the solution of Integer Linear Programming models are presented. The heuristics are combined with local search procedures to improve the best solution found. Computational results on real-world instances are reported.
Walter J. Gutjahr, University of Vienna:
Heuristic Techniques for Stochastic Combinatorial Optimization
The tutorial starts with a very short recapitulation of the most important types of stochastic combinatorial optimization (SCO) problems, as they occur in production, logistics, scheduling, facility location, energy, environment, healthcare management, telecommunication and other areas. Since in many cases, already the deterministic counterparts of these problems are NP-hard and can often not be solved exactly, it is no surprise that also in the SCO domain, problem instances of realistic size and complexity frequently require heuristic solution techniques. The tutorial addresses some approximate or heuristic SCO solution approaches either derived from exact methods (as branch-and-bound or progressive hedging) or from prominent metaheuristics (as variants of local search, simulated annealing, evolutionary algorithms, or swarm intelligence algorithms). Special emphasis is given to a discussion of fixed-sample and variable-sample Monte Carlo techniques in SCO. Known results on analytical properties of the considered SCO algorithms are indicated. Finally, a short outline of multi-objective SCO problems and their solution is provided.
Xavier Gandibleux, University of Nantes:
The development of efficient exact algorithms for Multi-Objective Combinatorial Optimization (MOCO) problems is a central research topic in operations research. Major advances have been recorded these last 10 years. One example is the two phase method which is now able to deal with situations presenting more than two objectives. Another example is the definition of the multiobjective branch and bound principle and its
successful applications on several optimization problems. Nevertheless real-life applications complexify the picture. Large scale multiple
objective combinatorial optimization problems, and/or formulation combining continuous and discrete variables have to be considered.
This talk introduces some recent advances and open questions in that field, and develops an example of recent exact algorithms proposed.