Luận án Tiến sĩ Kỹ thuật: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:177

Thêm vào BST

Báo xấu

12
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ Kỹ thuật "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" trình bày các nội dung chính sau: 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í; Ứng dụng phân luồng giao thông tại thành phố Đà Nẵng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Kỹ thuật: 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 chi 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ế của đỉnh ................................................ 1 Phụ lục 2: Hệ số quy đổi hàng hóa .......................................................................... 2 Phụ lục 3: Các cặp nguồn-đích ................................................................................ 3 Phụ lục 4: Khả năng thông hành thực tế của cạnh và chi phí cạnh ..................... 4 Phụ lục 5: Chi phí rẻ nhánh ..................................................................................... 6 Phụ lục 6: Cá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 Minimum Cực tiểu cf Conversion flow Luồng quy đổi rf Real flow Luồng thực tế Maximal flow on multicost multi- Luồng cực đại trên mạng hỗn hợp MFMM commodity extended mixed network mở rộng đa hàng hóa đa chi phí Maximal flow on multi-cost multi- Luồng cực đại trên mạng hỗn hợp LMF commodity extended mixed network mở rộng đa hàng hóa đa chi phí with limited cost với chi phí giới hạn Maximal concurrent flow on multi- Luồng cực đại đồng thời trên CMF cost multi-commodity extended mạng hỗn hợp mở rộng đa hàng mixed network hóa đa chi phí Maximal concurrent flow on Luồng cực đại đồng thời trên LCMF multicost multi-commodity extended mạng hỗn hợp mở rộng đa hàng mixed network with limited cost hóa đa chi phí với chi phí giới hạn Maximal concurent flow on multi- Luồng cực đại đồng thời trên MCMF cost multi-commodity extended mạng hỗn hợp mở rộng đa hàng mixed network with minimal cost 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 Maximal flow problem on single-cost Bài toán luồng cực đại trên mạng MSFP multi-commodity extended mixed hỗn hợp mở rộng đa hàng hóa đơn network chi phí Maximal flow problem on multi-cost Bài toán luồng cực đại trên mạng MFP multi-commodity extended mixed hỗn hợp mở rộng đa hàng hóa đa network chi phí DM The dual problem of the MFP Bài toán đối ngẫu của MFP Maximal flow problem on multicost Bài toán luồng cực đại trên mạng LMFP multi-commodity extended mixed hỗn hợp mở rộng đa hàng hóa đa network with limited cost 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 Maximal concurrent flow problem on Bài toán luồng cực đại đồng thời CMFP multicost multi-commodity extended trên mạng hỗn hợp mở rộng đa mixed network hàng hóa đa chi phí DC The dual problem of the CMFP Bài toán đối ngẫu của CMFP Maximal concurrent flow problem on Bài toán luồng cực đại đồng thời multicost multi-commodity extended trên mạng hỗn hợp mở rộng đa LCMFP mixed network with limited cost 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 Maximal concurrent flow problem on Bài toán luồng cực đại đồng thời multicost multi-commodity extended trên mạng hỗn hợp mở rộng đa MCMFP mixed network with minimal cost 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 Tập các cạnh e của đồ thị G N* 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ỉ   Hệ số cực đại đồng thời  B Chi phí giới hạn B Bf Tổng chi phí của luồng f 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 Chi phí lưu hành của một đơn vị hàng hóa loại i quy đổi qua đường bi(p) đi p với i=1,...,r Chi phí phải trả để chuyển một đơn vị hàng hóa loại i quy đổi từ bvi(v,e,e’) 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 thuật toán MCMF ............................136
x DANH MỤC HÌNH Hình 1.1. Cạnh nối cặp đỉnh i, j ................................................................................10 Hình 1.2. Đồ thị vô hướng ........................................................................................10 Hình 1.3. Cung nối cặp đỉnh i, j ................................................................................10 Hình 1.4. Đồ thị có hướng.........................................................................................11 Hình 1. 5. Đồ thị hỗn hợp..........................................................................................11 Hình 1.6. Mạng với đỉnh nguồn s đỉnh đích t ...........................................................11 Hình 1.7. Luồng trên mạng .......................................................................................12 Hình 1.8. Mạng biểu diễn lát cắt ...............................................................................13 Hình 1.9. Đồ thị tăng luồng Gf ..................................................................................13 Hình 1.10. Luồng sau khi tăng luồng ........................................................................14 Hình 1.11. Sơ đồ mạng G ..........................................................................................17 Hình 1.12. Mạng sau khi gán nhãn đỉnh s .................................................................17 Hình 1.13. Mạng sau khi đánh dấu đỉnh s và gán nhãn đỉnh b,c ..............................18 Hình 1.14. Mạng sau khi gán nhãn đỉnh s,c,b,t .........................................................18 Hình 1.15. Mạng sau khi tăng luồng theo P=(s,b,t) ..................................................18 Hình 1.16. Mạng sau khi gán nhãn đỉnh s,c,t ............................................................19 Hình 1.17. Mạng sau khi tăng luồng theo P=(s,c,t) ..................................................19 Hình 1.18. Mạng sau khi gán nhãn đỉnh s,d,e,t .........................................................19 Hình 1.19. Mạng sau khi tăng luồng theo P=(s,c,b,t) ...............................................19 Hình 1.20. Mạng sau khi gán nhãn đỉnh s,c với fv=6 ...............................................20 Hình 1.21. Mô hình nút giao thông ...........................................................................28 Hình 1.22. Mô hình mạng hỗn hợp mở rộng ............................................................29 Hình 1.23. Sơ đồ mạng giao thông hỗn hợp mở rộng ...............................................31 Hình 3.1. Sơ đồ một phần mạng lưới giao thông thành phố Đà Nẵng......................99 Hình 3.2. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán MFMM cho cặp nguồn-đích (1,4) ......................................................................................................103 Hình 3.3. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán MFMM cho cặp nguồn-đích (1,5) ......................................................................................................104 Hình 3.4. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán MFMM cho cặp nguồn-đích (1,9) ......................................................................................................104
xi Hình 3.5. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán MFMM cho cặp nguồn-đích (12,4) ....................................................................................................105 Hình 3.6. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán MFMM cho cặp nguồn-đích (12,5) ....................................................................................................105 Hình 3.7. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán MFMM cho cặp nguồn-đích (12,9) ....................................................................................................106 Hình 3.8. Sơ đồ phân luồng rf của hàng hóa loại 3 với thuật toán MFMM cho cặp nguồn-đích (12,16) ..................................................................................................106 Hình 3.9. Sơ đồ phân luồng rf của hàng hóa loại 4 với thuật toán MFMM cho cặp nguồn-đích (13,16) ..................................................................................................107 Hình 3.10. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán CMF cho cặp nguồn–đích (1,4) .....................................................................................................113 Hình 3.11. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán CMF cho cặp nguồn–đích (1,5) .....................................................................................................114 Hình 3.12. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán CMF cho cặp nguồn–đích (1,9) .....................................................................................................114 Hình 3.13. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán CMF cho cặp nguồn–đích (12,4) ...................................................................................................115 Hình 3.14. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán CMF cho cặp nguồn–đích (12,5) ...................................................................................................115 Hình 3.15. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán CMF cho cặp nguồn–đích (12,9) ...................................................................................................116 Hình 3.16. Sơ đồ phân luồng rf của hàng hóa loại 3 với thuật toán CMF cho cặp nguồn–đích (12,16) .................................................................................................116 Hình 3.17. Sơ đồ phân luồng rf của hàng hóa loại 4 với thuật toán CMF cho cặp nguồn–đích (13,16) .................................................................................................117 Hình 3.18. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán LMF cho cặp nguồn-đích (1,4) ......................................................................................................122 Hình 3.19. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán LMF cho cặp nguồn-đích (1,5) ......................................................................................................123
xii Hình 3.20. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán LMF cho cặp nguồn-đích (1,9) ......................................................................................................123 Hình 3.21. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán LMF cho cặp nguồn-đích (12,4) ....................................................................................................124 Hình 3.22. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán LMF cho cặp nguồn-đích (12,9) ....................................................................................................124 Hình 3.23. Sơ đồ phân luồng rf của hàng hóa loại 3 với thuật toán LMF cho cặp nguồn-đích (12,16) ..................................................................................................125 Hình 3.24. Sơ đồ phân luồng rf của hàng hóa loại 4 với thuật toán LMF cho cặp nguồn-đích (13,16) ..................................................................................................125 Hình 3.25. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán LCMF cho cặp nguồn –đích (1,4) ....................................................................................................131 Hình 3.26. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán LCMF cho cặp nguồn–đích (1,5) .....................................................................................................131 Hình 3.27. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán LCMF cho cặp nguồn–đích (1,9) .....................................................................................................132 Hình 3.28. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán LCMF cho cặp nguồn–đích (12,4) ...................................................................................................132 Hình 3.29. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán LCMF cho cặp nguồn–đích (12,5) ...................................................................................................133 Hình 3.30. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán LCMF cho cặp nguồn–đích (12,9) ...................................................................................................133 Hình 3.31. Sơ đồ phân luồng rf của hàng hóa loại 3 với thuật toán LCMF cho cặp nguồn–đích (12,16) .................................................................................................134 Hình 3.32. Sơ đồ phân luồng rf của hàng hóa loại 4 với thuật toán LCMF cho cặp nguồn–đích (13,16) .................................................................................................134 Hình 3.33. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán MCMF cho cặp nguồn–đích (1,4) .....................................................................................................139 Hình 3.34. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán MCMF cho cặp nguồn–đích (1,5) .....................................................................................................139
xiii Hình 3.35. Sơ đồ phân luồng rf của hàng hóa loại 1 với thuật toán MCMF cho cặp nguồn–đích (1,9) .....................................................................................................140 Hình 3.36. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán MCMF cho cặp nguồn–đích (12,4) ...................................................................................................140 Hình 3.37. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán MCMF cho cặp nguồn–đích (12,5) ...................................................................................................141 Hình 3.38. Sơ đồ phân luồng rf của hàng hóa loại 2 với thuật toán MCMF cho cặp nguồn–đích (12,9) ...................................................................................................141 Hình 3.39. Sơ đồ phân luồng rf của hàng hóa loại 3 với thuật toán MCMF cho cặp nguồn–đích (12,16) .................................................................................................142 Hình 3.40. Sơ đồ phân luồng rf của hàng hóa loại 4 với thuật toán MCMF cho cặp nguồn –đích (13,16) ................................................................................................142
1 MỞ ĐẦU 1. Tính cấp thiết của việc nghiên cứu Đồ thị là đối tượng nghiên cứu cơ bản của lý thuyết đồ thị, là lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng trong thực tế. Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh hoặc cung nối các đỉnh [37][47] và là công cụ hữu ích để mô hình hoá và giải quyết các bài toán trong nhiều lĩnh vực kỹ thuật, kinh tế, xã hội… Mạng là một dạng đồ thị có hướng có trọng số, trọng số của các cung trên mạng được hiểu là khả năng thông qua của cung. Mạng dùng để mô tả các mạng lưới giao thông vận tải, liên lạc, truyền tin, ... Bài toán luồng cực đại trên mạng, là một trong số các bài toán tối ưu có nhiều ứng dụng rộng rãi trong thực tế và được nhiều nhà nghiên cứu quan tâm. Bài toán được đề xuất vào năm 1956 bởi hai nhà toán học Mỹ là L. R. Jr. Ford và D. R. Fulkerson [30]. Sau đó, rất nhiều các giải thuật khác nhau đã được đề xuất nhằm cải tiến thuật toán Ford-Fulkerson, chẳng hạn tại công trình [25] các tác giả đã đề xuất thuật toán Edmonds–Karp để tìm luồng cực đại, tại công trình [26] J. B. Orlin đã đề xuất giải thuật tìm luồng cực đại với độ phức tạp O(nm), tại công trình [50][51] các tác giả đã đề xuất thuật toán hoán chuyển nguồn đích để tìm luồng cực đại, công trình [49] các tác giả đã đề xuất phương pháp kéo luồng sau tìm luồng cực đại, công trình [8] các tác giả đề xuất phương pháp đẩy luồng trước để tìm luồng cực đại. Bên cạnh đó, để giải quyết bài toán tìm luồng cực đại hiệu quả hơn các nhà nghiên cứu tại các công trình [15][39][44][64] đã đề xuất các thuật toán song song nhằm tăng khả năng và giảm thời gian thực hiện bài toán luồng cực đại. Tuy nhiên, các nghiên cứu trên mới chỉ giải quyết được bài toán luồng cực đại trên mạng đồ thị truyền thống. Trong đồ thị truyền thống do chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, nên độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh, các đỉnh trên đường đi đó. Nhưng trong thực tế có nhiều bài toán mà ở đó trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào tuyến đến và tuyến đi khỏi đỉnh đó. Để giải quyết vấn đề này tại công trình [35] các tác giả đã đề xuất chi phí chuyển làn (switch cost) cho đồ thị có hướng, trong công trình [57] các tác giả đã xây dựng mô hình đồ thị mở rộng có trọng số
2 cạnh và trọng số đỉnh phụ thuộc vào tuyến đến và tuyến đi ra khỏi đỉnh, trên cơ sở đó tác giả đã xây dựng thuật toán tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị mở rộng, tiếp theo đó tại công trình [58] các tác giả đã xây dựng thuật toán tìm luồng cực đại trên mạng mở rộng từ cải biên thuật toán Ford-Fulkerson và tại công trình [43] các tác giả đã xây dựng bài toán tìm luồng cực đại trên mạng giao thông mở rộng. Bài toán luồng đa hàng hóa trên mạng là bài toán tối ưu có nhiều ứng dụng, trên mạng có nhiều loại hàng hóa lưu hành như các gói tin, các phương tiện giao thông,… tùy thuộc vào loại hàng hóa mà cần nhu cầu vận chuyển khác nhau. Bài toán đặt ra là tìm luồng vận chuyển có chi phí cực tiểu và lưu lượng trên mỗi tuyến được chia sẻ cho nhiều loại hàng hóa. Tại công trình [45] nhóm tác giả đã xây dựng được thuật toán tổng quát cho bài toán luồng cực đại đa hàng hóa, tại công trình [53][54] các tác giả đã vận dụng thuật toán Dijkstra kết hợp với lý thuyết đối ngẫu trong quy hoạch tuyến tính để xây dựng thuật toán tìm luồng cực đại đa hàng hóa đồng thời, luồng cực đại đa hàng hóa đồng thời chi phí cực tiểu. Tại công trình [55] tác giả đã nghiên cứu xây dựng bài toán tìm luồng cực đại đa hàng hóa đồng thời chi phí cực tiểu trên mạng giao thông mở rộng dựa trên thuật toán tìm đường đi ngắn nhất trong đồ thị mở rộng đã được đề xuất trong công trình [57]. Bài toán luồng đa hàng hóa trên mạng đã trở nên phổ biến trong các tài liệu học thuật và ngày càng có nhiều nhà nghiên cứu quan tâm đến lĩnh vực này. Các ứng dụng của bài toán luồng đa hàng hóa trên mạng dùng để giải quyết nhiều bài toán trong nhiều lĩnh vực trong thực tế, cụ thể ở các lĩnh vực sau (1) logistic, hệ thống giao thông và kỹ thuật giao thông; (2) ngành kinh tế và năng lượng và cuối cùng (3) mạng truyền thông và máy tính. Trong lĩnh vực logistic, hệ thống giao thông và kỹ thuật giao thông (logistics and transportation): Năm 2010, Noguera và Leirens tại công trình [27] đã áp dụng mô hình bài toán luồng đa hàng hóa để xác định việc vận chuyển tối ưu các mặt hàng như xăng, dầu diesel trong mạng lưới liên kết giữa nhà máy lọc dầu, cảng và khách hàng. Với lượng phương tiện giao thông ngày càng tăng nên tại công trình [17] F. R. Zanjirani và các cộng sự đã ứng dụng bài toán luồng vào nghiên cứu đánh giá các vấn đề về mạng lưới giao thông đô thị từ đó đưa ra phương pháp giải quyết vấn đề liên quan đến di chuyển, bao gồm tắc nghẽn, ô nhiễm không khí, ô nhiễm tiếng ồn và tai
3 nạn. Trong một nghiên cứu khác [9] B. Bevrani và cộng sự đã giới thiệu mô hình luồng mạng đa hàng hóa cải tiến để đánh giá toàn diện hệ thống giao thông đa phương thức và xác định các luồng tối ưu có thể đạt được. Năm 2017, Wright và cộng sự [34] đã xây dựng mô hình bài toán tối ưu với tất cả các ràng buộc cần thiết để phân luồng đa hàng hóa tại một điểm giao. Năm 2019, Y Lu và cộng sự [63] đã đề xuất một thuật toán để việc giao và nhận hàng của nhân viên bán hàng du lịch đạt hiệu quả cao nhất, tại công trình [2] các tác giả đã ứng dụng bài toán luồng đa hàng hóa để giải quyết bài toán bố trí hướng dẫn viên du lịch hợp lý. Năm 2019, S. Vazir và cộng sự [42] đã đề xuất bài toán định tuyến phương tiện trong vấn đề giao và nhận hàng dựa trên sự hợp tác của nhà vận chuyển, mục tiêu của mô hình là tối đa hóa lợi nhuận và chia sẻ lợi nhuận công bằng giữa các hãng vận tải và giảm thiểu thời gian di chuyển. Tại công trình [66] các tác giả đã đề xuất giải pháp tối ưu cho việc giao và nhận hàng bán lẻ trong công ty thời trang ở Singapore. Tại công trình [33] Mohammadi và cộng sự tập trung vào đề xuất mô hình mạng lưới vận chuyển vật liệu nguy hiểm trong điều kiện không an toàn và tại công trình [16] các tác giả đã giải quyết vấn đề mất cân bằng giữa nhu cầu của người dùng và tính sẵn có của xe đạp ở các trạm bằng cách đề xuất một phương pháp định vị lại xe đạp một cách linh hoạt, xem xét dự báo mức tồn kho, dự báo lượng người dùng đến, và định tuyến xe theo một cách thống nhất. Tại công trình [6] A. Rudi và cộng sự đã xây dựng giải pháp vận tải hàng hóa đa phương thức để giảm các yếu tố như khí thải, chi phí vận chuyển cũng như cải thiện thời gian vận chuyển. Ngoài vận tải đường bộ, bài toán luồng đa hàng hóa có thể được áp dụng trong hệ thống giao thông đường sắt và đường biển, tại công trình [36]] M. Yaghini và R. Akhavan đã ứng dụng bài toán luồng vào thiết kế mạng lưới đa phương tiện trong quy hoạch vận tải hàng hóa đường sắt, tiếp đó năm 2013 Z. Lin và R. Kwan [65] đã ứng dụng bài toán luồng đa hàng hóa vào vấn đề lập lịch trình cho tàu hỏa. Tại công trình [1] các tác giả đã xây dựng mô hình luồng đa hàng hóa để tối ưu hóa công suất đường sắt trong trường hợp tắc nghẽn. Như chúng ta đã biết, hàng không được công nhận là một phương thức vận chuyển nhanh chóng và an toàn, đã tạo ra một sự đột biến lớn trong cơ sở hạ tầng