Ants can solve the parallel drone scheduling traveling salesman problem

In this work, we are interested in studying the parallel drone scheduling traveling salesman problem (PDSTSP), where deliveries are split between a truck and a fleet of drones. The truck performs a common delivery tour, while the drones are forced to perform back and forth trips between customers an...

Full description

Saved in:
Bibliographic Details
Main Authors: Quoc Trung Dinh, Duc Dong Do, Minh Hoàng Hà
Format: Bài trích
Language:eng
Published: GECCO 2021
Online Access:https://dl.acm.org/doi/10.1145/3449639.3459342
https://dlib.phenikaa-uni.edu.vn/handle/PNK/2861
https://doi.org/10.1145/3449639.3459342
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work, we are interested in studying the parallel drone scheduling traveling salesman problem (PDSTSP), where deliveries are split between a truck and a fleet of drones. The truck performs a common delivery tour, while the drones are forced to perform back and forth trips between customers and a depot. The objective is to minimize the completion time coming back to the depot of all the vehicles. We present a hybrid ant colony optimization (HACO) metaheuristic to solve the problem. Our algorithm is based on an idea from the literature that represents a PDSTSP solution as a permutation of all customers. And then a dynamic programming is used to decompose the customer sequence into a tour for the truck and trips for the drones. We propose a new dynamic programming combined with other problem-tailored components to efficiently solve the problem. When being tested on benchmark instances from the literature, the HACO algorithm outperforms state-of-the-art algorithms in terms of both running time and solution quality. More remarkably, we find 23 new best known solutions out of 90 instances considered.