TY - GEN A1 - Borndörfer, Ralf A1 - Omont, Bertrand A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Stackelberg game to optimize the distribution of controls in transportation networks N2 - We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of $N$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways. T3 - ZIB-Report - 12-15 KW - Stackelberg game KW - Polymatrix game KW - Controls in transportation networks Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14995 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - An IP Approach to Toll Enforcement Optimization on German Motorways N2 - This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany. T3 - ZIB-Report - 11-42 KW - Toll Enforcement KW - Vehicle Routing Problem KW - Duty Roster Planning KW - Integer Programming Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14299 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Aggregation Methods for Railway Networks N2 - In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run. T3 - ZIB-Report - 10-23 KW - makroskopische Bahnmodellierung KW - Netzwerkaggregation KW - macroscopic railway modeling KW - network aggregation Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11881 UR - http://www.sciencedirect.com/science/article/pii/S2210970611000047 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimizing the Simplon Railway Corridor N2 - This paper presents a case study on a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. Starting from a detailed microscopic network as it is used in railway simulation, the data is transformed by an automatic procedure to a less detailed macroscopic network, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. In this way, the macroscopic railway network is saturated with trains. Finally, the corresponding timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the slots. Using this integer programming based micro-macro aggregation-disaggregation approach, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. This also allows to to undertake a sensitivity analysis of various problem parameters. T3 - ZIB-Report - 10-24 KW - Trassenallokation KW - Netzwerkaggregation KW - Fallstudie KW - Simplon Korridor KW - railway track allocation KW - network aggregation KW - case study KW - Simplon corridor Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11892 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Railway Track Allocation - Simulation, Aggregation, and Optimization N2 - Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data. T3 - ZIB-Report - 11-35 KW - railway models, railway capacity, track allocation framework Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14031 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimizing the Simplon railway corridor JF - Annals of Operations Research Y1 - 2012 UR - http://dx.doi.org/10.1007/s10479-012-1260-9 U6 - https://doi.org/10.1007/s10479-012-1260-9 VL - 218 IS - 1 SP - 93 EP - 106 PB - Springer US ET - Annals of Operations Research ER - TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of edges to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. T3 - ZIB-Report - 14-07 KW - Game Theory KW - Stackelberg Equilibrium KW - Security Games KW - Mixed Integer Programming KW - Price of Anarchy Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-47139 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach T2 - Proceedings of INOC'2013 N2 - We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented. Y1 - 2013 U6 - https://doi.org/http://dx.doi.org//10.1016/j.endm.2013.05.100 VL - 41 SP - 253 EP - 260 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Omont, Bertrand A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Stackelberg game to optimize the distribution of controls in transportation networks T2 - Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012) N2 - We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of $N$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways. Y1 - 2012 U6 - https://doi.org/http://dx.doi.org/10.1007/978-3-642-35582-0_17 VL - 105 SP - 224 EP - 235 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Swarat, Elmar A1 - Weider, Steffen T1 - Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively. Y1 - 2015 ER -