Uncertainty in Real-World Vehicle Routing (Extended Abstract)

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Uncertainty in Real-World Vehicle Routing (Extended Abstract)

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

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

Publication year

2025

Confidentiality

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

Article name in the collection

18th International Symposium on Combinatorial Search, SoCS 2025

ISBN

9781577359012

ISSN

—

e-ISSN

—

Number of pages

2

Pages from-to

269-270

Publisher name

AAAI Press

Place of publication

Washington, DC, USA

Event location

Glasgow, United Kingdom

Event date

Jan 1, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—