Thông tin tài liệu
Nhan đề : | Ants can solve the parallel drone scheduling traveling salesman problem |
Tác giả : | Quoc Trung Dinh Duc Dong Do Minh Hoàng Hà |
Năm xuất bản : | 2021 |
Nhà xuất bản : | GECCO |
Tóm tắt : | 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. |
URI: | https://dl.acm.org/doi/10.1145/3449639.3459342 https://dlib.phenikaa-uni.edu.vn/handle/PNK/2861 |
Bộ sưu tập | Bài báo khoa học |
XEM MÔ TẢ
57
XEM TOÀN VĂN
0
Danh sách tệp tin đính kèm:
Hiện tại không có tệp tin đính kèm tới tài liệu.