Uncertainty in Real-World Vehicle Routing (Extended Abstract)

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00141880" target="_blank" >RIV/00216224:14330/25:00141880 - isvavai.cz</a>

Výsledek na webu

<a href="https://ojs.aaai.org/index.php/SOCS/article/view/36013" target="_blank" >https://ojs.aaai.org/index.php/SOCS/article/view/36013</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/socs.v18i1.36013" target="_blank" >10.1609/socs.v18i1.36013</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Uncertainty in Real-World Vehicle Routing (Extended Abstract)

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Uncertainty in Real-World Vehicle Routing (Extended Abstract)

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

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 statě ve sborníku

18th International Symposium on Combinatorial Search, SoCS 2025

ISBN

9781577359012

ISSN

—

e-ISSN

—

Počet stran výsledku

2

Strana od-do

269-270

Název nakladatele

AAAI Press

Místo vydání

Washington, DC, USA

Místo konání akce

Glasgow, United Kingdom

Datum konání akce

1. 1. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—