Uncertainty in Real-World Vehicle Routing (Extended Abstract)

D 2025

Uncertainty in Real-World Vehicle Routing (Extended Abstract)

SOBOTKA, Václav a Hana RUDOVÁ

Základní údaje

Originální název

Uncertainty in Real-World Vehicle Routing (Extended Abstract)

Autoři

SOBOTKA, Václav a Hana RUDOVÁ

Vydání

Washington, DC, USA, 18th International Symposium on Combinatorial Search, SoCS 2025, od s. 269-270, 2 s. 2025

Nakladatel

AAAI Press

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00141880

Organizační jednotka

Fakulta informatiky

ISBN

978-1-57735-901-2

DOI

https://doi.org/10.1609/socs.v18i1.36013

EID Scopus

2-s2.0-105012221603

Klíčová slova anglicky

Vehicle routing; Uncertainty; Search; Heuristics; Real-life applications; Combinatorial optimization

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 9. 4. 2026 05:07, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

The motivation for our research arises from the limitations of traditional deterministic heuristic solvers for vehicle routing problems (VRP) observed in industrial practice. In general, the quantities provided to the solvers as inputs, e.g., loads or service times, are typically estimates or simplifying reflections of reality. While current state-of-the-art solvers are applicable to complex VRP variants at scale, their inability to reason about uncertainties limits their usefulness in real-world applications. Despite stochastic VRPs being a widely studied topic, related approaches are typically centered around the uncertainty in the problem rather than extending successful deterministic methods. Moreover, uncertainty-related methodologies and models are often strongly linked to computationally expensive sampling or exact algorithms making their scaling problematic. Thus, we aim for easy-to-integrate, reusable, and especially computationally efficient mechanisms, allowing us to naturally extend state-of-the-art heuristic solvers for a wide range of VRPs with reasoning about input uncertainties. We formulate four mechanisms fitting these criteria, including standard chance constraints, two data manipulation methods, and a novel penalty-based method. These four mechanisms are compared and analyzed for the most common sources of uncertainty in loads and times on both benchmark and complex real-world instances. Their favorable scaling properties are demonstrated on instances with up to 1,000 customers.

Návaznosti

MUNI/A/1709/2024, interní kód MU

Název: Aplikovaný výzkum na FI: Důvěra v dynamických softwarových ekosystémech, kryptografické implementace včetně uživatelských aspektů, kyberbezpečnostní cvičení, fúze dat pro fyzikální sensory a algoritmy plánování v logistice

Investor: Masarykova univerzita, Aplikovaný výzkum na FI: Důvěra v dynamických softwarových ekosystémech, kryptografické implementace včetně uživatelských aspektů, kyberbezpečnostní cvičení, fúze dat pro fyzikální sensory a algoritmy plánování v logistice

Citovat

SOBOTKA, Václav a Hana RUDOVÁ. Uncertainty in Real-World Vehicle Routing (Extended Abstract). Online. In Maxim Likhachev, Hana Rudová, Enrico Scala. 18th International Symposium on Combinatorial Search, SoCS 2025. Washington, DC, USA: AAAI Press, 2025, s. 269-270. ISBN 978-1-57735-901-2. Dostupné z: https://doi.org/10.1609/socs.v18i1.36013.

@inproceedings{2514897,
   author = {Sobotka, Václav and Rudová, Hana},
   address = {Washington, DC, USA},
   booktitle = {18th International Symposium on Combinatorial Search, SoCS 2025},
   doi = {https://doi.org/10.1609/socs.v18i1.36013},
   editor = {Maxim Likhachev, Hana Rudová, Enrico Scala},
   keywords = {Vehicle routing; Uncertainty; Search; Heuristics; Real-life applications; Combinatorial optimization},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Washington, DC, USA},
   isbn = {978-1-57735-901-2},
   pages = {269-270},
   publisher = {AAAI Press},
   title = {Uncertainty in Real-World Vehicle Routing (Extended Abstract)},
   url = {https://ojs.aaai.org/index.php/SOCS/article/view/36013},
   year = {2025}
}

TY  - CONF
ID  - 2514897
AU  - Sobotka, Václav - Rudová, Hana
PY  - 2025
TI  - Uncertainty in Real-World Vehicle Routing (Extended Abstract)
PB  - AAAI Press
CY  - Washington, DC, USA
SN  - 9781577359012
KW  - Vehicle routing
KW  - Uncertainty
KW  - Search
KW  - Heuristics
KW  - Real-life applications
KW  - Combinatorial optimization
UR  - https://ojs.aaai.org/index.php/SOCS/article/view/36013
N2  - The motivation for our research arises from the limitations of traditional deterministic heuristic solvers for vehicle routing problems (VRP) observed in industrial practice. In general, the quantities provided to the solvers as inputs, e.g., loads or service times, are typically estimates or simplifying reflections of reality. While current state-of-the-art solvers are applicable to complex VRP variants at scale, their inability to reason about uncertainties limits their usefulness in real-world applications. Despite stochastic VRPs being a widely studied topic, related approaches are typically centered around the uncertainty in the problem rather than extending successful deterministic methods. Moreover, uncertainty-related methodologies and models are often strongly linked to computationally expensive sampling or exact algorithms making their scaling problematic. Thus, we aim for easy-to-integrate, reusable, and especially computationally efficient mechanisms, allowing us to naturally extend state-of-the-art heuristic solvers for a wide range of VRPs with reasoning about input uncertainties. We formulate four mechanisms fitting these criteria, including standard chance constraints, two data manipulation methods, and a novel penalty-based method. These four mechanisms are compared and analyzed for the most common sources of uncertainty in loads and times on both benchmark and complex real-world instances. Their favorable scaling properties are demonstrated on instances with up to 1,000 customers.
ER  -

SOBOTKA, Václav a Hana RUDOVÁ. Uncertainty in Real-World Vehicle Routing (Extended Abstract). Online. In Maxim Likhachev, Hana Rudová, Enrico Scala. \textit{18th International Symposium on Combinatorial Search, SoCS 2025}. Washington, DC, USA: AAAI Press, 2025, s.~269-270. ISBN~978-1-57735-901-2. Dostupné z: https://doi.org/10.1609/socs.v18i1.36013.

Přehled o publikaci