Swarat, Elmar
Refine
Year of publication
Document Type
- ZIB-Report (12)
- In Proceedings (9)
- Article (5)
Language
- English (26)
Is part of the Bibliography
- no (26)
Keywords
Institute
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.
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.
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.
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.
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.
Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks
(2014)
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.
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.
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.