Cover Image

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!
id oai:localhost:PNK-2861
record_format dspace
spelling oai:localhost:PNK-28612022-08-17T05:54:48Z Ants can solve the parallel drone scheduling traveling salesman problem Quoc Trung Dinh Duc Dong Do Minh Hoàng Hà 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. 2021-09-14T07:14:55Z 2021-09-14T07:14:55Z 2021 Bài trích 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 eng GECCO
institution Digital Phenikaa
collection Digital Phenikaa
language eng
description 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.
format Bài trích
author Quoc Trung Dinh
Duc Dong Do
Minh Hoàng Hà
spellingShingle Quoc Trung Dinh
Duc Dong Do
Minh Hoàng Hà
Ants can solve the parallel drone scheduling traveling salesman problem
author_facet Quoc Trung Dinh
Duc Dong Do
Minh Hoàng Hà
author_sort Quoc Trung Dinh
title Ants can solve the parallel drone scheduling traveling salesman problem
title_short Ants can solve the parallel drone scheduling traveling salesman problem
title_full Ants can solve the parallel drone scheduling traveling salesman problem
title_fullStr Ants can solve the parallel drone scheduling traveling salesman problem
title_full_unstemmed Ants can solve the parallel drone scheduling traveling salesman problem
title_sort ants can solve the parallel drone scheduling traveling salesman problem
publisher GECCO
publishDate 2021
url 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
_version_ 1751856266658971648
score 8.887836

Similar Items