Refine
Document Type
- Article (5) (remove)
Language
- English (5)
Has Fulltext
- no (5)
Is part of the Bibliography
- no (5)
Institute
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, we developed a personalized crew rostering model, to schedule the crews of the tours. 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 main focus of this paper extends our previous publications on how different requirements for the rostering can be modeled in detail. The second focus is on a bi-criteria analysis of the planning problem to find the balance between the control quality and the roster acceptance. Finally, computational results on real-world instances show the practicability of our method and how different input parameters influence the problem complexity.
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.
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.
Network spot-checking games: Theory and application to toll enforcing in transportation networks
(2015)
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 arcs 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 (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP-hard. More generally, we prove that it is NP-hard to compute a SSE in a polymatrix game, even if the game is pairwise zero-sum. Then, we give some bounds on the price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article.