Phương pháp tối ưu đàn kiến cho bài toán điều
phối xe
Lê Mỹ Hạnh
Trường Đại học Công nghệ
Luận văn ThS Chuyên ngành: Kỹ thuật phần mềm; Mã số 60 48 01 03
Người hướng dẫn: TS. Đỗ Đức Đồng
Năm bảo vệ: 2014

Keywords. Phương pháp tối ưu đàn kiến; Bài toán điều phối xe; Tối ưu hóa tổ hợp;
Phần mềm.

Content
MỞ ĐẦU

Bài toán điều phối xe (Vehicle Routing Problem_VRP) đã được nghiên cứu trong suốt 40
năm qua. Mục đích điển hình của bài toán điều phối xe là thiết lập hành trình cho một số
phương tiện từ kho tới các thành phố và quay trở lại kho ban đầu mà không vượt quá năng lực
hạn chế của mỗi xe với một chi phí tối thiểu. Sự kết hợp các khách hàng không bị giới hạn
đến việc lựa chọn các hành trình. Bài toán điều phối xe được coi là một vấn đề tối ưu hóa tổ
hợp mà số lượng các giải pháp khả thi cho bài toán tăng theo cấp số nhân với số lượng khách
hàng ngày càng tăng.
Mục đích của bài toán tối ưu tổ hợp là tìm lời giải tốt nhất trong các lời giải có thể và
không gian tìm kiếm lời giải của bài toán là rời rạc. Nhiều bài toán tối ưu tổ hợp có độ phức
tạp tính toán cao và được phân loại thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài
toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn
thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng
xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ ) trong giới hạn thời
gian cho phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được
nghiên cứu sâu trong lĩnh vực tối ưu tổ hợp.
Các giải thuật Heuristic như thuật toán luyện kim (SA) để giải quyết bài toán điều phối xe.


nguyên tắc ứng dụng ACO.
Chương 2: Giới thiệu về bài toán điều phối xe, các vấn đề liên quan và các phương pháp
chính giải quyết bài toán.


Chương 3: Tối ưu đàn kiến và bài toán điều phối xe: Trình bày cách thức chung để áp dụng
tối ưu đàn kiến để giải các bài toán điều phối xe. Trình bày các kết quả thực nghiệm.

Reference
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Đỗ Đức Đông (2012), Phương pháp tối ưu đàn kiến và ứng dụng, Luận án tiến sĩ công
nghệ thông tin ĐHCN-ĐHQGHN.
Tiếng Anh
[2] M.Dorigo, V.Mainezzo and A.Corloni. Positive feedback as a search strategy,
Technical Report 91-109, Departimento di electronica e infomatica, Poletico di Milano,
IT, 1991.
[3] M.Dorigo. Optimization, learning and natural algorithms, PhD.dissertation, Milan
Polytechnique, Italy, 1992.
[4] M.Dorigo, V.Maniezzo and A.Corloni. The Ant System: Optimization by a colony of
cooperating agents, IEEE, Trans.Syst., Man, Cybern.B, vol.26, no.2, 1996, pp 29-41.
[5] M.Dorigo and L.M.Caro. The Ant Conoly Optimization metaheuristic, A New Idea in
Optimization, D.Corne, M.Dorigo and F.Glover, Eds.London, U.K, McGraw-Hill, 1999,
pp.11-32.
[6] M.Dorigo and Thomas Stutzle. The Ant Colony Optimization Metaheuristic:
Algorithms, Applications and Advances, 2000.
[7] Hoang Xuan Huan. Convergence Analysis of ACO Algorithms and New Perpectives,
manuscript, 2003.
[8] J.F.Shapiro. Mathematical Programming: Structures and Algorithms.
Wiley-Interscience [John Wiley & Sons], New York, 1979.