1,721,076 research outputs found
Exact and heuristic approaches to the robust periodic event scheduling problem
No full textIn the periodic event scheduling problem, periodically reoccurring events need to be scheduled, subject to constraints on the resulting time differences. A typical application for this type of problem relates to train schedules, which have to repeat every hour for passenger convenience. As external disruptions may occur, robustness considerations need to be included in the scheduling process. In this work, we present a recovery approach for instances where integer programming methods can be applied, and a bi-criteria local search algorithm for large-scale instances. In computational experiments, we compare solutions calculated using the recovery approach to risk-averse and to risk-oblivious solutions. Our results suggest that the solutions generated by our approach have a favorable trade-off between cost and robustness. Furthermore, we compare the local search algorithm to a simplified approach that includes the desired robustness level as a hard constraint. The experiments show that our algorithm finds an improved set of non-dominated solutions within equal computation times
A combined local search and integer programming approach to the traveling tournament problem
No full textThe traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances
An experimental comparison of periodic timetabling models
No full textIn the Periodic Timetabling Problem, vehicle arrivals and departures need to be scheduled over a periodically repeating time horizon. Its relevance and applicability have been demonstrated by several real-world implementations, including the Netherlands railways and the Berlin subway. In this work, we consider the practical impact of two possible problem variations: firstly, how passenger paths are handled, and secondly, how line frequencies are included. In computational experiments on real-world and close-to real-world networks, we can show that passenger travel times can significantly benefit from extended models. (C) 2013 Elsevier Ltd. All rights reserved
Improving the modulo simplex algorithm for large-scale periodic timetabling
No full textThe periodic event scheduling problem (PESP), in which events have to be scheduled repeatedly over a given period, is a complex and well-known discrete problem with numerous real-world applications. The most prominent of them is to find periodic timetables in public transport. Although even finding a feasible solution to the PESP is NP-hard, recent achievements demonstrate the applicability and practicability of the periodic event scheduling model. In this paper we propose different approaches to improve the modulo network simplex algorithm (Nachtigall and Opitz, 2008 [17]), which is a powerful heuristic for the PESP problem, by exploiting improved search methods in the modulo simplex tableau and larger classes of cuts to escape from the many local optima. Numerical experiments on large-scale railway instances show that our algorithms not only perform better than the original method, but even outperform a state-of-the-art commercial MIP solver
Recovery-to-optimality : A new two-stage approach to robustness with an application to aperiodic timetabling
No full textThe goal of robust optimization is to hedge against uncertainties: in most real-world applications, the specific problem instance depends on uncertain data and is hence not known beforehand. In this work we introduce a new two-stage approach called recovery-to-optimality to handle uncertain optimization problems. Motivated by two-stage stochastic programming and in a similar spirit as the well-known approaches of adjustable robustness or recovery robustness, our new concept allows us to adapt a solution when the realized input scenario is revealed. Using a metric in the solution space measuring the recovery costs, we can evaluate the worst-case costs or the average costs of any solution. Our new concept recovery-to-optimality asks for a solution which can be recovered to an optimal solution with low recovery costs. We set up the robust counterpart (RecOpt) for this concept. However, our intention is to provide a practical approach that can easily be used to generate robust solutions for any application. Building on solution algorithms for the deterministic problem, and on algorithms from location theory, we propose a generic procedure which is able to generate solutions with low recovery costs. We point out properties of these solutions and analyze special cases in which the outcome of the procedure coincides with the optimal solutions to (RecOpt). In an experimental study, we apply our approach to linear programs, and to the problem of finding aperiodic train timetables. We compare it to other robustness concepts, and discuss their trade-offs with respect to multiple evaluation criteria
A Comparison of models for uncertain network design: 30th European Conference on Operational Research
No full textTo solve a real-world problem, the modeler usually needs to make a trade-off between model complexity and usefulness. This is also true for robust optimization, where a wide range of models for uncertainty, so-called uncertainty sets, have been proposed. However, while these sets have been mainly studied from a theoretical perspective, there is little research comparing different sets regarding their usefulness for a real-world problem. In this paper we consider a network design problem in a telecommunications context. We need to invest into the infrastructure, such that there is sufficient capacity for future demand which is not known with certainty. There is a penalty for an unsatisfied realized demand, which needs to be outsourced. We consider three approaches to model demand: using a discrete uncertainty set, using a polyhedral uncertainty set, and using the mean of a per-commodity fitted zero-inflated uniform distribution. While the first two models are used as part of a robust optimization setting, the last model represents a simple stochastic optimization setting. We compare these approaches on an efficiency frontier real-world data taken from the online library SNDlib and observe that, contrary to current research trends, robust optimization using the polyhedral uncertainty set may result in less efficient solutions
A comparison of data-driven uncertainty sets for robust network design
No full textWe consider a network design and expansion problem, where we need to make a capacity investment now, such that uncertain future demand can be satisfied as closely as possible. To use a robust optimization approach, we need to construct an uncertainty set that contains all scenarios that we believe to be possible. In this paper we discuss how to actually construct two common models of uncertainty set, discrete and polyhedral uncertainty, using data-driven techniques on real-world data. We employ clustering to generate a discrete uncertainty set, and supervised learning to generate a polyhedral uncertainty set. We then compare the performance of the resulting robust solutions for these two types of models on real-world data. Our results indicate that polyhedral models, while being popular in the recent literature, are less effective than discrete models both in terms of computational burden and solution quality regardless of the performance measure considered (worst-case, conditional value-at-risk, average)
Robust load planning of trains in intermodal transportation
No full textIn this paper, the problem of robust load planning for trains in intermodal container terminals is studied. The goal of load planning is to choose wagon settings and assign load units to wagons of a train such that the utilization of the train is maximized, and setup and transportation costs in the terminal are minimized. However, in real-world applications, many of the parameters needed for the model are not known exactly. Since feasibility of the resulting load distribution has always to be guaranteed, we decided to use a robust approach. In particular, we apply the concepts of strict and adjustable robustness to enhance the load planning problem. Based on a formulation developed in Bruns and Knust (OR Spectrum 34:511-533, 2012) for the deterministic load planning problem, we propose mixed-integer linear programming formulations for most of the respective robust counterparts, dependent on the type of uncertainty. An experimental study shows that most of the robust problems can be solved within runtimes of a few minutes, which is good enough for real-world applications. Furthermore, our results indicate that robust solutions may improve the planning considerably, and that it is promising to add robustness even to large mixed-integer programs with many and diverse technical constraints
An Empirical Analysis of Robustness Concepts for Timetabling
No full textCalculating timetables that are insensitive to disturbances has drawn considerable research efforts due to its practical importance on the one hand and its hard tractability by classical robustness concepts on the other hand. Many different robustness concepts for timetabling have been suggested in the literature, some of them very recently. In this paper we compare such concepts on real-world instances. We also introduce a new approach that is generically applicable to any robustness problem. Nevertheless it is able to adapt the special characteristics of the respective problem structure and hence generates solutions that fit to the needs of the respective problem
An efficient approach to distributionally robust network capacity planning
No full textIn this paper, we consider a network capacity expansion problem in the context of telecommunication networks, where there is uncertainty associated with the expected traffic demand. We employ a distributionally robust stochastic optimization (DRSO) framework where the ambiguity set of the uncertain demand distribution is constructed using the moments information, the mean and variance. The resulting DRSO problem is formulated as a bilevel optimization problem. We develop an efficient solution algorithm for this problem by characterizing the resulting worst-case two-point distribution, which allows us to reformulate the original problem as a convex optimization problem. In computational experiments the performance of this approach is compared to that of the robust optimization approach with a discrete uncertainty set. The results show that solutions from the DRSO model outperform the robust optimization approach on highly risk-averse performance metrics, whereas the robust solution is better on the less risk-averse metric
- …
