Claudia Archetti: Matheuristics for routing problems (slides here).Due to the advances in exact methods and in technology, several mixed integer linear programming (MILP) models can be solved to optimality or close to optimality within a reasonable amount of time. This has encouraged a number of researchers to design heuristics that incorporate phases where MILP or more generally mathematical programming models are solved, the so-called matheuristics. The relation between the original problem and the mathematical programming model or models incorporated in a matheuristic may vary significantly. Surveys on matheuristics are due to Ball (2011) and Maniezzo et al. (2010) and cover a large variety of approaches and problems. The scope of this talk is to present the literature on matheuristics proposed for the solution of routing problems, classify the approaches proposed and analyze the characteristics of the different methodologies. The goal is to understand which are the features that make a matheuristic a competitive solution approach for a routing problem and to highlight promising lines of research.
Ball, M. (2011). Heuristics based on mathematical programming. Surveys in Operations Research and Management Science, 16: 21–38. Maniezzo, V., Stutzle, T., and Voss, S., (2010). Matheuristics, Annals of Information Systems 10, Springer US.
Rommert Dekker: Robust planning of transportation systems (slides here)In many transportation systems schedules are made before demand is realized. This has several advantages for its customers as they can plan their trip well before and by consolidating demand prices can be kept low. For the carrier it also means that capacity can be optimized. Creating fixed schedules further allows a coordination with other bottlenecks in the transportation system, such as berths at a container terminal, platforms at stations and gates at airports. Yet demand may vary and transportation times may be subject to all kind of disturbances, so the question is how robust are these schedules and what can be done to make them more robust. In principle there are two ways to tackle this problem. First of all, one can insert buffer time or slack in the schedule and secondly, one can apply all kind of recovery actions, like speeding up or cutting stops in order to compensate delays. We will first review approaches for the recovery actions, e.g. optimizing ship speeds in a given schedule. Approaches to the buffer time optimization are more complex as increasing buffer time implies a loss of capacity and this may even lead to higher occupation of the infrastructure. E.g. increasing buffer times may lead to a longer stationing of trains at stations, thereby creating more bottlenecks. We will present models for the optimal distribution of buffer time, both for railways, shipping lines and vehicles. Finally we consider the integrated model of determining both buffer time and recovery actions. This combines a tactical and operational problem in one. Apart from presenting and analyzing the model we will also consider practical cases and pay attention to the problem of obtaining input data for the problems as well as the practical value of the models.
Published June 25, 2014