- Những đặc trưng cơ bản của bài toỏn VRP. - Những yếu tố khụng xỏc định trong bài toỏn VRP. - Cỏc dạng cơ bản bài toỏn VRP. - Bài toỏn VRP với hạn chế về trọng tải xe (CVRP. - Mụ hỡnh toỏn học cho bài toỏn VRP. - Cỏc phương phỏp heuristic và metaheuristic giải bài toỏn VRP. - Cỏc thuật toỏn heuristic cho bài toỏn VRP. - Một số thuật toỏn metaheuristic cho bài toỏn VRP. - Bài toỏn VRPTW và thuật toỏn Đa bầy kiến. - Giới thiệu thuật toỏn bầy kiến. - Dạng bài toỏn cho thuật toỏn Bầy kiến. - Cấu trỳc chung của họ thuật toỏn Bầy kiến. - Thuật toỏn Đa bầy kiến cho bài toỏn VRPTW. - Lộ trỡnh đường đi cho bài toỏn VRP. - 33 Hỡnh 2-1: Cấu trỳc chung của cỏc thuật toỏn bầy kiến. - 47 Hỡnh 2-3: Mụ hỡnh thuật toỏn Đa bầy kiến giải bài toỏn VRPTW. - 51 Hỡnh 2-4: Thuật toỏn MACS-VRPTW. - 52 Hỡnh 2-5: Thuật toỏn cho ACS-TIME. - 54 Hỡnh 2-6: Thuật toỏn cho ACS-TIME. - 56 Hỡnh 2-7: Phương ỏn cho bài toỏn VRPTW. - Tỡm hiểu thuật toỏn bầy kiến. - Phỏt triển thuật toỏn dựa trờn sơ đồ thuật toỏn bầy kiến để giải bài toỏn. - Xõy dựng được phõn mềm ứng dụng thuật toỏn đa bầy kiến cho bài toỏn VRP với hạn chế thời gian và thực nghiệm trờn cỏc bộ dữ liệu đề xuất (Solomon). - Cỏc khỏch hàng Khỏch hàng là trung tõm của bài toỏn VRP. - Một phương ỏn chấp nhận được của bất kỳ dạng nào bài toỏn đều phải phục vụ được tất cả cỏc khỏch hàng. - Trờn thực tế, sự biến đổi của thời gian vận chuyển này cú thể ảnh hưởng rất lớn đến kết quả của cỏc phương ỏn đó được xõy dựng cho bài toỏn. - Đầu tiờn mụ hỡnh lưu lượng xe vận tải được xõy dựng cho bài toỏn CVRP khụng đối xứng. - Mụ hỡnh trờn cú thể thay đổi để ỏp dụng cho bài toỏn đối xứng SCVRP. - Khi đú cú thể thờm nhiều ràng buộc tương ứng với cỏc bài toỏn thực tế. - Kỹ thuật này cũng được sử dụng trong thuật toỏn Đa bầy kiến giải bài toỏn VRPTW được trỡnh bày ở phần sau. - Bài toỏn trở thành: tỡm phương ỏn chi phớ thấp nhất mà thực hiện đỳng K lộ trỡnh. - Nếu λ = 0, ta cú bài toỏn tỡm phương ỏn chi phớ thấp nhất sử dụng nhiều nhất K lộ trỡnh. - Cỏc thuật toỏn heuristic cho bài toỏn VRP cú thể chia làm hai loại: xõy dựng lộ trỡnh (constructive heuristic) và cải tiến lộ trỡnh (improvement heuristic). - Thuật toỏn Clarke và Wright5F6 (hay cũn gọi là thuật toỏn dạng rỳt ngắn thời gian di chuyển) là một trong những thuật toỏn heuristic nổi tiếng nhất cho bài toỏn VRP. - Thuật toỏn này được ỏp dụng cho bài toỏn mà số lượng xe là chưa xỏc định trước và do thuật toỏn đưa ra. - Những thuật toỏn dạng cũn được gọi là tỡm kiếm cục bộ (local search) do chỳng chỉ tỡm kiếm trong giới hạn của một phương ỏn của bài toỏn. - Đối với bài toỏn VRP thuật toỏn cải tiến cú thể được thực hiện trờn một tuyến hay trờn hai tuyến khỏc nhau của lộ trỡnh. - Thuật toỏn Trao đổi chộo (CROSS exchange)là thuật toỏn của Taillard [6] và cỏc cộng sự. - Thuật toỏn này được phỏt biểu cho bài toỏn VRPTW và nú cũng được sử dụng như là một bước cải tiến phương ỏn trong thuật toỏn Đa bầy kiến cho bài toỏn VRPTW. - Thuật toỏn trao đổi chộo giữ nguyờn hướng của cỏc tuyến nờn thớch hợp cho giới hạn khung thời gian trong bài toỏn VRPTW. - Khỏc với cỏc thuật toỏn heuristic thường chỉ được phỏt triển cho từng bài toỏn. - Trong những năm gần đõy, nhiều thuật toỏn metaheuristic đó được ỏp dụng cho bài toỏn VRP. - Những thuật toỏn metaheuristic đó được ỏp dụng cho bài toỏn VRP là thuật toỏn mụ phỏng luyện thộp (Simulated Annealing - SA), tỡm kiếm Tabu (Tabu Search - TS), thuật toỏn di truyền (Genetic Algorithms - GA) và thuật toỏn Bầy kiến (Ant Colony Optimization). - Cũn thuật toỏn GA, tại mỗi bước thuật toỏn xem xột một tập cỏc phương ỏn. - Thuật toỏn bầy kiến là thuật toỏn dạng xõy dựng phương ỏn theo từng bước. - Trong mỗi vũng lặp mỗi tỏc tử của thuật toỏn (cỏc con kiến) tạo ra một phương ỏn mới. - Do đú thuật toỏn Bầy kiến tao ra rất nhiều phương ỏn tại mỗi vũng lặp. - Thuật toỏn mụ phỏng luyện thộp (SA): Trong thuật toỏn này, tại vũng lặp thứ t, một phương ỏn x được lấy một cỏch ngẫu nhiờn từ tập N(xt). - Thuật toỏn SA nổi tiếng nhất ỏp dụng cho bài toỏn VRP là thuật toỏn của Osman. - Trong khoảng 20 năm gần đõy, thuật toỏn tỡm kiếm tabu được ỏp dụng cho bài toỏn VRP. - Đặc điểm chung của thuật toỏn GA là. - Bài toỏn VRPTW và thuật toỏn Đa bầy kiến Cỏc đặc điểm của bài toỏn VRPTW Chỉ cú một kho chứa. - Với thuật toỏn để giải bài toỏn VRPTW, em lựa chọn thuật toỏn Đa bầy kiến (MACS-VRPTW). - Cỏc thuật toỏn ACO cú thể được sử dụng để giải quyết cả 2 loại bài toỏn tối ưu húa tĩnh và động. - Thuật toỏn Bầy kiến sử dụng một tập cỏc con kiến nhõn tạo để xõy dựng những phương ỏn khỏc nhau cho bài toỏn. - Do đú thuật toỏn Bầy kiến cú thể ỏp dụng cho mất cứ bài toỏn nào mà phương ỏn của nú cú thể tỡm được bằng một thủ tục xõy dựng dần từng bước (constructive heuristic). - Điều này cú nghĩa là thuật toỏn Bầy kiến cú thể ỏp dụng cho bất kỳ bài toỏn tối ưu húa tổ hợp nào. - Dưới đõylà cỏch biểu diễn thường gặp để mụ hỡnh húa cỏc bài toỏn tối ưu húa tổ hợp về dạng cú thể ỏp dụng thuật toỏn Bầy kiến. - Mục tiờu của bài toỏn là tỡm phương ỏn tối ưu toàn cục s*, hay phương ỏn chấp nhận được cú chi phớ nhỏ nhất. - Tập là tập tất cả cỏc trạng thỏi cú thể của bài toỏn. - Như đó núi ở trờn, trong thuật toỏn Bầy kiến, mỗi con kiến là một hàm xõy dựng cỏc phương ỏn dựa trờn xỏc suất. - o Những ràng buộc của bài toỏn. - Trang 45 Hỡnh 2-1: Cấu trỳc chung của cỏc thuật toỏn bầy kiến. - Hỡnh 2.1 ở trờn mụ tả cấu trỳc chung của thuật toỏn bầy kiến. - Ngày nay, thuật toỏn bầy kiến được ỏp dụng cho rất nhiều bài toỏn tối ưu húa tổ hợp khỏc nhau.. - Đõy cũng được xem như cơ sở cho nhiều thuật toỏn Đa bầy kiến cho bài toỏn VRPTW. - Trong thuật toỏn bầy kiến cho bài toỏn Người du lịch ta phải tỡm ra đường đi ngắn nhất. - Sau đú, thuật toỏn sẽ cập nhật dấu vết đặc trưng trờn cỏc cạnh dựa trờn phương ỏn tốt nhất hiện biết. - Ở trong thuật toỏn này, chỉ cú phương ỏn tốt nhất hiện biết được sử dụng để thay đổi dấu vết đặc trưng. - Trong đú cỏc thuật toỏn trước đõy sử dụng tất cả cỏc phương ỏn đó được xõy dựng bởi cỏc con kiến để cập nhật dấu vết đặc trưng. - Cú rất nhiều giỏ trị τ0 được sử dụng trong cỏc thuật toỏn khỏc nhau. - Trong thuật toỏn Bầy kiến cho bài toỏn Người du lịch sử dụng giỏ trị khởi tạo trong đú là chiều dài (tổng chi phớ) của phương ỏn khởi tạo. - Nội dung của phần tiếp theo trỡnh bày về thuật toỏn Đa bầy kiến cho bài toỏn VRPTW. - Hai bầy kiến này sẽ hoạt động song song nhằm xõy dựng phương ỏn thỏa món nhiều mục tiờu trong bài toỏn VRPTW. - Do đú, điều quan trọng của thuật toỏn là kết hợp hoạt động của cỏc bầy kiến để phục vụ cho việc giải quyết bài toỏn. - Trang 52 Hỡnh 2-4: Thuật toỏn MACS-VRPTW. - MACS-VRPTW: Thuật toỏn đa bầy kiến giải bài toỏn lộ trỡnh giao nhận hàng húa với hạn chế thời điểm phục vụ. - Chương trỡnh này tương tự chương trỡnh sử dụng trong thuật toỏn Bầy kiến được thiết kế cho bài toỏn Người du lịch. - Trang 54 Hỡnh 2-5: Thuật toỏn cho ACS-TIME. - xõy dựng phương ỏn ψk. - Trang 56 Hỡnh 2-6: Thuật toỏn cho ACS-TIME Phần tiếp theo trỡnh bày về cỏch xõy dựng từng phương ỏn cho bài toỏn VRPTW. - Chương trỡnh này tương tự như chương trỡnh xõy dựng phương ỏn được sử dụng trong thuật toỏn Bầy kiến thiết kế cho bài toỏn Người du lịch. - Xỏc định yờu cầu Nhiệm vụ của đề tài là nghiờn cứu thuật toỏn Bầy kiến và xõy dựng chương trỡnh mụ phỏng thuật toỏn để giải bài toỏn VRPTW. - Thiết kế chức năng chương trỡnh Chương trỡnh mụ phỏng thuật toỏn Đa bầy kiến giải bài toỏn VRPTW. - Đầu ra: Cỏc biến đặc trưng của bài toỏn. - Chương trỡnh mụ phỏng thuật toỏn đa bầy kiến cho bài toỏn VRPTW. - Improvement: Cài đặt cỏc thuật toỏn nhằm cải thiện phương ỏn vừa tỡm được. - cập nhật lại trạng thỏi của bài toỏn m_pathVect.add(newNode). - Phương thức localsearch: cài đặt thuật toỏn trao đổi chộo (xem phần 1.4.1.Cỏc thuật toỏn heuristic cho bài toỏn VRP) 3.2.6. - Đõy là một thuật toỏn heuristic cho một phương ỏn khỏ tốt của bài toỏn VRPTW. - Bài toỏn chỉ khỏc nhau về độ rộng của cỏc khung thời gian. - Thụng thường η được đưa vào để hướng cỏc con kiến tỡm những phương ỏn thỏa món mục tiờu của bài toỏn. - Lựa chọn điều kiện dừng Thuật toỏn Bầy kiến sử dụng nhiều con kiến khỏc nhau cựng đồng thời xõy dựng cỏc phương ỏn dựa trờn xỏc suất. - Thuật toỏn bầy kiến là thuật toỏn liờn tục tỡm kiếm cỏc phương ỏn cho kết quả tốt hơn. - So sỏnh với kết quả cài đặt cựng thuật toỏn của tỏc giả. - Hai thuật toỏn này được xem là một trong những thuật toỏn tốt nhất cho bài toỏn VRPTW. - Thuật toỏn này đó giới thiệu một mụ hỡnh mới cho cỏc bài toỏn tối ưu húa cú nhiều hàm mục tiờu. - Đõy là thuật toỏn đầu tiờn sử dụng nhiều bầy kiến vào việc giải quyờt bài toỏn tối ưu húa tổ hợp đa hàm mục tiờu. - Từ đú, phỏt triển thuật toỏn đa bầy kiến để giải bài toỏn VRPTW. - Chương 1: Bài toỏn lộ trỡnh vận tải Chương 2: Thuật toỏn bầy kiến Chương 3: Thực nghiệm tớnh toỏn và đỏnh giỏ Chương 4: Kết luận 5
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt