Wednesday, 15:45 - 16:10 h, Room: H 0106


Elmar Swarat
Modeling and solving a toll enforcement problem

Coauthors: Ralf Borndörfer, Guillaume Sagnol


We present the Toll Enforcement Problem to optimize the tours of toll inspectors on German motorways. This is an integrated planning and scheduling model, consisting of a tour planning and a duty rostering part. The goal is to achieve a network-wide control proportional to the traffic distribution. We introduce a time-expanded planning graph, based on a given time discretization, where computing the tours corresponds to a Multi-Commodity flow problem. This is formulated as an IP using path variables. For the rostering problem we develop a graph model, where arcs model feasible sequences of duties. Finding feasible rosters again comes up to a Multi-Commodity flow problem in an IP formulation. By introducing coupling constraints, both problems were connected to an integrated model. We will show, that many important requirements and legal rules can be modeled by this approach. By our modeling issues the extreme complexity of our problem can be reduced to reasonable size problem instances. Computational experiments on several real-world instances indicate that we are able to solve them to a proven optimality with only a small gap.


Talk 2 of the contributed session Wed.3.H 0106
"Vehicle and crew planning" [...]
Cluster 13
"Logistics, traffic, and transportation" [...]


  pay day loans . In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.