Luận án tiến sĩ kỹ thuật: Tối ưu luồng đa hàng hóa đa chi phí trên mạng hỗn hợp mở rộng - Hồ Văn Hùng, ĐH Bách Khoa Đà Nẵ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. Trần Quốc Chiến ĐÀ NẴNG – Năm 2022 LỜI CAM 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. 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 đủ. Hồ Văn Hùng LỜI CẢM 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. 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. Đồ thị vô hướng.

Đồ thị hỗn hợp. Mạng, luồng trên mạng. Luồng trên mạng. Lát cắt, đồ thị tăng luồng, đường đi tăng luồng.

Bài toán luồng cực đại trên mạng. Giới thiệu bài toán. Phát biểu bài toán. Thuật toán Ford- Fulkerson.

Luồng cực đại và lát cắt cực tiểu. Bài toán quy hoạch tuyến tính. Giới thiệu về quy hoạch tuyến tính. Các dạng bài toán quy hoạch tuyến tính.

Bài toán đối ngẫu. 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í. Mạng hỗn hợp mở rộng. Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí.

Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. 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í. Kết luận chương.

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Í. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 36 2. Mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí.

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í. 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í. Giới thiệu bài toán. Phát biểu bài toán.

Thuật toán MFMM. 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í. Giới thiệu bài toán. Phát biểu bài toán.

Thuật toán CMF. 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. 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. Giới thiệu bài toán.

Phát biểu bài toán. Thuật toán LMF. 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. Giới thiệu bài toán.2 Phát biểu bài toán.

Thuật toán LCMF. 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. Giới thiệu bài toán. Phát biểu bài toán.

Thuật toán MCMF. Kết luận chương. ỨNG DỤNG PHÂN LUỒNG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG. Sơ đồ một phần mạng lưới giao thông thành phố Đà nẵng.

Ứng dụng thuật toán MFMM phân luồng giao thông. Cài đặt thuật toán MFMM. Kết quả chạy chương trình. Phân tích kết quả.

Ứng dụng thuật toán CMF phân luồng giao thông. Cài đặt thuật toán CMF. Kết quả chạy chương trình. Phân tích kết quả.

Ứng dụng thuật toán LMF phân luồng giao thông. Cài đặt thuật toán LMF. Kết quả chạy chương trình. Phân tích kết quả.

Ứng dụng thuật toán LCMF phân luồng giao thông. Cài đặt thuật toán LCMF. Kết quả chạy chương trình. Phân tích kết quả.

Ứng dụng thuật toán MCMF phân luồng giao thông. Cài đặt thuật toán MCMF. Kết quả chạy chương trình. Phân tích kết quả.

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.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 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 MFMM commodity extended mixed network hợp 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 LMF commodity extended mixed network hợp mở rộng đa hàng hóa đa chi with limited cost phí 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- Bài toán luồng cực đại trên mạng MSFP cost multi-commodity hỗn hợp mở rộng đa hàng hóa đơn extended mixed chi phí network 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 Bài toán luồng cực đại đồng thời on multicost multi-commodity trên mạng hỗn hợp mở rộng đa LCMFP extended mixed network with hàng hóa đa chi phí với chi phí limited cost 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 Bài toán luồng cực đại đồng thời on multicost multi-commodity trên mạng hỗn hợp mở rộng đa MCMFP extended mixed network with hàng hóa đa chi phí với chi phí minimal cost cực tiểu vi 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 vi 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,.,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,. 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 bi(p) đường đ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.

Quy tắc xây dựng bài toán đối ngẫu dạng chuẩn max. Hệ số quy đổi hàng hóa theo TCVN 4054-2005. Khả năng thông hành đỉnh. Khả năng thông hành cạnh.

Chi phí đỉnh. Chi phí cạnh. Cặp đỉnh nguồn đích. Khả năng thông hành thực tế của đỉnh.

Chi phí rẽ nhánh. Khả năng thông hành thực tế cạnh và chi phí cạnh. Cặp đỉnh nguồn đích và lượng hàng cần chuyển. Kết quả chạy chương trình cài đặt thuật toán MFMM.

Kết quả chạy chương trình cài đặt thuật toán CMF. Kết quả chạy chương trình cài đặt thuật toán LMF.