Cover Image

The min-cost parallel drone scheduling vehicle routing problem

Adopting unmanned aerial vehicles (UAV), also known as drones, into the last-mile-delivery sector and having them work alongside trucks with the aim of improving service quality and reducing the transportation cost gives rise to a new class of Vehicle Routing Problems (VRPs). In this paper, we intro...

Full description

Saved in:
Bibliographic Details
Main Authors: Minh Anh Nguyen, Giang Thi-Huong Dang, Minh Hoàng Hà, Minh-Trien Pham
Format: Bài trích
Language:eng
Published: European Journal of Operational Research 2021
Subjects:
Transportation
Vehicle routing problem
Drone parallel scheduling
Online Access:https://www.sciencedirect.com/science/article/abs/pii/S0377221721006032?via%3Dihub
https://dlib.phenikaa-uni.edu.vn/handle/PNK/2862
https://doi.org/10.1016/j.ejor.2021.07.008
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-2862
record_format dspace
spelling oai:localhost:PNK-28622022-08-17T05:54:49Z The min-cost parallel drone scheduling vehicle routing problem Minh Anh Nguyen Giang Thi-Huong Dang Minh Hoàng Hà Minh-Trien Pham Transportation Vehicle routing problem Drone parallel scheduling Adopting unmanned aerial vehicles (UAV), also known as drones, into the last-mile-delivery sector and having them work alongside trucks with the aim of improving service quality and reducing the transportation cost gives rise to a new class of Vehicle Routing Problems (VRPs). In this paper, we introduce a new optimization problem called the min-cost Parallel Drone Scheduling Vehicle Routing Problem (PDSVRP). This problem is a variant of the well-known Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP) recently introduced in the literature in which we allow multiple trucks and consider the objective of minimizing the total transportation costs. We formulate the problem as a Mixed Integer Linear Program and then develop a Ruin and Recreate () algorithm. Exploiting PDSVRP solution characteristics in an effective manner, our heuristic manages to introduce “sufficient” rooms to a solution via new removal operators during the ruin phase. It is expected to enhance the possibilities for improving solutions later in the recreate phase. Multiple experiments on a new set of randomly generated instances confirm the performance of our approach. To explore the benefits of drone delivery as well as the insight into the impact of related factors on the contribution of drones’ use to operational cost, a sensitivity analysis is conducted. We also adapt the proposed algorithm to solve the PDSTSP and validate it via benchmarks available in the literature. It is shown that our algorithm outperforms state-of-the-art algorithms in terms of solution quality. Out of 90 considered instances, it finds 26 new best known solutions. 2021-09-14T07:14:55Z 2021-09-14T07:14:55Z 2021 Bài trích https://www.sciencedirect.com/science/article/abs/pii/S0377221721006032?via%3Dihub https://dlib.phenikaa-uni.edu.vn/handle/PNK/2862 https://doi.org/10.1016/j.ejor.2021.07.008 eng European Journal of Operational Research
institution Digital Phenikaa
collection Digital Phenikaa
language eng
topic Transportation
Vehicle routing problem
Drone parallel scheduling
spellingShingle Transportation
Vehicle routing problem
Drone parallel scheduling
Minh Anh Nguyen
Giang Thi-Huong Dang
Minh Hoàng Hà
Minh-Trien Pham
The min-cost parallel drone scheduling vehicle routing problem
description Adopting unmanned aerial vehicles (UAV), also known as drones, into the last-mile-delivery sector and having them work alongside trucks with the aim of improving service quality and reducing the transportation cost gives rise to a new class of Vehicle Routing Problems (VRPs). In this paper, we introduce a new optimization problem called the min-cost Parallel Drone Scheduling Vehicle Routing Problem (PDSVRP). This problem is a variant of the well-known Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP) recently introduced in the literature in which we allow multiple trucks and consider the objective of minimizing the total transportation costs. We formulate the problem as a Mixed Integer Linear Program and then develop a Ruin and Recreate () algorithm. Exploiting PDSVRP solution characteristics in an effective manner, our heuristic manages to introduce “sufficient” rooms to a solution via new removal operators during the ruin phase. It is expected to enhance the possibilities for improving solutions later in the recreate phase. Multiple experiments on a new set of randomly generated instances confirm the performance of our approach. To explore the benefits of drone delivery as well as the insight into the impact of related factors on the contribution of drones’ use to operational cost, a sensitivity analysis is conducted. We also adapt the proposed algorithm to solve the PDSTSP and validate it via benchmarks available in the literature. It is shown that our algorithm outperforms state-of-the-art algorithms in terms of solution quality. Out of 90 considered instances, it finds 26 new best known solutions.
format Bài trích
author Minh Anh Nguyen
Giang Thi-Huong Dang
Minh Hoàng Hà
Minh-Trien Pham
author_facet Minh Anh Nguyen
Giang Thi-Huong Dang
Minh Hoàng Hà
Minh-Trien Pham
author_sort Minh Anh Nguyen
title The min-cost parallel drone scheduling vehicle routing problem
title_short The min-cost parallel drone scheduling vehicle routing problem
title_full The min-cost parallel drone scheduling vehicle routing problem
title_fullStr The min-cost parallel drone scheduling vehicle routing problem
title_full_unstemmed The min-cost parallel drone scheduling vehicle routing problem
title_sort min-cost parallel drone scheduling vehicle routing problem
publisher European Journal of Operational Research
publishDate 2021
url https://www.sciencedirect.com/science/article/abs/pii/S0377221721006032?via%3Dihub
https://dlib.phenikaa-uni.edu.vn/handle/PNK/2862
https://doi.org/10.1016/j.ejor.2021.07.008
_version_ 1751856304070066176
score 8.8894005

Similar Items