Problem

The project "Optimization of Toll Control Tours" aims at developing models and algorithms for planning the tours of toll controllers 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 requirement 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 criteria 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 analyse and model the behaviour of toll evaders, such that this aspect could also be used as a citerion for our tour planning.

Our main goal is the computation of operable monthly duty plans for each regional control area. But also planning scenarios including several control areas should be supported.

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 not anonymous 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 we want to test and implement several solution approaches for the integrated problem.

One of our approaches consists in modelling both problems as "Multi-Commodity Flow Problems", and formulate them as an integer program with coupling constraints. Another very promising approach is the enhancement of conventional vehicle-routing-heuristics. The goal of the first stage of this project is to test several solution methods. The most efficient one will be implemented as the optimization kernel of a duty planning software.

During the first year we developed a prototype of our optimization tool. The tool, called TC-OPT, is implemented in C++ and uses currently an interface based on csv-Files.

Simulation

A simulation software based on "Java View" is being developped, to visualize the truck traffic and to simulate the occurrence of toll evaders in the network. Hence, this tool allows an evaluation of the quality and the efficiency of a control plan and an empirical analysis of the toll evader distribution.

Optimal Experimental Design

The theory of "Optimal Eperimental Design" is an important branch of statistics, which explains how to best select experiments when the goal is to estimate an unknown parameter. A possibility is to consider the control tours as "experiments", in which sampled measurements from the number of toll evaders are performed. Therefore, a part of this project is devoted to the application of "optimal experimental design" methods for the modelling and the resolution of the toll control tour problem.

Game Theory

We have developped a model based on game theory to optimize the control
strategy of the BAG. In our model, the controllers and the truck drivers are playing a game, in which each driver has the choice between two possible actions (pay or evade), and the 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 (pay or evade) in order to mimize their expected loss (which depends of the level of control along their route). A simple linear program can be
used to find the optimal control distribution with respect to this goal, and we plan to use this theoretical control strategy as a target in our control planning tool.

• Elmar Swarat

• Ralf Borndörfer
  
• Guillaume Sagnol
  
• Elmar Swarat

• Federal Office for Goods Transport (BAG)
  
• IVU Traffic Technologies AG

Federal Office for Goods Transport (BAG)

Duration: 06.2010-05.2013