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" [...]


  Online lending company provides a wide range of ways to get money by means of Tennessee Payday Loans. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.