Giải thuật tìm kiếm cục bộ giải bài toán người du lịch

##plugins.themes.academic_pro.article.main##

Author

  • Võ Khánh Trung*; Đặng Đại Thọ*

Từ khóa:

bài toán người du lịch
NP-khó
giải thuật meta-heuristic
tìm kiếm cục bộ
tối ưu hóa tổ hợp

Tóm tắt

Bài toán người du lịch là một bài toán NP-khó thuộc thể loại tối ưu rời rạc hay tổ hợp được nghiên cứu trong vận trù học hoặc lý thuyết khoa học máy tính. Bài toán được phát biểu như sau: cho trước một danh sách các thành phố và khoảng cách giữa chúng, tìm chu trình ngắn nhất thăm mỗi thành phố đúng một lần. Hiện nay chưa có giải thuật chính xác nào để giải bài quyết bài toán này trong trường hợp tổng quát. Vì vậy, các giải thuật gần đúng đặc biệt được quan tâm. Trong bài báo này, chúng tôi đề xuất một giải thuật meta-heuristic sử dụng ý tưởng tìm kiếm địa phương để giải bài toán người du lịch. Giải thuật đã được cài đặt, thử nghiệm trên bộ dữ liệu chuẩn lấy từ TSPLIB và thu được những kết quả khá tốt.

Tài liệu tham khảo

    [1] R. Bellman, "Combinatorial processes and dynamic programming", in: Combinatorial Analysis (R. Bellman and M. Hall, Jr., eds.), American Mathematical Society, pp. 217-249.
    [2] Woeginger, G.J. (2003), "Exact Algorithms for NP-Hard Problems: A Survey", Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer, pp. 185–207.
    [3] Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J. (2006), The Traveling Salesman Problem, ISBN 0-691-12993-2.
    [4] Avriel, Mordecai (2003), Nonlinear Programming: Analysis and Methods, Dover Publications, ISBN 0-486-43227-0.
    [5] P. Chundi and D. J. Rosenkrantz, Efficient Algorithms for Segmentation of Item-Set Time Series, Data Mining, An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal on Computing, 6, 3, Sept. 1977, 563-581.
    [6] Johnson, D.S. and McGeoch, L.A., “The traveling salesman problem: A case study in local optimization", Local search in combinatorial optimization, 1997, 215-310.
    [7] S. S. Ray, S. Bandyopadhyay and S. K. Pal, "Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering", Applied Intelligence, 2007, 26(3). pp. 183-195.
    [8] A. B. Kahng and S. Reda, "Match Twice and Stitch: A New TSP Tour Construction Heuristic", Operations Research Letters, 2004, 32(6). pp. 499–509.
    [9] AARTS, E.H.L., AND J.K. LENSTRA (eds.) [1997], Local Search in Combinatorial Optimization, Wiley.
    [10] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976.
    [11] Matthias Englert, Heiko Roglin, and Berthold Vocking. Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP, InProc. of the 18th Ann. ACM-SIAM Symp, On Discrete Algorithms (SODA), pages 1295–1304. SIAM, 2007.
    [12] Mohammad Ahmadvand, Majid Yousefikhoshbakht, Narges Mahmoodi Darani. Solving the Traveling Salesman Problem by an Efficient Hybrid Metaheuristic Algorithm, Article 7, Volume 3, Number 3, Summer 2012, Page 75-84, 2012.
Xem thêm

##plugins.themes.academic_pro.article.sidebar##

Đã Xuất bản

Dec 31, 2013
Download
PDF
Cách trích dẫn
Vo Khanh Trung*; Dang Dai Tho*. “Giải thuật tìm kiếm cục bộ giải bài toán người Du lịch”. Tạp Chí Khoa học Và Công nghệ - Đại học Đà Nẵng, vol 12, số p.h 73.2, Tháng Chạp 2013, tr 117-22, https://jst-ud.vn/jst-ud/article/view/2715.

##plugins.themes.academic_pro.article.details##