Optimization of Truck-Drone Parcel Delivery Using Metaheuristics

This research addresses a variant of the traveling salesman problem in drone-based delivery systems known as the TSP-D. The TSP-D is a combinatorial optimization problem in which a truck and a drone collaborate to deliver parcels to customers, with the objective of minimizing the total delivery time...

Full description

Saved in:
Bibliographic Details
Published in:Applied sciences 2021-07, Vol.11 (14), p.6443
Main Authors: AlMuhaideb, Sarab, Alhussan, Taghreed, Alamri, Sara, Altwaijry, Yara, Aljarbou, Lujain, Alrayes, Haifa
Format: Article
Language:English
Subjects:
Adaptive algorithms
Algorithms
Combinatorial analysis
Cost control
COVID-19
Customers
drone
Drone vehicles
Drones
GRASP
Heuristic
metaheuristics
Optimization
routing
Statistical analysis
Statistical tests
Traveling salesman problem
TSP-D
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This research addresses a variant of the traveling salesman problem in drone-based delivery systems known as the TSP-D. The TSP-D is a combinatorial optimization problem in which a truck and a drone collaborate to deliver parcels to customers, with the objective of minimizing the total delivery time. Determining the optimal solution is NP-hard; thus, the size of the problems that can be solved optimally is limited. Therefore, metaheuristics are used to solve the problem. Metaheuristics are adaptive and intelligent algorithms that have proved their success in many similar problems. In this study, a solution to the TSP-D problem using the greedy, randomized adaptive search procedure with two local search alternatives and a self-adaptive neighborhood selection scheme is presented. The proposed approach was tested on 200 instances with different properties from the publicly available “Instances of TSP with Drone” benchmark. Results were evaluated against state-of-the-art algorithms. Non-parametric statistical tests concluded that the proposed approach has comparable performance to the rival algorithms (p=0.074) in terms of tour duration. The proposed approach has better or similar performance in instances where the drone and truck have the same speed (α=1).
ISSN:2076-3417
2076-3417
DOI:10.3390/app11146443