DROPS

Document

DOI: 10.4230/OASIcs.SCOR.2012.1

A Case Study on Optimizing Toll Enforcements on Motorways

Authors: Ralf Borndörfer, Guillaume Sagnol, and Elmar Swarat

Published in: OASIcs, Volume 22, 3rd Student Conference on Operational Research (2012)

Abstract

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.

Cite as

Ralf Borndörfer, Guillaume Sagnol, and Elmar Swarat. A Case Study on Optimizing Toll Enforcements on Motorways. In 3rd Student Conference on Operational Research. Open Access Series in Informatics (OASIcs), Volume 22, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.SCOR.2012.1,
  author =	{Bornd\"{o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar},
  title =	{{A Case Study on Optimizing Toll Enforcements on Motorways}},
  booktitle =	{3rd Student Conference on Operational Research},
  pages =	{1--10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-39-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{22},
  editor =	{Ravizza, Stefan and Holborn, Penny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2012.1},
  URN =		{urn:nbn:de:0030-drops-35418},
  doi =		{10.4230/OASIcs.SCOR.2012.1},
  annote =	{Keywords: Vehicle Routing Problem, Duty Rostering, Integer Programming, Operations Research}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2008.1580

The Second Chvatal Closure Can Yield Better Railway Timetables

Authors: Christian Liebchen and Elmar Swarat

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract

We investigate the polyhedral structure of the Periodic Event Scheduling Problem (PESP), which is commonly used in periodic railway timetable optimization. This is the first investigation of Chvatal closures and of the Chvatal rank of PESP instances. In most detail, we first provide a PESP instance on only two events, whose Chvatal rank is very large. Second, we identify an instance for which we prove that it is feasible over the first Chvatal closure, and also feasible for another prominent class of known valid inequalities, which we reveal to live in much larger Chvatal closures. In contrast, this instance turns out to be infeasible already over the second Chvatal closure. We obtain the latter result by introducing new valid inequalities for the PESP, the multi-circuit cuts. In the past, for other classes of valid inequalities for the PESP, it had been observed that these do not have any effect in practical computations. In contrast, the new multi-circuit cuts that we are introducing here indeed show some effect in the computations that we perform on several real-world instances - a positive effect, in most of the cases.

Cite as

Christian Liebchen and Elmar Swarat. The Second Chvatal Closure Can Yield Better Railway Timetables. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{liebchen_et_al:OASIcs.ATMOS.2008.1580,
  author =	{Liebchen, Christian and Swarat, Elmar},
  title =	{{The Second Chvatal Closure Can Yield Better Railway Timetables}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1580},
  URN =		{urn:nbn:de:0030-drops-15802},
  doi =		{10.4230/OASIcs.ATMOS.2008.1580},
  annote =	{Keywords: }
}

Search Results

Documents authored by Swarat, Elmar

A Case Study on Optimizing Toll Enforcements on Motorways

Abstract

Cite as

The Second Chvatal Closure Can Yield Better Railway Timetables

Abstract

Cite as

Thanks for your feedback!

Could not send message