2026-08-16T04:05:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2163 2024-03-06T11:08:50Z ddc:004 open_access

New Models and Methods for Arc Routing Irnich, Stefan Postman problems branch-and-cut 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Irnich 2009 Is Part Of Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09261.18 urn:nbn:de:0030-drops-21635 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.18 eng https://creativecommons.org/licenses/by/4.0/legalcode