Reoptimisation strategies for dynamic vehicle routing problems with proximity-dependent nodes

Andersen, Tiria, Belward, Shaun, Sankupellay, Mangalam, Myers, Trina, and Chen, Carla (2024) Reoptimisation strategies for dynamic vehicle routing problems with proximity-dependent nodes. TOP, 32. pp. 1-21.

[img]
Preview
PDF (Publisher Accepted Version) - Published Version
Available under License Creative Commons Attribution.

Download (1MB) | Preview
View at Publisher Website: https://doi.org/10.1007/s11750-023-00656...
 
344


Abstract

Autonomous vehicles create new opportunities as well as new challenges to dynamic vehicle routing. The introduction of autonomous vehicles as information-collecting agents results in scenarios, where dynamic nodes are found by proximity. This paper presents a novel dynamic vehicle-routing problem variant with proximity-dependent nodes. Here, we introduced a novel variable, detectability, which determines whether a proximal dynamic node will be detected, based on the sight radius of the vehicle. The problem considered is motivated by autonomous weed-spraying vehicles in large agricultural operations. This work is generalisable to many other autonomous vehicle applications. The first step to crafting a solution approach for the problem is to decide when reoptimisation should be triggered. Two reoptimisation trigger strategies are considered—exogenous and endogenous. Computational experiments compared the strategies for both the classical dynamic vehicle routing problem as well as the introduced variant. Experiments used extensive standardised vehicle-routing problem benchmarks with varying degrees of dynamism and geographical node distributions. The results showed that for both the classical problem and the novel variant, an endogenous trigger strategy is better in most cases, while an exogenous trigger strategy is only suitable when both detectability and dynamism are low. Furthermore, the optimal level of detectability was shown to be dependent on the combination of trigger, degree of dynamism, and geographical node distribution, meaning practitioners may determine the required detectability based on the attributes of their specific problem.

Item ID: 79014
Item Type: Article (Research - C1)
ISSN: 1863-8279
Keywords: Autonomous vehicles, Dynamic, Proximity-dependent, Vehicle routing
Copyright Information: This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Date Deposited: 14 Jun 2023 23:34
FoR Codes: 49 MATHEMATICAL SCIENCES > 4903 Numerical and computational mathematics > 490304 Optimisation @ 100%
SEO Codes: 15 ECONOMIC FRAMEWORK > 1505 Microeconomics > 150510 Production @ 100%
Downloads: Total: 344
Last 12 Months: 31
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page