A Case Study on Optimizing Toll Enforcements on Motorways

Please always quote using this URN: urn:nbn:de:0297-zib-15498
  • In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Ralf Borndörfer, Guillaume Sagnol, Elmar Swarat
Document Type:ZIB-Report
Tag:Duty Rostering; Integer Programming; Operations Research; Vehicle Routing Problem
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
CCS-Classification:G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.3 Applications (NEW)
Date of first Publication:2012/05/31
Series (Serial Number):ZIB-Report (12-21)
ISSN:1438-0064
Published in:Appeared in: 3rd Student Conference on Operational Research. S. Ravizza, P. Holborn (eds.) Open Acess Series in Informatics 22 (2012) pp. 1-10
DOI:http://dx.doi.org/10.4230/OASIcs.SCOR.2012.1
Licence (German):License LogoCreative Commons - Namensnennung

$Rev: 13581 $