TY - CHAP A1 - Liebchen, Christian A1 - Swarat, Elmar ED - Fischetti, Matteo ED - Widmayer, Peter T1 - The Second Chvatal Closure Can Yield Better Railway Timetables T2 - ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-15802 UR - http://drops.dagstuhl.de/opus/volltexte/2008/1580 PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany CY - Dagstuhl, Germany ER - TY - CHAP A1 - Schwartz, Stephan A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Designing Inspector Rosters with Optimal Strategies T2 - Operations Research Proceedings 2016 N2 - We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_30 SP - 217 EP - 223 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Case Study on Optimizing Toll Enforcements on Motorways T2 - 3rd Student Conference on Operational Research N2 - In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach. Y1 - 2012 U6 - https://doi.org/10.4230/OASIcs.SCOR.2012.1 VL - 22 SP - 1 EP - 10 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - An IP Approach to Toll Enforcement Optimization on German Motorways T2 - Operations Research Proceedings 2011 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. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-29210-1_51 SP - 317 EP - 322 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 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar ED - Lavi, Ron T1 - The Price of Spite in Spot-checking games T2 - 7th International Symposium on Algorithmic Game Theory (SAGT'2014) 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. 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. Y1 - 2014 SN - 978-3-662-44802-1 U6 - https://doi.org/10.1007/978-3-662-44803-8 N1 - Brief Announcement included in Back Matter p. 293 following VL - 8768 SP - 293 PB - Springer 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 - TY - CHAP A1 - Gamrath, Gerwin A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - An LP-based heuristic for Inspector Scheduling T2 - Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I N2 - We present a heuristic based on linear programming (LP) for the integrated tour and crew roster planning of toll enforcement inspectors. Their task is to enforce the proper paying of a distance-based toll on German motorways. This leads to an integrated tour planning and duty rostering problem; it is called Toll Enforcement Problem (TEP). We tackle the TEP by a standard multi-commodity flow model with some extensions in order to incorporate the control tours. The heuristic consists of two variants. The first, called Price & Branch, is a column generation approach to solve the model’s LP relaxation by pricing tour and roster arc variables. Then, we compute an integer feasible solution by restricting to all variables that were priced. The second is a coarse-to-fine approach. Its basic idea is projecting variables to an aggregated variable space, which is much smaller. The aim is to spend as much algorithmic effort in this coarse model as possible. For both heuristic procedures we will show that feasible solutions of high quality can be computed even for large scale industrial instances. Y1 - 2021 UR - https://patatconference.org/patat2020/proceedings/ VL - 1 SP - 77 EP - 86 ER -