• Deutsch
Login

  • Home
  • Search
  • Browse
  • Publish
  • FAQ

Refine

Author

  • Swarat, Elmar (25)
  • Borndörfer, Ralf (22)
  • Sagnol, Guillaume (14)
  • Schlechte, Thomas (14)
  • Buwaya, Julia (4)
  • Erol, Berkan (4)
  • Graffagnino, Thomas (4)
  • Omont, Bertrand (2)
  • Reuther, Markus (2)
  • Schulz, Christof (2)
+ more

Year of publication

  • 2017 (1)
  • 2016 (2)
  • 2015 (3)
  • 2014 (3)
  • 2013 (2)
  • 2012 (8)
  • 2011 (3)
  • 2010 (2)
  • 2008 (1)

Document Type

  • ZIB-Report (12)
  • In Proceedings (8)
  • Article (5)

Has Fulltext

  • no (13)
  • yes (12)

Keywords

  • Game Theory (2)
  • Integer Programming (2)
  • Mixed Integer Programming (2)
  • Netzwerkaggregation (2)
  • Stackelberg Equilibrium (2)
  • Vehicle Routing Problem (2)
  • network aggregation (2)
  • Controls in transportation networks (1)
  • Duty Roster Planning (1)
  • Duty Rostering (1)
+ more

Institute

  • Mathematical Optimization (25)
  • Mathematics of Transportation and Logistics (13)

25 search hits

  • 1 to 10
  • BibTeX
  • CSV
  • RIS
  • XML
  • 10
  • 20
  • 50
  • 100

Sort by

  • Year
  • Year
  • Title
  • Title
  • Author
  • Author
A Stackelberg game to optimize the distribution of controls in transportation networks (2012)
Borndörfer, Ralf ; Omont, Bertrand ; Sagnol, Guillaume ; Swarat, Elmar
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.
Aggregation Methods for Railway Networks (2010)
Borndörfer, Ralf ; Erol, Berkan ; Graffagnino, Thomas ; Schlechte, Thomas ; Swarat, Elmar
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.
Optimizing the Simplon Railway Corridor (2010)
Borndörfer, Ralf ; Erol, Berkan ; Graffagnino, Thomas ; Schlechte, Thomas ; Swarat, Elmar
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.
Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach (2012)
Borndörfer, Ralf ; Buwaya, Julia ; Sagnol, Guillaume ; Swarat, Elmar
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.
The Second Chvatal Closure Can Yield Better Railway Timetables (2008)
Liebchen, Christian ; Swarat, Elmar
Optimizing the Simplon railway corridor (2012)
Borndörfer, Ralf ; Erol, Berkan ; Graffagnino, Thomas ; Schlechte, Thomas ; Swarat, Elmar
Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering (2013)
Borndörfer, Ralf ; Sagnol, Guillaume ; Schlechte, Thomas ; Swarat, Elmar
We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.
Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue (2015)
Borndörfer, Ralf ; Reuther, Markus ; Schlechte, Thomas ; Schulz, Christof ; Swarat, Elmar ; Weider, Steffen
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.
Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks (2014)
Borndörfer, Ralf ; Buwaya, Julia ; Sagnol, Guillaume ; Swarat, Elmar
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.
Micro–macro transformation of railway networks (2011)
Schlechte, Thomas ; Borndörfer, Ralf ; Erol, Berkan ; Graffagnino, Thomas ; Swarat, Elmar
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.
  • 1 to 10

OPUS4 Logo

  • Contact
  • Impressum und Datenschutz
  • Sitelinks