Luận án Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA HỒ VĂN HÙNG LUỒNG ĐA HÀNG HÓA ĐA CHI PHÍ TUYẾN TÍNH TỐI ƯU TRÊN MẠNG HỖN HỢP MỞ RỘNG LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐÀ NẴNG – Năm 2022 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA HỒ VĂN HÙNG LUỒNG ĐA HÀNG HÓA ĐA CHI PHÍ TUYẾN TÍNH TỐI ƯU TRÊN MẠNG HỖN HỢP MỞ RỘNG Chuyên ngành: Khoa học máy tính Mã số: 9480101 LUẬN ÁN TIẾN SĨ KỸ THUẬT Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến ĐÀ NẴNG – Năm 2022 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện, dưới sự hướng dẫn của PGS.TSKH. Trần Quốc Chiến. Tôi cam đoan các kết quả nghiên cứu được trình bày trong luận án là trung thực và không sao chép từ bất kỳ công trình nghiên cứu nào khác. Mọi trích dẫn trong luận án đều có ghi nguồn gốc xuất xứ rõ ràng và đầy đủ. Tác giả NCS. Hồ Văn Hùng LỜI CẢM ƠN Trước tiên, tôi xin bày tỏ lòng biết ơn sâu sắc và gửi lời tri ân đến PGS.TSKH. Trần Quốc Chiến đã tận tình hướng dẫn, truyền đạt kiến thức và kinh nghiệm nghiên cứu khoa học cho tôi trong suốt quá trình học tập, nghiên cứu và hoàn thành luận án. Tôi xin chân thành cảm ơn Phòng Đào tạo và Khoa Công nghệ thông tin cũng như các đơn vị có liên quan khác của Trường Đại học Bách khoa, Đại học Đà Nẵng đã luôn tạo điều kiện thuận lợi cho tôi trong thời gian làm nghiên cứu sinh tại đây. Xin cảm ơn Ban Lãnh đạo Trường Đại học Quảng Nam đã luôn hỗ trợ và tạo điều kiện tốt nhất để tôi hoàn thành tốt nghiên cứu này. Cuối cùng, tôi xin được gửi lời cảm ơn sâu sắc đến gia đình và bạn bè, đồng nghiệp những người luôn bên cạnh, giúp đỡ và động viên tôi trong suốt thời gian học tập, nghiên cứu và hoàn thành luận án. Đà Nẵng, ngày 14 tháng 11 năm 2022 i MỤC LỤC MỤC LỤC ......................................................................................... i DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT ......................... v DANH MỤC CÁC KÝ HIỆU ........................................................... vii DANH MỤC BẢNG .......................................................................... ix DANH MỤC HÌNH ............................................................................ x MỞ ĐẦU ........................................................................................... 1 CHƯƠNG 1. TỔNG QUAN ............................................................. 10 1.1. Đồ thị ....................................................................................... 10 1.1.1. Đồ thị vô hướng .......................................................................................... 10 1.1.2. Đồ thị có hướng .......................................................................................... 10 1.1.3. Đồ thị hỗn hợp ............................................................................................ 11 1.2. Mạng, luồng trên mạng ............................................................ 11 1.2.1. Mạng ........................................................................................................... 11 1.2.2. Luồng trên mạng ......................................................................................... 12 1.2.3. Lát cắt, đồ thị tăng luồng, đường đi tăng luồng .......................................... 12 1.3. Bài toán luồng cực đại trên mạng ............................................. 14 1.3.1. Giới thiệu bài toán ...................................................................................... 14 1.3.2. Phát biểu bài toán ........................................................................................ 15 1.3.3. Thuật toán Ford- Fulkerson ........................................................................ 15 1.3.4. Luồng cực đại và lát cắt cực tiểu ................................................................ 20 1.4. Bài toán quy hoạch tuyến tính .................................................. 21 1.4.1. Giới thiệu về quy hoạch tuyến tính ............................................................. 21 1.4.2. Các dạng bài toán quy hoạch tuyến tính ..................................................... 22 1.4.3. Bài toán đối ngẫu ........................................................................................ 26 1.5. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí ................................................................................................................................... 28 1.5.1. Mạng hỗn hợp mở rộng ........................................................ 28 1.5.2. Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí ....................................... 29 1.5.2.1 Giới thiệu .............................................................................................. 29 ii 1.5.2.2. Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí ............................... 30 1.5.3. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí ... 34 1.5.4. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí ....................................................................................... 34 1.6. Kết luận chương ....................................................................... 35 CHƯƠNG 2. XÂY DỰNG MÔ HÌNH VÀ THUẬT TOÁN GIẢI QUYẾT CÁC BÀI TOÁN LUỒNG TRÊN MẠNG HỖN HỢP MỞ RỘNG ĐA HÀNG HÓA ĐA CHI PHÍ ............................................................... 36 2.1. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa ch i phí ...... 36 2.1.1. Giới thiệu .................................................................................................... 36 2.1.2. Mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ......................................... 37 2.1.3. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ....................... 41 2.1.4. Kết luận ....................................................................................................... 42 2.2. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí .................................................................... 42 2.2.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ......................................................................................... 42 2.2.1.1. Giới thiệu bài toán ............................................................................... 42 2.2.1.2. Phát biểu bài toán ................................................................................ 42 2.2.1.3. Thuật toán MFMM .............................................................................. 45 2.2.1.4. Kết luận ............................................................................................... 53 2.2.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí........................................................................... 53 2.2.2.1. Giới thiệu bài toán ............................................................................... 53 2.2.2.2. Phát biểu bài toán ................................................................................ 54 2.2.2.3. Thuật toán CMF .................................................................................. 57 2.2.2.4. Kết luận ............................................................................................... 65 2.3. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ..................................... 65 2.3.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ........................................................... 65 iii 2.3.1.1. Giới thiệu bài toán ............................................................................... 65 2.3.1.2. Phát biểu bài toán ................................................................................ 66 2.3.1.3. Thuật toán LMF ................................................................................... 69 2.3.1.4. Kết luận ............................................................................................... 79 2.3.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ............................................. 79 2.3.2.1. Giới thiệu bài toán ............................................................................... 79 2.3.2.2 Phát biểu bài toán ................................................................................. 80 2.3.2.3. Thuật toán LCMF ................................................................................ 83 2.3.2.4. Kết luận ............................................................................................... 92 2.4. Mô hình và thuật toán bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu .......... 92 2.4.1. Giới thiệu bài toán ............................................................... 92 2.4.2. Phát biểu bài toán ................................................................ 93 2.4.3. Thuật toán MCMF ................................................................ 94 2.4.4. Kết luận .............................................................................. 96 2.5. Kết luận chương ....................................................................... 97 CHƯƠNG 3. ỨNG DỤNG PHÂN LUỒNG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG ............................................................................... 98 3.1. Sơ đồ một phần mạng lưới giao thông thành phố Đà nẵng ........ 98 3.2. Ứng dụng thuật toán MFMM phân luồng giao thông ................. 99 3.2.1. Giới thiệu ........................................................................... 99 3.2.2. Cài đặt thuật toán MFMM ........................................................................... 99 3.2.3. Kết quả chạy chương trình ........................................................................ 101 3.2.4. Phân tích kết quả ....................................................................................... 103 3.2.5. Kết luận ..................................................................................................... 107 3.3. Ứng dụng thuật toán CMF phân luồng giao thông .................. 107 3.3.1. Giới thiệu ......................................................................... 107 3.3.2. Cài đặt thuật toán CMF ............................................................................. 107 3.3.3. Kết quả chạy chương trình ........................................................................ 109 3.3.4. Phân tích kết quả ....................................................................................... 113 iv 3.3.5. Kết luận ..................................................................................................... 117 3.4. Ứng dụng thuật toán LMF phân luồng giao thông .................. 117 3.4.1. Giới thiệu ......................................................................... 117 3.4.2. Cài đặt thuật toán LMF ............................................................................. 117 3.4.3. Kết quả chạy chương trình ........................................................................ 120 3.4.4. Phân tích kết quả ....................................................................................... 122 3.4.5. Kết luận ..................................................................................................... 125 3.5. Ứng dụng thuật toán LCMF phân luồng giao thông ................ 126 3.5.1. Giới thiệu ......................................................................... 126 3.5.2. Cài đặt thuật toán LCMF .......................................................................... 126 3.5.3. Kết quả chạy chương trình ........................................................................ 128 3.5.4. Phân tích kết quả ....................................................................................... 130 3.5.5. Kết luận ..................................................................................................... 135 3.6. Ứng dụng thuật toán MCMF phân luồng giao thông ............... 135 3.6.1. Giới thiệu ......................................................................... 135 3.6.2. Cài đặt thuật toán MCMF ......................................................................... 135 3.6.3. Kết quả chạy chương trình ........................................................................ 136 3.6.4. Phân tích kết quả ....................................................................................... 138 3.4.4. Kết luận ..................................................................................................... 143 3.7. Kết luận chương ..................................................................... 143 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ........................................ 144 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ .......................... 145 TÀI LIỆU THAM KHẢO .............................................................. 146 PHỤ LỤC .......................................................................................... 1 Phụ lục 1: Khả năng thông hành thực tế của đỉnh ................................................ 1 Phụ lục 2: Hệ số quy đổi hàng hóa .......................................................................... 2 Phụ lục 3: Các cặp nguồn-đích ................................................................................ 3 Phụ lục 4: Khả năng thông hành thực tế của cạnh và chi phí cạnh ..................... 4 Phụ lục 5: Chi phí rẻ nhánh ..................................................................................... 6 Phụ lục 6: Các cặp nguồn-đích và lượng hàng cần chuyển ................................... 9 v DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT Viết tắt Tiếng Anh Tiếng Việt G Graph Đồ thị V Vertex Đỉnh E Edge Cạnh s Source Nguồn t Target Đích f Flow Luồng c Capacity Khả năng thông qua D Dual Đối ngẫu Max Maximum Cực đại Min cf rf Minimum Conversion flow Real flow Cực tiểu Luồng quy đổi Luồng thực tế MFMM Maximal flow on multicost multi- commodity extended mixed network Luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí LMF Maximal flow on multi-cost multi- commodity extended mixed network with limited cost Luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn CMF Maximal concurrent flow on multi- cost multi-commodity extended mixed network Luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí LCMF Maximal concurrent flow on multicost multi-commodity extended mixed network with limited cost Luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn MCMF Maximal concurent flow on multi- cost multi-commodity extended mixed network with minimal cost Luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu vi Viết tắt Tiếng Anh Tiếng Việt MSFP Maximal flow problem on single-cost multi-commodity extended mixed network Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí MFP Maximal flow problem on multi-cost multi-commodity extended mixed network Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí DM The dual problem of the MFP Bài toán đối ngẫu của MFP LMFP Maximal flow problem on multicost multi-commodity extended mixed network with limited cost Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn DL The dual problem of LMFP Bài toán đối ngẫu của LMFP CMFP Maximal concurrent flow problem on multicost multi-commodity extended mixed network Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí DC The dual problem of the CMFP Bài toán đối ngẫu của CMFP LCMFP Maximal concurrent flow problem on multicost multi-commodity extended mixed network with limited cost Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn DLC The dual problem of the LCMFP Bài toán đối ngẫu của LCMFP MCMFP Maximal concurrent flow problem on multicost multi-commodity extended mixed network with minimal cost Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu vii DANH MỤC CÁC KÝ HIỆU Ký hiệu Ý nghĩa G Đồ thị G V Tập các đỉnh v của đồ thị G E N* Tập các cạnh e của đồ thị G Tập các số tự nhiên khác 0 s Đỉnh nguồn t Đỉnh đích (P) Bài toán gốc dạng chuẩn max (D) Bái toán đối ngẫu của bài toán (P) r Số lượng hàng hóa lưu thông trên mạng ki Số cặp nguồn đích của hàng hóa loại i q Hệ số quy đổi hàng hóa f Tổng luồng f fv Giá trị của luồng f  Hệ số xấp xỉ  0.070  Hệ số cực đại đồng thời  0.834 B Chi phí giới hạn B 2201.440 Bf Tổng chi phí của luồng f 58325.582 cij Khả năng thông qua cung (i, j) fịj Luồng trên cung (i, j) cf Luồng quy đổi rf Luồng thực tế cfij(p) Luồng hàng hóa loại i quy đổi lưu hành từ đỉnh nguồn sij đến đỉnh đích tij dọc theo đường đi p viii Ký hiệu Ý nghĩa (sij, tij) Cặp nguồn- đích để chuyển hàng hóa loại i từ đỉnh nguồn sij đến đỉnh đích tij với i=1,...,r và j=1,...,ki Gf Đồ thị tăng luồng Ef Tập các cung trên Gf p Đường đi từ đỉnh nguồn sij đến đỉnh đích tij Pij Tập hợp các đường đi từ đỉnh nguồn sij đến đỉnh đích tij trên G có thể lưu hành hàng hóa loại i, i=1,...,r, j=1,...,ki. Pi Tập hợp các đường đi Pij của hàng hóa loại i trên G ứng với ki cặp đỉnh nguồn- đích (sij, tij) P Tập hợp các đường đi của Pi trên G. Pie Tập hợp các đường đi trong Pi đi qua cạnh e Piv Tập hợp các đường đi trong Pi đi qua đỉnh v bi(p) Chi phí lưu hành của một đơn vị hàng hóa loại i quy đổi qua đường đi p với i=1,...,r bvi(v,e,e’) Chi phí phải trả để chuyển một đơn vị hàng hóa loại i quy đổi từ cạnh e qua đỉnh v sang cạnh e’. ce(e) Khả năng thông hành cạnh e ze(e) Tỉ lệ thông hành cạnh e cv(v) Khả năng thông hành đỉnh v zv(v) Tỉ lệ thông hành đỉnh v ix DANH MỤC BẢNG Bảng 1.1. Quy tắc xây dựng bài toán đối ngẫu dạng chuẩn max .............................. 26 Bảng 1.2. Hệ số quy đổi hàng hóa theo TCVN 4054-2005 ...................................... 31 Bảng 1.3. Khả năng thông hành đỉnh ........................................................................ 31 Bảng 1.4. Khả năng thông hành cạnh ....................................................................... 32 Bảng 1.5. Chi phí đỉnh .............................................................................................. 32 Bảng 1.6. Chi phí cạnh .............................................................................................. 32 Bảng 2.1. Cặp đỉnh nguồn đích ................................................................................. 38 Bảng 2.2. Khả năng thông hành thực tế của đỉnh ..................................................... 38 Bảng 2.3. Chi phí rẽ nhánh ........................................................................................ 39 Bảng 2.4. Khả năng thông hành thực tế cạnh và chi phí cạnh .................................. 38 Bảng 2.5. Cặp đỉnh nguồn đích và lượng hàng cần chuyển ...................................... 54 Bảng 3.1. Kết quả chạy chương trình cài đặt thuật toán MFMM............................ 101 Bảng 3.2. Kết quả chạy chương trình cài đặt thuật toán CMF................................ 109 Bảng 3.3. Kết quả chạy chương trình cài đặt thuật toán LMF ................................ 120 Bảng 3.4. Kết quả chạy chương trình cài đặt thuật toán LCMF ............................. 128 Bảng 3.5. Kết quả chạy chương trình cài đặt