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...
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Định dạng: | Bài trích |
| Ngôn ngữ: | eng |
| Nhà xuất bản: |
GECCO
2021
|
| Truy cập trực tuyến: | 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 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| 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 |