LỜI MỞ ĐẦU. 1 LỜI CAM ĐOAN. 6 DANH MỤC CÁC CHỮ VIẾT TẮT. 7 DANH MỤC CÁC BẢNG.
8 DANH MỤC CÁC HÌNH VẼ. 9 DANH MỤC CÁC GIẢ MÃ.1 Bài toán tối ưu tổ hợp .2 Các hướng tiếp cận giải bài toán tối ưu tổ hợp .1 Hướng tiếp cận giải đúng .2 Hướng tiếp cận giải gần đúng .3 Các bài toán tối ưu điều hành vận tải .4 Thư viện CBLSVR .5 Bài toán điều hành vận tải tối thiểu hóa hành trình dài nhất .1 Phát biểu bài toán .2 Mô hình toán học. CÀI ĐẶT THUẬT TOÁN GIẢI BÀI TOÁN ĐIỀU HÀNH VẬN TẢI TỐI THIỂU HÓA HÀNH TRÌNH DÀI NHẤT .1 Thuật toán tham lam 1 (Greedy1) .2 Thuật toán tham lam 2 (Greedy2) .3 Thuật toán tham lam 3 (Greedy3) .4 Thuật toán tham lam 4 (Greedy4) .5 Thuật toán tham lam 5 (Greedy5) .6 Thuật toán tham lam 6 (Greedy6) .7 Thuật toán tham lam 7 (Greedy7) .8 Thuật toán tham lam 8 (Greedy8) .9 Thuật toán tham lam 9 (Greedy9) .10 Thuật toán tham lam 10 (Greedy10). KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ .2 Kết quả thử nghiệm và đánh giá .3 Tổng kết và nhận xét kết quả thử nghiệm.
58 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN. 61 TÀI LIỆU THAM KHẢO. 62 4 LỜI CAM ĐOAN Tôi xin cam đoan số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không sao chép từ bất kỳ đồ án, luận văn nào khác. Mọi thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc rõ ràng và được phép công bố.
Nếu không đúng như đã nêu trên tôi xin hoàn toàn chịu trách nhiệm về đề tài của mình. Hà Nội, Ngày 30 Tháng 9 Năm 2018 Học viên thực hiện Nguyễn Hải Đăng 5 LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành và sự tri ân sâu sắc đối với các thầy cô của trường Đại học Bách Khoa Hà Nội, đặc biệt là các thầy cô trong viện Công Nghệ Thông Tin và Truyền thông của trường đã tạo điều kiện cho em được học tập và nghiên cứu chuyên ngành công nghệ thông tin. Và em cũng xin chân thành cảm ơn thầy TS. Phạm Quang Dũng và các thành viên trong nhóm nghiên cứu đã nhiệt tình hướng dẫn, giúp đỡ em hoàn thành khóa luận tốt nghiệp.
Với điều kiện thời gian cũng như kinh nghiệm còn hạn chế của một học viên, luận văn này không thể tránh được những thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp ý kiến của các thầy cô để em có điều kiện bổ sung, nâng cao ý thức của mình, phục vụ tốt hơn trong công việc thực tế. Em xin chân thành cảm ơn! 6 DANH MỤC CÁC CHỮ VIẾT TẮT Chữ viết tắt Tên đầy đủ Ý nghĩa CBLS Constraint Based Local Tìm kiếm cục bộ dựa trên Search ràng buộc MMCVRP Min-Max Capacitated Bài toán định tuyến Vehicle Routing Problem đường đi các phương tiện nhằm tối thiểu hóa hành trình dài nhất ILP Integer Linear Program Quy hoạch nguyên tuyến tính VNS Variable Neighborhood Tìm kiếm trên các tập Search láng giềng khác nhau VRP Vehicle Routing Problem Bài toán vận tải CVRP Capacitated Vehicle Bài toán vận tải có ràng Routing Problem buộc sức chứa VRPTW Vehicle Routing Problem Bài toán vận tải có ràng with Time Window buộc về khung thời gian VRPPD VRP Pickup and Delivery Bài toán vận chuyển hàng hóa UAV Unmanned aerial vehicle Máy bay không người lái CBLSVR Constraint Based Local Tìm kiếm cục bộ dựa trên Search Vehicle Routing ràng buộc các bài toán vận tải API Application Programming Giao diện lập trình ứng Interface dụng SD Standard Deviation Độ lệch chuẩn MDR Minimum distance Route 7 DANH MỤC CÁC BẢNG Bảng 1.1: Nhóm hàm khởi tạo lời giải .2: Nhóm hàm truy vấn về trạng thái của lời giải .3: Một số hàm và ràng buộc cơ bản được thiết kế trong thư viện CBLSVR 30 Bảng 3.1: Mô tả bộ dữ liệu.2: Kết quả thử nghiệm với thuật toán greedy1 .3: Kết quả thử nghiệm với thuật toán greedy2 .4: Kết quả thử nghiệm với thuật toán greedy3 .5: Kết quả thử nghiệm với thuật toán greedy4 .6: Kết quả thử nghiệm với thuật toán greedy5 .7: Kết quả thử nghiệm với thuật toán greedy6 .8: Kết quả thử nghiệm với thuật toán greedy7 .9: Kết quả thử nghiệm với thuật toán greedy8 .10: Kết quả thử nghiệm với thuật toán greedy9 .11: Kết quả thử nghiệm với thuật toán greedy10 .12: Tổng hợp kết quả thử nghiệm với các thuật toán. 60 8 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Ví dụ 2 tuyến đường khác nhau .2: Minh họa thuật toán performTwoOptMove1(2,6) .3: Minh họa thuật toán performTwoOptMove2(2,6) .4: Minh họa thuật toán performTwoOptMove3(2,6) .5: Minh họa thuật toán performTwoOptMove4(2,6) .6: Ví dụ 2 tuyến đường khác nhau router[1], router[2].7: Minh họa thuật toán performTwoOptMove5(2,6) .8: Minh họa thuật toán performTwoOptMove6(2,6) .9: Minh họa thuật toán performTwoOptMove7(2,6) .10: Minh họa thuật toán performTwoOptMove8(2,6) .11: Ví dụ 2 tuyến đường với 5 điểm .12: Minh họa thuật toán performOrOptMove1(2,4,6) .13: Minh họa thuật toán performOrOptMove2(2,4,6) .14: Ví dụ tuyến đường với 8 điểm .15: Minh họa thuật toán performThreeOptMove1(2,4,6) .16: Ví dụ 2 tuyến đường router[1] và router [2] với các điểm khác nhau .17: Minh họa giải thuật performCrossExchangeMove(2,4,7,9) .18: Minh họa lộ trình vận tải cho 2 xe.
34 9 DANH MỤC CÁC GIẢ MÃ Giả mã 2.1: Thuật toán tham lam thứ 1 .2: Thuật toán tham lam thứ 2 .3: Thuật toán tham lam thứ 3 .4: Thuật toán tham lam thứ 4 .5: Thuật toán tham lam thứ 5 .6: Thuật toán tham lam thứ 6 .7: Thuật toán tham lam thứ 7 .8: Thuật toán tham lam thứ 8 .9: Thuật toán tham lam thứ 9 .10: Thuật toán tham lam thứ 10 .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 [18] [16], 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 đó D i là một tập rời rạc thể hiện miền giá trị của Xi. C = {C 1, …, 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. Khả năng khống chế của mỗi con hậu bao gồm: Khống chế những ô cùng hàng hoặc cùng cột.
11 Khống chế những ô thuộc cùng đường chéo. 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. Miền giá trị D = {D 1, D2, …, Dn} trong đó Di = {1…n} Mỗi biến Xi có miền từ 1 đến n. Tập ràng buộc: Xi ≠ Xj với i ≠ j: Các con hậu không ở cùng 1 hàng.
Xi + i ≠ Xj + j với i ≠ j: Các con hậu không khống chế theo đường chéo. Xi - i ≠ Xj - j với i ≠ j: Các con hậu không khống chế theo đường chéo. 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.
Miền giá trị x[i], D[i] = [0. 12 Tập ràng buộc: Xi ≠ Xj với i ≠ j Xi + i ≠ X j + 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 = x 1, X2 = x2, …, X7 = x 7} thỏa mãn tất cả các ràng buộc. 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’ = {y1, y2, …y7} sao cho: xi ≠ yi với một giá trị i duy nhất. xj = y j với mọi j ≠ i Chỉ có duy nhất một loại bước di chuyển là gán lại giá trị một phần tử Xi trong tập biến.
Lời giải được khởi tạo ngẫu nhiên. Tìm kiếm dừng lại khi không còn vi phạm. 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. Gán lại giá trị Xi thành giá trị làm giảm vi phạm nhiều nhất.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.