Uncertainty in Real-World Vehicle Routing (Extended Abstract)

Abstract

In our paper, we aim to address common sources of uncertainty in real-world industrial vehicle routing problems. By extending traditional deterministic heuristic solvers with easy-to-integrate, reusable, and computationally efficient mechanisms, we introduce reasoning about uncertainty while retaining the capability of scaling to problems with up to 1,000 customers. We formulate four such mechanisms, including standard chance constraints, two data manipulation methods, and a novel penalty-based method. These mechanisms are evaluated on both standard benchmarks and real-world industrial vehicle routing instances, and their key search-related properties are discussed. This extended abstract presents results previously published at the European Conference on Artificial Intelligence 2024.