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.

RosterGraph

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.

 

 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

 

Publications

2023
A Comparison of Models for Rolling Stock Scheduling 2023 (under review) Boris Grimm, Rowan Hoogervorst, Ralf Borndörfer BibTeX
DOI
arXiv
Optimal Toll Enforcement
Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pp. 13:1-13:15, Vol.115, Open Access Series in Informatics (OASIcs), 2023 Boris Grimm, Ralf Borndörfer, Julian Bushe PDF
BibTeX
DOI
Optimal Toll Enforcement
Vertex Covering with Capacitated Trees Networks, 81(2), pp. 253-277, 2023 (preprint available as ZIB-Report 21-14) Ralf Borndörfer, Stephan Schwartz, William Surau PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
2022
An overview of graph covering and partitioning Discrete Mathematics, 345(8), 2022 (preprint available as ZIB-Report 20-24) Stephan Schwartz PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
Finding Minimum Balanced Separators - an Exact Approach Operations Research Proceedings 2021, pp. 154-159, 2022 Ralf Borndörfer, Stephan Schwartz, William Surau PDF
BibTeX
URN
DOI
Optimal Toll Enforcement
Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7–10, 2022, pp. 63-68, 2022 (preprint available as ZIB-Report 21-34) Ralf Borndörfer, Stephan Schwartz, William Surau PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
2021
An LP-based heuristic for Inspector Scheduling Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I, pp. 77-86, Vol.1, 2021 Gerwin Gamrath, Markus Reuther, Thomas Schlechte, Elmar Swarat BibTeX
Optimal Toll Enforcement
Connected k-partition of k-connected graphs and c-claw-free graphs Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, pp. 27:1-27:14, Vol.207, LIPIcs, 2021 Ralf Borndörfer, Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz, Ziena Zeif BibTeX
DOI
URN
Optimal Toll Enforcement
2019
Approximating Balanced Graph Partitions ZIB-Report 19-25 Ralf Borndörfer, Ziena Elijazyfer, Stephan Schwartz PDF
BibTeX
URN
Optimal Toll Enforcement
2018
Algorithmic Analysis of the Graph Segmentation Problem Master's thesis, Freie Universität Berlin, Ralf Borndörfer, Tim Conrad (Advisors), 2018 Vanessa Schreck BibTeX
Optimal Toll Enforcement
Längenbeschränkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung Master's thesis, Freie Universität Berlin, Ralf Borndörfer (Advisor), 2018 Ziena Elijazyfer BibTeX
Optimal Toll Enforcement
On Finding Subpaths With High Demand Operations Research Proceedings 2017, pp. 355-360, 2018 (preprint available as ZIB-Report 18-27) Stephan Schwartz, Ralf Borndörfer, Leonardo Balestrieri PDF (ZIB-Report)
BibTeX
Optimal Toll Enforcement
The Graph Segmentation Problem INOC 2017 – 8th International Network Optimization Conference, pp. 35-44, Vol.64, Electronic Notes in Discrete Mathematics, 2018 (preprint available as ) Ralf Borndörfer, Stephan Schwartz, Gerald Bartz BibTeX
Optimal Toll Enforcement
2017
Designing Inspector Rosters with Optimal Strategies Operations Research Proceedings 2016, pp. 217-223, 2017 (preprint available as ZIB-Report 16-65) Stephan Schwartz, Thomas Schlechte, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
2016
A Coarse-to-Fine Approach for the Workforce Scheduling of Teams Master's thesis, Technische Universität Berlin, Elmar Swarat (Advisor), 2016 Gerwin Gamrath BibTeX
Optimal Toll Enforcement
An Extended Network Interdiction Problem for Optimal Toll Control INOC 2015 – 7th International Network Optimization Conference, pp. 301-308, Vol.52, Electronic Notes in Discrete Mathematics, 2016 (preprint available as ZIB-Report 15-32) Ralf Borndörfer, Guillaume Sagnol, Stephan Schwartz PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
Optimal duty rostering for toll enforcement inspectors Annals of Operations Research, Vol.252(2), pp. 383-406, 2016 (preprint available as ZIB-Report 13-79) Ralf Borndörfer, Guillaume Sagnol, Thomas Schlechte, Elmar Swarat PDF (ZIB-Report)
PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
2015
Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015), 2015 (preprint available as ZIB-Report 15-44) Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Christof Schulz, Elmar Swarat, Steffen Weider PDF (ZIB-Report)
BibTeX
Optimal Toll Enforcement
Network spot-checking games: Theory and application to toll enforcing in transportation networks Networks, Vol.65, pp. 312-328, 2015 (preprint available as ZIB-Report 14-07) Ralf Borndörfer, Julia Buwaya, Guillaume Sagnol, Elmar Swarat PDF (ZIB-Report)
PDF (ZIB-Report)
PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
2014
The Price of Spite in Spot-checking games 7th International Symposium on Algorithmic Game Theory (SAGT'2014), Ron Lavi (Ed.), p. 293, Vol.8768, Lecture Notes in Computer Science, 2014, ISBN: 978-3-662-44802-1 (preprint available as ZIB-Report 14-38) Guillaume Sagnol, Ralf Borndörfer, Thomas Schlechte, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
2013
Bilevel Programming to Optimize the Use of Traffic Control Gantries for Toll Enforcement Master's thesis, Freie Universität Berlin, Ralf Borndörfer, Guillaume Sagnol (Advisors), 2013 Stephan Schwartz PDF
BibTeX
URN
Optimal Toll Enforcement
Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach Proceedings of INOC'2013, pp. 253-260, Vol.41, Electronic Notes in Discrete Mathematics, 2013 (preprint available as ZIB-Report 12-47) Ralf Borndörfer, Julia Buwaya, Guillaume Sagnol, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
2012
A Case Study on Optimizing Toll Enforcements on Motorways 3rd Student Conference on Operational Research, pp. 1-10, Vol.22, OpenAccess Series in Informatics (OASIcs), 2012 (preprint available as ZIB-Report 12-21) Ralf Borndörfer, Guillaume Sagnol, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
A Stackelberg game to optimize the distribution of controls in transportation networks Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012), pp. 224-235, Vol.105, Lecture Notes of the ICST, 2012 (preprint available as ZIB-Report 12-15) Ralf Borndörfer, Bertrand Omont, Guillaume Sagnol, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
An IP Approach to Toll Enforcement Optimization on German Motorways Operations Research Proceedings 2011, pp. 317-322, Operations Research Proceedings, 2012 (preprint available as ZIB-Report 11-42) Ralf Borndörfer, Guillaume Sagnol, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement
Network-related problems in optimal experimental design and second order cone programming Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications, pp. 161-171, Vol.51, 2012 (preprint available as ZIB-Report 11-52) Guillaume Sagnol PDF (ZIB-Report)
BibTeX
DOI
Optimal Toll Enforcement