All trucks with at least 7.5 tonnes weight have to pay a distance-based toll on German motorways and also on several 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 300 permanently installed control gantries operated by the technical system provider, Toll Collect. On the other hand a mobile control is done by almost 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 with stochastic influence that take 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. A first release of our algorithm TC-OPT is in operation at the enforcement agency.

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. One criterion for the tour planning is that the whole network should be covered by the tours. Beside that minimum requirement, the sections shall be controlled according to the traffic distribution. In addition we want to analyze and model the behaviour of toll evaders, such that this aspect could also be used as a criterion for our tour planning. In particular, 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 an optimization tool called TC-OPT. For the second phase (until 2016), 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. Both are modeled by appropriate planning graphs. In those graphs feasible tours and rosters are represented by paths. Based on these graph models it is possible to formulate both problems as "Multi-Commodity Flow Problems", and solve them by using an integer program (IP) with coupling constraints. Therefore, legal work rules are either implicitly modeled by the graph structure or by resource or base constraints in the IP.

The yellow path in the figure below represents a feasible weekly control tour on a small subregion for a single inspector. The possible shifts for the days are "early" (E), "day" (D) and "late" (L) as well as "Free". In the back, the traffic distribution on the respective subregion over the week is depicted.

RosterGraph

 

During the first phase we developed a prototype of our optimization tool. The tool, called TC-OPT, is implemented in C++ and it interfaces the commercial software tool  "IVU.plan" by IVU AG. In the second 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 bounds on unsocial work hours, duty requests or the use of additional working time windows. Furthermore, the new version will make it possible to compute duty rosters based on some random duties 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.

 

 Ausleitung eines LKW ©BAG

 

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.

 

Control distribution Germany