- Thân Thị Lệ Quyên PHÁT TRIỂN THUẬT TOÁN GIẢI BÀI TOÁN TỐI ƯU HOÁ TRONG ĐIỀU HÀNH VẬN TẢI CHỞ HÀNH KHÁCH VÀ HÀNG HOÁ CHIA SẺ LỘ TRÌNH Chuyên ngành: Công nghệ thông tin LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC TS. - Phạm Quang Dũng Hà Nội – Năm 2017 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác giả luận văn: Thân Thị Lệ Quyên Đề tài luận văn: Phát triển thuật toán giải bài toán tối ưu hoá trong điều hành vận tải chở hành khách và hàng hoá chia sẻ lộ trình Chuyên ngành: Công nghệ thông tin Mã số SV: CB150297 Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày với các nội dung sau: A. - Bổ sung thêm tính toán độ phức tạp của thuật toán 2. - Bổ sung thêm ưu điểm, nhược điểm của thuật toán Giáo viên hướng dẫn Hà Nội, ngày 10 tháng 11 năm 2017 Tác giả luận văn CHỦ TỊCH HỘI ĐỒNG Trang 1 LỜI MỞ ĐẦU Trong thực tế hiện nay có nhiều loại mô hình vận tải. - Trong luận văn này, chúng tôi khảo sát bài toán lập lộ trình vận tải kết hợp giữa chở người và hàng hóa. - Sau đó chúng tôi đề xuất và cài đặt thử nghiệm 7 thuật toán tham lam xây dựng lời giải. - Các thuật toán này được cài đặt, thử nghiệm và đánh giá trên các bộ dữ liệu trích xuất từ bộ dữ liệu vận hành của Taxi San Francisco. - Luận văn được chia thành 3 chương không kể phần mở đầu và kết luận: Chương 1 trình bày cơ sở lý thuyết về bài toán tối ưu tổ hợp, bài toán tối ưu lộ trình vận tải, các hướng tiếp cận và thư viện. - Chương 2 trình bày về 7 thuật toán tham lam và chiến lược của từng thuật toán. - 8 1.1 Bài toán tối ưu tổ hợp. - 8 1.2 Các hướng tiếp cận giải bài toán tối ưu tổ hợp. - 10 1.3 Các bài toán tối ưu điều hành vận tải. - 13 1.5 Bài toán điều hành vận tải chở người và hàng hoá chia sẻ tuyến đường. - CÀI ĐẶT THUẬT TOÁN GIẢI BÀI TOÁN ĐIỀU HÀNH VẬN TẢI CHỞ NGƯỜI VÀ HÀNG HOÁ. - 32 2.1 Chiến lược tham lam 1 (Greedy1. - 32 2.2 Chiến lược tham lam 2 (Greedy2. - 33 2.3 Chiến lược tham lam 3 (Greedy3. - 35 2.4 Chiến lược tham lam 4 (Greedy4. - 36 2.5 Chiến lược tham lam 5 (Greedy5. - 37 2.6 Chiến lược tham lam 6 (Greedy6. - 38 2.7 Chiến lược tham lam 7 (Greedy7. - Em xin chân thành cảm ơn! Trang 5 DANH MỤC CÁC CHỮ VIẾT TẮT Chữ viết tắt Tên đầy đủ Ý nghĩa VRP Vehicle Routing Problem Bài toán vận tải CVRP Capacitated Vehicle Routing Problem Bài toán vận tải có ràng buộc sức chứa VRPTW Vehicle Routing Problem with Time Window Bài toán vận tải có ràng buộc về khung thời gian CBLS Constraint Based Local Search Tìm kiếm cục bộ dựa trên ràng buộc CBLSVR Constraint Based Local Search Vehicle Routing Tìm kiếm cục bộ dựa trên ràng buộc các bài toán vận tải VNS Variable Neighborhood Search Tìm kiếm trên các tập láng giềng khác nhau. - ILP Integer Linear Program Quy hoạch nguyên tuyến tính VRPPD VRP Pickup and Delivery Bài toán vận chuyển hàng Trang 6 DANH MỤC CÁC BẢNG Bảng 1.1: Nhóm hàm khởi tạo lời giải. - 21 Bảng 1.2: Nhóm hàm truy vấn về trạng thái của lời giải. - 47 Bảng 3.6: Kết quả thuật toán tham lam thứ 5 với trường hợp ngẫu nhiên. - 48 Bảng 3.7: So sánh thuật toán greedy2 với bộ dữ liệu n2000r100_1. - 14 Hình 1.2: Minh họa thuật toán performTwoOptMove1(2,6. - 14 Hình 1.3: Minh họa thuật toán performTwoOptMove1(2,6. - 14 Hình 1.4: Minh họa thuật toán performTwoOptMove3(2,6. - 15 Hình 1.5: Minh họa thuật toán performTwoOptMove4(2,6. - 16 Hình 1.7: Minh họa thuật toán performTwoOptMove5(2,6. - 16 Hình 1.8: Minh họa thuật toán performTwoOptMove6(2,6. - 16 Hình 1.9: Minh họa thuật toán performTwoOptMove7(2,6. - 17 Hình 1.10: Minh họa thuật toán performTwoOptMove8(2,6. - 18 Hình 1.12: Minh họa thuật toán performOrOptMove1(2,4,6. - 18 Hình 1.13: Minh họa thuật toán performOrOptMove2(2,4,6. - 19 Hình 1.15: Minh họa thuật toán performThreeOptMove1(2,4,6. - 20 Hình 1.18: Minh họa lộ trình vận tải cho 3 xe. - 27 DANH MỤC CÁC GIẢ MÃ Giả mã 2.1: Thuật toán tham lam thứ 1. - 33 Giả mã 2.2: Thuật toán tham lam thứ 2. - 34 Giả mã 2.3: Thuật toán tham lam thứ 3. - 35 Giả mã 2.4: Thuật toán tham lam thứ 4. - 36 Giả mã 2.5: Thuật toán tham lam thứ 5. - 37 Giả mã 2.6: Thuật toán tham lam thứ 6. - 38 Giả mã 2.7: Thuật toán tham lam thứ 7. - CƠ SỞ LÝ THUYẾT 1.1 Bài toán tối ưu tổ hợp Bài toán tối ưu tổ hợp là bài toán không quan tâm đến việc xây dựng tất cả các cấu hình như bài toán liệt kê mà chỉ nhằm xây dựng một cấu hình “tốt” nhất theo một mục tiêu nào đó. - Bài toán thường xuất hiện rất nhiều trong các lĩnh vực của đời sống xã hội đặc biệt là các hoạt động quản lý, lập kế hoạch, điều hành trong các tổ chức, doanh nghiệp. - Như bài toán lập tuyến tối ưu trong lĩnh vực giao thông vận tải bài toán đóng gói hàng hóa [26], bài toán xếp hàng trong các dây chuyền sản xuất [8], bài toán xếp thời khóa biểu trong quản lý đào tạo [25]… Mục tiêu của các bài toán này là cần tìm ra một lời giải thỏa mãn một tập các ràng buộc đặt ra, đồng thời tối ưu một hoặc nhiều hàm mục tiêu nào đó. - Một bài toán tối ưu tổ hợp [31] là một bộ (X,D,C,f) trong đó: X ={X1,…,Xn} là tập các biến, D ={D1,…,Dn} trong đó Di là một tập rời rạc thể hiện miền giá trị của Xi. - C ={C1,…,Ck} là tập các ràng buộc được định nghĩa trên các biến, f là hàm mục tiêu cần tối ưu. - Trong nhiều bài toán, yêu cầu đặt ra là tìm lời giải thỏa mãn ràng buộc, vì vậy hàm mục tiêu f không được quan tâm. - Bài toán tối ưu tổ hợp có nhiều ứng dụng trong thực tế, đã và đang thu hút được đầu tư nghiên cứu nhằm giải quyết các vấn đề trong điều hành, sản xuất để tăng sản lượng lao động, tiết kiệm chi phí nguyên liệu và thời gian. - Ví dụ về bài toán N-Queen yêu cầu xếp n con hậu lên một bàn cờ vua kích thước nxn sao cho không có hai con hậu bất kì nào khống chế nhau. - Bài toán N-Queen thuộc vào lớp bài toán tối ưu tổ hợp, có thể được mô tả bằng mô hình toán học: Tập n biến quyết định X = {X1,X2,…,Xn}: Biến Xi biểu thị hàng cho con hậu đứng ở cột i. - Quá trình giải bài toán theo hướng tìm kiếm cục bộ dựa trên ràng buộc gồm hai bước chính dựa theo kiến trúc CBLS [28]: Mô hình hóa bài toán Định nghĩa các biến quyết định. - Xây dựng ràng buộc và hàm mục tiêu. - Tìm kiếm Khởi tạo lời giải ban đầu. - Thực hiện lặp: Di chuyển qua các lời giải lân cận. - Phân tích bài toán N-Queen với n = 8 theo mô hình CBLS. - Quá trình mô hình hóa bài toán dựa theo mô hình toán học đã trình bày ở trên: Tập biến: Mảng x[i], trong đó x[i] là hàng của con hậu trên cột i. - Tập ràng buộc: Xi ≠ Xj với i ≠ j Xi+i ≠ Xj+j với i ≠ j Xi-i ≠ Xj-j với i ≠ j Một lời giải là một cách gán giá trị {X1 = x1, X2 = x2. - Tập lời giải lân cận của một lời giải S = {x1,x2,…x7} gồm mọi lời giải S. - Lời giải được khởi tạo ngẫu nhiên. - Lời giải tiếp theo được lựa chọn ra trong các lời giải lân cận hiện tại theo cách tham lam: Chọn con hậu ở cột i đang bị khống chế nhiều nhất. - 1.2 Các hướng tiếp cận giải bài toán tối ưu tổ hợp Các hướng tiếp cận để giải bài toán tối ưu tổ hợp được chia thành 2 loại: hướng tiếp cận giải đúng và hướng tiếp cận giải gần đúng. - Hướng tiếp cận giải đúng đảm bảo luôn cho lời giải tối ưu, tuy nhiên với các bộ dữ liệu lớn thì thời gian tính là rất lớn. - Hướng tiếp cận giải gần đúng trong đó có tìm kiếm cục bộ để giải các bài toán tối ưu tổ hợp kích thước lớn đang được quan tâm nghiên cứu phát triển vì nó có khả năng tìm ra lời giải chất lượng tốt trong nhiều bài toán kích thước lớn với thời gian hữu hạn cho phép. - 1.2.1 Hướng tiếp cận giải đúng Hướng tiếp cận giải đúng bao gồm các kỹ thuật cho phép tìm ra lời giải tối ưu hoặc chỉ ra lời giải thỏa mãn ràng buộc không tồn tại vì nó duyệt hết các khả năng trong không gian lời giải. - Phương pháp này bao gồm các thuật toán điển hình như thuật toán nhánh cận hoặc quy hoạnh động, quy hoạch ràng buộc, hay quy hoạch nguyên tuyến tính (ILP). - 1.2.2 Hướng tiếp cận giải gần đúng Tìm kiếm cục bộ (Local Search) là phương pháp tìm lời giải tốt hơn từ những lời giải là láng giềng của lời giải hiện tại bằng cách áp dụng các phép biến đổi cục bộ để sinh ra lời giải láng giềng từ lời giải hiện tại. - Để tránh vấn đề tối ưu cục bộ của Local search có thể áp dụng các phương pháp Meta-Heuristic được trình bày sau đây. - Tìm kiếm Tabu (Tabu search Là thuật toán sử dụng một danh sách chứa các thao tác di chuyển đã thực hiện trước đó, thao tác di chuyển sẽ không được thực hiện nếu đã tồn tại trong danh sách. - Sử dụng phương pháp này để tránh quay trở lại các lời giải trước đó. - Ý tưởng ban đầu là khởi tạo một quần thể các lời giải. - Cho đến nay, đã có rất nhiều phương thức được đề xuất Trang 11 cho quá trình ghép gặp và đột biến áp dụng cho bài toán tối ưu, trong đó có đề xuất khác thành công như . - Thuật toán Variable neighborhood Search chia tập láng giềng thành các tập láng giềng nhỏ hơn với độ ưu tiên khác nhau. - Nếu tìm thấy láng giềng tốt hơn lời giải hiện tại thì các tập láng giềng còn lại sẽ không được duyệt, nhờ vậy tại mỗi vòng lặp, lời giải được cải thiện với chi phí thấp và trong tình huống gặp tối ưu cục bộ, tất cả các tập láng giềng sẽ được duyệt để tìm lời giải tốt hơn do đó khả năng tìm được lời giải tối ưu sẽ cao hơn. - Hansen đã nguyên cứu tỉ mỉ thuật toán Variable Neighborhood Search (VNS) cơ bản và các kỹ thuật cải tiến, rồi sử dụng chúng để giải nhiều bài toán cổ điển trong [19]. - 1.3 Các bài toán tối ưu điều hành vận tải Bài toán tối ưu điều hành vận tải là bài toán trong đó cần xây dựng lộ trình cho một đội xe phục vụ các yêu cầu vận chuyển người và hàng hóa. - Có nhiều biến thể của bài toán phụ thuộc vào ràng buộc và hàm mục tiêu trong tùy từng ngữ cảnh cụ thể. - Vào năm 1959 Dantzig [6] và cộng sự đã đề xuất mô hình hóa của bài toán vận tải dưới dạng bài toán tối ưu. - Ngày nay, bài toán này được gọi chung là “Vehicle Routing Problem” (VRP) [17] [22]. - Mục tiêu của bài toán CVRP là tổng chiều dài tuyến đường là ngắn nhất. - Có rất nhiều nhà khoa học đã phát triển các thuật toán heuristics [11] [24] và thuật toán chính xác [3] [10]. - Bài toán MMCVRP (Min-Max Capacitated Vehicle Routing Problem) với mục tiêu tối thiểu hóa hành trình dài nhất. - Thuật toán này đầu tiên được đề xuất bởi Golden và đồng sự [2]. - Gần đây, thuật toán tìm kiếm cục bộ đang được đề xuất và cài đặt thử nghiệm [9] để giải bài toán MMCVRP. - Trang 12 Bài toán VRPTW thực chất là bài toán CVRP có bổ sung thêm ràng buộc về khung thời gian. - VRPTW Là bài toán điều hành xe sao cho với mỗi yêu cầu của khách hàng điều tồn tại 2 tham số e, l. - Một số thuật toán thường được sử dụng để giải quyết vấn đề này là tìm kiếm Tabu, giải thuật di truyền, thuật toán tiến hóa, tối ưu hóa quần thể [21]. - Bài toán này thường được áp dụng cho các dịch vụ vận chuyển hàng hóa. - Có nhiều công trình nghiên cứu về vấn đề này, thuật toán tìm kiếm cục bộ Heuristics đã được đề xuất trong [12], để tối ưu hóa tuyến đường dự kiến của xe. - Đến năm 2014, một mô hình vận tải mới kết hợp vận chuyển người và hàng hoá được đề xuất đầu tiên bởi Li và đồng nghiệp [23]. - Bài toán này sẽ được trình bày cụ thể phần 1.5.3. - Mô hình tối ưu cho bài toán này được đề xuất bởi Murray và Chu vào năm 2015 [27]. - Điều đó cho thấy, bài toán tối ưu điều hành vận tải được quan tâm trong nhiều thập kỷ qua và số lượng giải pháp đã tăng lên nhanh chóng. - Trang 13 1.4 Thư viện CBLSVR 1.4.1 Tổng quan Constraint Based Local Search Vehicle Routing (CBLSVR) [9] là thư viện CBLS cho các bài toán VRP, thư viện này cung cấp sẵn các bất biến, hàm, ràng buộc hay gặp trong các bài toán VRP có thể sử dụng thư viện giải quyết các bài toán VRP bằng cách lên mô hình hóa bài toán. - 1.4.2 Láng giềng Thuật toán local Search là thuật toán được tạo ra từ các lời giải láng giềng dựa trên các thao tác di chuyển (move). - Đổi chiều tuyến đường Hình 1.2: Minh họa thuật toán performTwoOptMove1(2,6) Kết quả route[1. - Đổi chiều tuyến đường Hình 1.3: Minh họa thuật toán performTwoOptMove E1 S1 5 6 7 E2 S2 5 6 7 E2 E1 1 2 3 4 S2 S1 5 6 7 E2 S1 1 2 3 4 S2 E1
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt