License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09261.18
URN: urn:nbn:de:0030-drops-21635
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2163/
Go to the corresponding Portal

Irnich, Stefan

New Models and Methods for Arc Routing

pdf-format:
09261.IrnichStefan.ExtAbstract.2163.pdf (0.3 MB)

Abstract

The talk presents two non-standard extensions for single-vehicle arc-routing problems a.k.a. postman problems: First, street segments that require a service on both sides of the street can be covered either by two separate services or by a single zigzag service. Instead of deciding the type of service beforehand, we propose to take into account the zigzagging option when designing a tour. We present MIP models for the extension of Undirected Chinese and Rural Postman Problem (UCPP, URPP). We show that these models can be solved reasonable well using a cutting-plane or branch-and-cut algorithm.
Second, capacitated postman problems occur as subproblems in column-generation and Lagrangian-relaxation approaches of the capacitated arc-routing problem. In order to model these and similar subproblems or submodels, we present the Profitable Capacitated Rural Postman Problem (PCRPP): In the PCRPP, edges that are serviced give a profit, but deadheading through edges generates costs. Both service and deadheading consume time. The task is to find a tour that maximizes the difference of profits and costs, while the overall duration of the tour must not exceed a given bound. The solution approach for this problem is again based on branch-and-cut.

BibTeX - Entry

@InProceedings{irnich:DagSemProc.09261.18,
  author =	{Irnich, Stefan},
  title =	{{New Models and Methods for Arc Routing}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/2163},
  URN =		{urn:nbn:de:0030-drops-21635},
  doi =		{10.4230/DagSemProc.09261.18},
  annote =	{Keywords: Postman problems, branch-and-cut}
}

Keywords: Postman problems, branch-and-cut
Collection: 09261 - Models and Algorithms for Optimization in Logistics
Issue Date: 2009
Date of publication: 02.10.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI