Arc-routing for winter road maintenance

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10438390" target="_blank" >RIV/00216208:11320/21:10438390 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1E0xSfHTCe" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1E0xSfHTCe</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.disopt.2021.100644" target="_blank" >10.1016/j.disopt.2021.100644</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Arc-routing for winter road maintenance

Popis výsledku v původním jazyce

The winter road maintenance arc-routing is recognized as a notoriously hard problem not only from the algorithmic point of view. This paper lays down foundations of theoretical understanding of our new winter road maintenance optimization for the Plzen region of the Czech Republic which has been implemented by the regional authorities since the winter of 2019-20. Our approach is not, contrary to most of existing work, based on the integer and linear programming machinery. We concentrate on studying arc-routing on trees. This is practical since routes of single vehicles can be well represented by trees, and allows algorithms and complementary hardness results. We then extend the approach to the bounded tree width graphs. This leads to considering planar graphs which well abstract the realistic road networks. We formalize important aspects of the winter road maintenance problem which were not formalized before, e.g., public complaints. The number of complaints from public against the winter road maintenance is a quantitative measure of the quality of the service which is focused on, e.g., in media or in election campaigns. A fear of &apos;complaints&apos; is a fact every optimizer must deal with. Hence, a formal model of public complaints and its inclusion in the optimization is vital. Our formalization of the winter road maintenance is robust in the sense that it relates to well-known extensively studied concepts of discrete mathematics like graph cutting and splitting of necklaces. (C) 2021 Elsevier B.V. All rights reserved.

Název v anglickém jazyce

Arc-routing for winter road maintenance

Popis výsledku anglicky

The winter road maintenance arc-routing is recognized as a notoriously hard problem not only from the algorithmic point of view. This paper lays down foundations of theoretical understanding of our new winter road maintenance optimization for the Plzen region of the Czech Republic which has been implemented by the regional authorities since the winter of 2019-20. Our approach is not, contrary to most of existing work, based on the integer and linear programming machinery. We concentrate on studying arc-routing on trees. This is practical since routes of single vehicles can be well represented by trees, and allows algorithms and complementary hardness results. We then extend the approach to the bounded tree width graphs. This leads to considering planar graphs which well abstract the realistic road networks. We formalize important aspects of the winter road maintenance problem which were not formalized before, e.g., public complaints. The number of complaints from public against the winter road maintenance is a quantitative measure of the quality of the service which is focused on, e.g., in media or in election campaigns. A fear of &apos;complaints&apos; is a fact every optimizer must deal with. Hence, a formal model of public complaints and its inclusion in the optimization is vital. Our formalization of the winter road maintenance is robust in the sense that it relates to well-known extensively studied concepts of discrete mathematics like graph cutting and splitting of necklaces. (C) 2021 Elsevier B.V. All rights reserved.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GJ17-10090Y" target="_blank" >GJ17-10090Y: Optimalizace sítí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Optimization

ISSN

1572-5286

e-ISSN

—

Svazek periodika

41

Číslo periodika v rámci svazku

August 2021

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

100644

Kód UT WoS článku

000683549500004

EID výsledku v databázi Scopus

2-s2.0-85105287782