Arc-routing for winter road maintenance
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Arc-routing for winter road maintenance
Original language description
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 'complaints' 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GJ17-10090Y" target="_blank" >GJ17-10090Y: Network Optimization</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Discrete Optimization
ISSN
1572-5286
e-ISSN
—
Volume of the periodical
41
Issue of the periodical within the volume
August 2021
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
18
Pages from-to
100644
UT code for WoS article
000683549500004
EID of the result in the Scopus database
2-s2.0-85105287782