Multi-Depot Vehicle Routing Problem with Drones: Mathematical Formulation, Solution Algorithm and Experiments

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60162694%3AG42__%2F25%3A00560709" target="_blank" >RIV/60162694:G42__/25:00560709 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S0957417423029858" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0957417423029858</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.eswa.2023.122483" target="_blank" >10.1016/j.eswa.2023.122483</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Multi-Depot Vehicle Routing Problem with Drones: Mathematical Formulation, Solution Algorithm and Experiments

Popis výsledku v původním jazyce

The use of Unmanned Aerial Vehicles (UAVs) is expected to grow rapidly in the coming years, driven by technological advancements, cost-effectiveness, and the increasing demand for faster and more efficient delivery solutions. This article deals with the mathematical formulation of the Multi-Depot Vehicle Routing Problem with Drones (MDVRP-D), whereby a set of heterogeneous trucks, each paired with a UAV, are located in different depots. Both types of vehicles deliver goods to customers; UAVs are dispatched from trucks while en route to make the last-mile delivery. A metaheuristic algorithm based on the Ant Colony Optimization (ACO) principle is proposed as the solution. This algorithm has been adapted for this newly proposed problem; the novel mechanics include the probabilistic decision to dispatch an UAV, the selection of a customer to be served, and local search optimization. Extensive computational experiments are performed to verify the proposed algorithm. First, its performance is compared with Adaptive Large Neighborhood Search (ALNS) metaheuristics on a set of Vehicle Routing Problem with Drones (VRP-D) benchmarks. A set of various benchmark instances are subsequently proposed for the newly formulated MDVRP-D (differing in complexity and graph topology). Finally, the behavior of the proposed algorithm is thoroughly analyzed, especially in respect of features connected with UAVs. The findings presented in this article provide valuable contributions to the NP-hard models related to the Travelling Salesman Problem (TSP) and to the very popular ACO-based algorithms.

Název v anglickém jazyce

Multi-Depot Vehicle Routing Problem with Drones: Mathematical Formulation, Solution Algorithm and Experiments

Popis výsledku anglicky

The use of Unmanned Aerial Vehicles (UAVs) is expected to grow rapidly in the coming years, driven by technological advancements, cost-effectiveness, and the increasing demand for faster and more efficient delivery solutions. This article deals with the mathematical formulation of the Multi-Depot Vehicle Routing Problem with Drones (MDVRP-D), whereby a set of heterogeneous trucks, each paired with a UAV, are located in different depots. Both types of vehicles deliver goods to customers; UAVs are dispatched from trucks while en route to make the last-mile delivery. A metaheuristic algorithm based on the Ant Colony Optimization (ACO) principle is proposed as the solution. This algorithm has been adapted for this newly proposed problem; the novel mechanics include the probabilistic decision to dispatch an UAV, the selection of a customer to be served, and local search optimization. Extensive computational experiments are performed to verify the proposed algorithm. First, its performance is compared with Adaptive Large Neighborhood Search (ALNS) metaheuristics on a set of Vehicle Routing Problem with Drones (VRP-D) benchmarks. A set of various benchmark instances are subsequently proposed for the newly formulated MDVRP-D (differing in complexity and graph topology). Finally, the behavior of the proposed algorithm is thoroughly analyzed, especially in respect of features connected with UAVs. The findings presented in this article provide valuable contributions to the NP-hard models related to the Travelling Salesman Problem (TSP) and to the very popular ACO-based algorithms.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

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 periodika

EXPERT SYSTEMS WITH APPLICATIONS

ISSN

0957-4174

e-ISSN

1873-6793

Svazek periodika

241

Číslo periodika v rámci svazku

1 May 2024

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

23

Strana od-do

122483

Kód UT WoS článku

001129525300001

EID výsledku v databázi Scopus

2-s2.0-85179010514