Ấn phẩm:
The traveling salesman problem with multi-visit drone
Đang tải...
Xem mô tả
9
Xem & Tải
4
Nhan đề khác
Tóm tắt
This paper deals with the Traveling Salesman Problem with Multi-Visit Drone (TSPMVD) in which a truck works in collaboration with a drone that can serve up to q ≥ 1 customers consecutively during each sortie. We propose a Mixed Integer Linear Programming (MILP) formulation and a metaheuristic based on Iterated Local Search (ILS) to solve the problem. Benchmark instances collected from the literature of the special case with q = 1 are used to test the performance of our algorithms. The obtained results show that our MILP model can solve a number of instances to optimality. This is the fist time optimal solutions for these instances are reported. Our ILS performs better than other algorithms in terms of both solution quality and running time on several instance classes. The numerical results obtained by testing the methods on new randomly generated instances show again the effctiveness of the methods as well as the positive impact of using the multi-visit drone.
Mô tả
Journal of Computer Science and Cybernetics, Vol.37, No.4
Tác giả
Ha, Quang Minh
Vu, Duy Manh
Le, Xuan Thanh
Hoang, Minh Ha
Người hướng dẫn
Nơi xuất bản
Nhà xuất bản
Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Năm xuất bản
2021-10
ISSN tạp chí
Nhan đề tập
Từ khóa chủ đề
Traveling salesman problem , Multi-visit drone , Mixed Integer linear programming , Iterated local search
URI
Tài liệu tham khảo
Thông tin bản quyền
Tệp tin
Quang Minh Ha, Duy Manh Vu, Xuan Thanh Le, Minh Ha Hoang.pdf
Dung lượng: 913.02 KBĐịnh dạng: pdf
Lượt xem: 4 Lượt tải: 0