- 1.2.1 Bài toán tối ưu hóa tổ hợp. - 1.2.2 Bài toán tổng quát. - 2.1 Giới thiệu về bài toán điều phối xe. - 2.1.2 Các biến thể của bài toán điều phối xe. - 2.2 Tóm tắt nội dung bài toán. - 2.3 Mô hình hóa bài toán. - 2.4 Các cách tiếp cận bài toán. - 3.1 Bài toán điều phối xe (Vehicle Routing Problem -VRP. - 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. - 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ó.. - 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ó. - 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.. - Đ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. - 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. - Những ví dụ của metaheuristic bao gồm giải thuật luyện thép (SA), giải thuật di truyền (GA), giải thuật đàn kiến (ACO),…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. - Theo ý tưởng này, các thuật toán ACO sử dụng thông tin heuristic kết hợp với thông tin học tăng cường (xem [3]) qua các vệt mùi của các con kiến nhân tạo (artificial ant) để giải các bài toán tối ưu tổ hợp khó bằng cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng được xây dựng từ đặc điểm của từng bài cụ thể. - AS ban đầu được áp dụng cho bài toán người du lịch (TSP) và bài toán Phân bậc hai (QAP).. - Dorigo đã đề xuất hệ thống Ant- Q, là một cách tiếp cận học tăng cường cho cho bài toán TSP. - Đây là hệ thống đề cập đến cách học phối hợp áp dụng cho bài toán TSP.. - Bài toán tối ưu hóa tổ hợp liên quan tới việc tìm giá trị cho các biến số rời rạc như lời giải tối ưu mà có lưu ý tới hàm mục tiêu (objective function) cho trước.. - Bài toán có thể là bài toán tìm cực đại hoặc tìm cực tiểu. - Một cách thông thường, bài toán tối ưu hoá tổ hợp được cho dưới dạng bộ 3 (S, f, Ω). - Trong đó S là tập các lời giải ứng cử viên, f là hàm mục tiêu (hàm này gán giá trị f(s) cho mỗi lời giải ứng cử viên s S), và Ω là tập các ràng buộc của bài toán. - Mục tiêu bài toán là tìm ra một lời giải khả thi tối ưu toàn cục s. - Với các bài toán tối ưu hóa cực tiểu là tìm lời giải s * với giá nhỏ nhất, nghĩa là f(s. - Ngược lại bài toán tối ưu hóa cực đại là tìm lời giải s * với giá lớn nhất, nghĩa là f(s. - Bài toán tối ưu hóa tổ hợp có thể chia 2 loại: Bài toán tĩnh và bài toán động.. - Bài toán tối ƣu hóa tổ hợp tĩnh (Static Combinatorial optimization):. - Là bài toán tối ưu hóa tổ hợp trong đó cấu trúc (topology) và giá (cost) không thay đổi khi bài toán đang được giải quyết. - Ví dụ là bài toán người du lịch. - Khi thực hiện thuật toán để giải bài toán vị trí các thành phố, khoảng cách giữa các thành phố là không thay đổi.. - Bài toán tối ƣu hóa tổ hợp động (Dynamic Combinatorial optimization):. - Là bài toán tối ưu hóa tổ hợp trong đó cấu trúc (topology) và giá (cost) có thể thay đổi khi bài toán đang được giải quyết. - Xét bài toán cực tiểu hóa (S,f. - Một cách nhìn khác, nó là bài toán tìm kiếm vectơ độ dài không quá h trên đồ thị đầy đủ có các đỉnh có nhãn trong tập C.. - Hai bài toán người du lịch (TSP) và quy hoạch toàn phương nhị phân không ràng buộc (UPQB) được giới thiệu làm ví dụ cho các bài toán tối ưu tổ hợp.. - Thông thường ta sẽ có các phương pháp heuristic để tìm lời giải đủ tốt cho bài toán. - Procedure Thuật toán ACO cho bài toán tối ưu tổ hợp tĩnh Begin. - Phương pháp ACO metaheuristic chủ yếu được áp dụng cho các bài toán tối ưu tổ hợp, ví dụ như ứng dụng vào bài toán TSP đã trình bày ở phần trước.. - Một số bài toán tối ưu NP-khó như:. - Các bài toán lập lịch (job shop, flow shop, project scheduling). - Bài toán phân chia sản phẩm (The Generalized Assignment Problem_GAP). - Bài toán phủ tập hợp (The Set Covering problem-SCP. - Các bài toán trong học máy: bài toán phân lớp, mạng Bayes,…. - các thuật toán khá thành công cho các bài toán định tuyến trên các mạng truyền tin theo gói tin (packed switched) như mạng truyền thông internet chẳng hạn.. - Các chú ý sau đây làm tăng khả năng cho thuật toán ACO khi áp dụng các bài toán khác nhau. - Khi kết hợp các thuật toán ACO với phương pháp tìm kiếm địa phương sẽ tìm ra được những lời giải tốt hơn cho những bài toán khó xây dựng được những thông tin heuristic.. - Trong trường hợp bài toán động, thông tin heuristic cần phải được tính tại mỗi bước đi của con kiến bởi vì chúng phụ thuộc vào các lời giải thành phần được xây dựng. - Rất nhiều các ứng dụng của các bài toán tối ưu tổ hợp như TSP, bài toán phân chia sản phẩm, hay bài toán định tuyến cho xe cộ, các thuật toán ACO đều cho ra kết quả tốt khi kết hợp các thuật toán tìm kiếm địa phương. - Số lượng kiến trong các bài toán khác nhau cần được điều chỉnh khác nhau. - Số lượng kiến tùy thuộc vào kích thước cài đặt và phụ thuộc vào kích thước của bài toán cần giải quyết. - Với thuật toán MMAS áp dụng cho các bài toán nhỏ người ta chỉ dùng từ 2 đến 10 kiến. - Khi mà bài toán đi vào bế tắc. - Đối với các bài toán tĩnh danh sách này được tính toán ngay từ đầu.. - Khi áp dụng phương pháp ACO cho mỗi bài toán cụ thể có ba yếu tố quyết định hiệu quả thuật toán:. - 1) Xây dựng đồ thị có cấu trúc thích hợp: Việc xây dựng đồ thị có cấu trúc để tìm được lời giải cho bài toán theo thủ tục tuần tự không khó. - Khó khăn chính là với các bài toán cỡ lớn thì không gian tìm kiếm quá rộng, đòi hỏi ta sử dụng các ràng buộc một một cách hợp lý để giảm miền tìm kiếm cho mỗi con kiến.. - Tuy nhiên, nhiều bài toán ta không có thông tin này thì có thể đánh giá chúng như nhau. - Nếu đồ thị có cấu trúc và thông tin heuristic luôn phụ thuộc vào từng bài toán cụ thể thì quy tắc cập nhật mùi là yếu tố phổ dụng và thường dùng để đặt tên cho thuật toán. - Có nhiều quy tắc cập nhật mùi đã được đề xuất, trong luận văn này chúng tôi sẽ áp dụng hai quy tắc cập nhật mùi để thấy rõ ảnh hưởng của quy tắc cập nhật mùi tới việc giải quyết bài toán.. - BÀI TOÁN ĐIỀU PHỐI XE VÀ CÁC CÁCH GIẢI HIỆN NAY 2.1 Giới thiệu về bài toán điều phối xe. - Bài toán điều phối xe là sự kết hợp của bài toán tối ưu hóa tổ hợp và vấn đề nghiên cứu lập trình số nguyên để giải bài toán số lượng khách hàng với một đội xe. - Bài toán điều phối xe được nhiều nhà khoa học trên thế giới nghiên cứu như Bullnheimer và các cộng sự [11], Toth và Vigo [13], Bell và McMullen[12].. - 2.1.2 Các biến thể của bài toán điều phối xe Bài toán VRP tổng quát như sau:. - Trên thực tế nó khó hơn rất nhiều so với bài toán TSP bởi VRP chứa 2 vấn đề lồng nhau. - Bài toán VRP có rất nhiều biến thể khác nhau như bài toán Capacitated Vehicle Routing Problem(CVRP), VRP with Time Windows (VRPTW), VRP with Pickup và Delivery(VRPPD), và Dynamic VRP(DVRP). - Ở đây luận văn trình bày khái lược 3 bài toán VRP hay gặp:. - Ở bài toán này lượng hàng hóa ở mỗi thành phố là xác định và biết trước. - Mục tiêu của bài toán là tối thiểu hóa tổng chi phí cho các hành trình mà chi phí ở đây thường được dùng là khoảng cách của tất cả các thành phố.. - Đối với bài toán ‘VRP with Time Windows’ (VRPTW) điều kiện hạn chế công suất xe vẫn tồn tại và thêm ràng buộc đó là mỗi thành phố thứ i được gắn với một khoảng thời gian [a i ,b i ] gọi là cửa sổ thời gian với một khoảng thời gian s i. - Đối với bài toán ‘ Dynamic VRP’(DVRP): Đây là một mở rộng của bài toán VRP cơ bản , nó được ứng dụng rất nhiều trong thế giới thực. - Biến thể này gọi là bài toán VRP động (DVRP). - Yêu cầu bài toán:. - 2.3 Mô hình hóa bài toán:. - Hình 2.1 là ví dụ về bài toán điều phối xe với 4 xe và 13 thành phố C 1 ,C 2 ,…C 13 . - Với những bài toán có kích thước nhỏ (ít thành phố khoảng 10 đến 20 thành phố, và ít xe từ 2 đến 6 xe) ta có thể sử dụng các phương pháp tìm kiếm. - Nhưng với những bài toán có kích thước lớn hơn cần sử dụng các thuật toán sau:. - Trong mục này, luận văn trình bày tóm tắt thuật toán nhánh cận(xem[8]) được xem là cách tiếp cận tốt và cho được nghiệm tối ưu với trường hợp bài toán có kích thước trung bình.. - Xét bài toán tối ưu. - Để áp dụng thuật toán nhánh cận giải bài toán đặt ra, chúng ta cần xây dựng hai thủ tục chính sau đây:. - Trong chương 3, luận văn sẽ trình bày cách thức áp dụng tối ưu đàn kiến giải bài toán điều phối xe.. - Để giải một bài toán tối ưu tổ hợp bằng phương pháp tối ưu đàn kiến, đầu tiên ta phải đưa bài toán về dạng tìm kiếm đường đi tối ưu trên đồ thị. - Trong bài toán điều phối xe, đồ thị các chuyến xe được xây dựng dựa trên thứ tự các thành phố mà mỗi xe đi qua. - Chương này luận văn trình bày về cách áp dụng tối ưu đàn kiến giải bài toán điều phối xe.. - 3.1 Bài toán điều phối xe (Vehicle Routing Problem -VRP ) Mô tả lại bài toán điều phối xe (đã được giới thiệu ở chương II). - Bài báo nghiên cứu về việc Áp dụng phương pháp ACO cho bài toán điều phối xe.. - Đây là trang web chứa các bộ dữ liệu chuẩn của các bài toán tối ưu tổ hợp kinh điển. - Đối với bài toán VRP khuôn dạng file input như sau:. - Sau nhiều thử nghiệm chúng tôi đề xuất các tham số cụ thể sau cho bài toán:. - Từ đó thấy rằng quy tắc cập nhật mùi theo chiến lược kiến trọng lượng là phù hợp hơn với bài toán điều phối xe.. - đã giải quyết tốt bài toán. - Tìm hiểu về bài toán VRP và cài đặt thành công thuật toán ACO áp dụng cho bài toán VRP. - Tiến hành thử nghiệm thay thế, và so sánh hai quy tắc cập nhật mùi mới nhất hiện nay áp dụng cho bài toán VRP là quy tắc cập nhật mùi theo. - Sẽ nghiên cứu cải tiến để có thể giải quyết bài toán với số thành phố lớn hơn 200 và với thời gian ngày càng nhỏ.