All trucks with at least 7.5 tonnes weight have to pay a distance-based toll on German motorways and on main roads. It has become an important income for the Bundesverkehrsministerium, the German ministry of transport. The payment of the toll has to be enforced. Thus, the Federal Office for Goods Transport (BAG) has the task to execute a sample, network-wide control. For that on the one hand there are around 400 permanently installed control gantries operated by the technical system provider, Toll Collect. On the other hand a mobile control is done by 300 vehicles of the BAG. Our research is focused on developing and implementing suitable optimization models and algorithms for a good and efficient planning of the mobile control tours. We want to build up control schedules that guarantee a network-wide control that takes the spatial and temporal traffic distribution into account. In addition the planning of the tours should account for the distribution of the toll evaders. A major challange in this project is the generation of feasible crew rosters respecting several legal and administrative rules.
Goals
The project "Optimization of Toll Control Tours" aims at developing models and algorithms for planning the tours of toll inspectors on German motorways in an optimal way, with respect to certain objectives. These schedules are subject to several legal constraints, like the weekly working time, the daily rest period or the authorized control areas.
The task is both to define the service hours of the controllers, as well as the sections that will be controlled. The optimized duties should guarantee a network-wide control but also take the temporal and spatial distribution of traffic into account to allocate the limited number of control forces in a most efficient way. In addition also data about evaders is considered in the objective function. In addition, we have developed a game-theoretic model to compute the randomized control schedules that minimize the numbers of drivers who could have an incentive to evade the toll.
In the first phase of this project (2010-2013), we have developed first models and a prototype for a pilot test. In the second phase (2013-2016) we have implemented an optimization tool called TC-OPT. For the third phase (until 2019), we want both to extend the features of the program and implement more efficient algorithms. Furthermore, we will take into account the expected behavior of drivers.
Optimization
From a mathematical point of view, the problem of determining the control tours is a vehicle-routing problem with time-dependent profits under several conditions like length restrictions of the tours or minimum levels of control for each section. This problem is coupled with a personalized duty roster planning. While the tours can be enumerated the rostering is modeled by an appropriate planning graph. In this graph rosters are represented by paths.
The yellow path in the figure below represents a feasible weekly roster for a single inspector. The possible duty times for the days are "early" (E), "day" (D) and "late" (L) as well as "Free". In the back, the traffic distribution of exemplary subregion over the week is depicted.
We use a standard Multi-Commodity Flow model for the rostering with additional constraints to incorporate the tours. Legal work rules are either implicitly modeled by the graph structure or by resource or base constraints in the IP. To solve real-world instances the entire spectrum of integer programming methods from column generation, cutting planes, branch & bound, to primal heuristics is utilized.
Our tool, TC-OPT, is implemented in C++ and it interfaces the commercial software tool "IVU.plan" by IVU AG. In the current phase of this project, we plan to extend TC-OPT. On the one hand the performance should be improved and a lot of additional features will be integrated. Examples are to complete duties that are partly fixed or to respect restrictions on inspector availability or the use of additional duty starting times. Furthermore, the new version will make it possible to compute duty rosters based on covering constraints based on the control distribution generated by our game-theoretic model (cf. below).
Results
Since the beginning of 2014 TC-OPT is in production operation in each control area of Germany to generate monthly duty rosters for over 400 inspectors.In addition, first tests are running to use it also to optimize the duties of inspectors conducting classical truck inspections like checks of maximum driving time, or of load and vehicle safety.
Game Theory
We have developed a model based on game theory to optimize the control strategy of the BAG (Bundesamt für Güterverkehr - Federal Office for Goods Transport). In our model, the controllers and the truck drivers are playing a game, in which each driver has the choice between several possible actions (pay or evade, and choose a path from the source to the destination of the trip). On the other hand, BAG chooses the distribution in space and time of the controls over the network. The goal for the BAG is to maximize the toll revenue (or to minimize the number of evaders), taking into account that the drivers will take their decision in order to minimize their expected loss (which depends on the level of control along their route).
This optimal control distribution can be computed with a linear program and specifies the optimal probabilities by which a particular control duty should be chosen. We plan to generate randomized control duties accordingly, and to use our tool TC-OPT to include them in a monthly roster.
