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

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

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Name of the periodical

EXPERT SYSTEMS WITH APPLICATIONS

ISSN

0957-4174

e-ISSN

1873-6793

Volume of the periodical

241

Issue of the periodical within the volume

1 May 2024

Country of publishing house

GB - UNITED KINGDOM

Number of pages

23

Pages from-to

122483

UT code for WoS article

001129525300001

EID of the result in the Scopus database

2-s2.0-85179010514