Phương pháp tối ưu đàn kiến cho bài toán điều phối xe

- Phương pháp tối ưu đàn kiến cho bài toán điều phối xe.
- 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;.
- 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.
- 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..
- Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc giải quyết các bài toán tổ hợp khó.
- Một cài đặt thành công của metaheuristic trong một bài toán tổ hợp phải cân bằng giữa sự khai thác được kinh nghiệm thu thập được trong quá trình tìm kiếm để xác định được những vùng với những lời giải có chất lượng cao gần tối ưu.
- Giải thuật đàn kiến là metaheuristic dùng chiến lược của kiến trong thế giới thực để giải bài toán tối ưu..
- Trong số các giải thuật heuristic, giải thuật tối ưu hóa đàn kiến ACO được công bố bởi nhà khoa học người Italia Dorigo năm 1996.
- Nó giống như việc mô phỏng lại hành vi tìm kiếm thức ăn của đàn kiến trong tự nhiên.
- Nó đã được áp dụng thành công như một giải pháp cho một số vấn đề tối ưu hóa kép cổ điển, ví dụ bài toán người du lịch, các bài toán lập lịch sản xuất, hay bài toán truyền thông.
- Thuật toán ACO rất giống với hành vi tìm kiếm thức ăn của đàn kiến trong tự nhiên.
- Điều này làm việc mã hóa thuật toán tối ưu đàn kiến cho bài toán điều phối xe là rất đơn giản..
- Đã có rất nhiều nghiên cứu áp dụng thuật toán ACO cho bài toán VRP bao gồm các nghiên cứu của Bullnheimer và các cô ̣ng sự [11.
- Với những ý nghĩa thiết thực đó trong luận văn này chu ́ ng tôi đã tiến hành nghiên cứu, trình bày lại những lý thuyết chung nhất của phương pháp ACO, cách áp dụng phương pháp ACO cho bài toán VRP.
- Ngoài ra trong luận văn chúng tôi còn ti ến hành cài đặt thử nghiệm các phương pháp cập nhật mùi mới..
- Chương 1: Phương pháp Tối ưu hóa đàn kiến và ứng dụng.
- Giới thiệu phương pháp tối ưu hóa đàn kiến: lịch sử phát triển, các thuật toán ACO, và một số 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.
- [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.