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

Nội dung tài liệu: 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

1. ĐẠ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ố : 9.48.01.01 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐÀ NẴNG – Năm 2022
2. Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA- ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến Phản biện 1: Phản biện 2: Phản biện 3: Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Trường, Trường Đại học Bách khoa Vào hồi giờ ngày tháng năm 2022 Có thể tìm hiểu luận án tại: - Thư viện quốc gia Việt Nam. - Trung tâm Thông tin - Học liệu & Truyền thông- Đại học Đà Nẵng.
3. MỤC LỤC MỞ ĐẦU 1 CHƯƠNG 1. TỔNG QUAN 3 1.1. Đồ thị 3 1.2. Mạng, luồng trên mạng 3 1.3. Bài toán luồng cực đại trên mạng 3 1.4. Bài toán quy hoạch tuyến tính 3 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í 3 1.6. Kết luận chương 3 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Í 6 2.1. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 6 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í 7 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í 7 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í 9 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 12 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 12 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 15 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 18 2.5. Kết luận chương 20 CHƯƠNG 3. ỨNG DỤNG PHÂN LUỒNG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG 20 3.1. Sơ đồ một phần mạng lưới giao thông thành phố Đà nẵng 20 3.2. Ứng dụng thuật toán MFMM phân luồng giao thông 21 3.3. Ứng dụng thuật toán CMF phân luồng giao thông 21 3.4. Ứng dụng thuật toán LMF phân luồng giao thông 22 3.5. Ứng dụng thuật toán LCMF phân luồng giao thông 22 3.6. Ứng dụng thuật toán MCMF phân luồng giao thông 23 3.7. Kết luận chương 24 KẾT LUẬN 24
4. 1 MỞ ĐẦU 1. Tính cấp thiết của việc nghiên cứu Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, . Hiện nay, việc ứng dụng lý thuyết đồ thị để giải quyết các bài toán trong thực tế được các nhà khoa học quan tâm nghiên cứu. 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 trong các lĩnh vực kinh tế xã hội như giao thông, truyền thông, vận tải , khác với bài toán đơn hàng, trong bài toán mạng đa hàng hóa có nhiều loại hàng hóa được lưu thông trên mạng 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 lưu 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. 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 thực tế trong nhiều lĩnh vực từ mạng lưới truyền thông đến vận tải và năng lượng . 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. Tuy nhiên, cho đến nay các nghiên cứu chỉ mới giải quyết được bài toán luồng đa hàng hóa đơn chi phí vì ở đó các loại hàng hóa quy về một loại hàng hóa chuẩn cùng một loại chi phí (đơn chi phí). Nhưng trong thực tế có nhiều bài toán mà ở đó chi phí lưu hành ứng với mỗi loại hàng hóa khác nhau, không thể quy đổi chi phí lưu hành của mỗi loại hàng hóa theo hệ số quy đổi của hàng hóa chuẩn. Ngoài ra trên mạng có một số tuyến cấm lưu hành đối với một số loại hàng hóa có chi phí vượt ngưỡng cho phép nào đó. Bên cạnh đó, do yếu tố khách quan khả năng thông hành của tuyến không thể đạt được tối đa, do đó cần xác định một tỷ lệ thông hành hợp lý tùy vào tình hình thực tế. Vì vậy, để mô hình hóa các bài toán trong thực tế một các chính xác và hiệu quả hơn chúng ta cần phải xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chí phí. Xuất phát từ đó, luận án sẽ quan tâm đến vấn đề xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí để từ đó xây dự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, đây là vấn đề cần thiết nghiên cứu trong giai đoạn hiện nay nhằm mô hình hóa các bài toán trong thực tế chính xác và hiệu quả hơn. 2. Mục tiêu nghiên cứu Luận án tìm hiểu mô hình mạng, luồng trên mạng, mạng mở rộng đa hàng hóa đơn chi phí để từ đó xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và trên cơ sở đó đề xuất mô hình và thuật toán giải quyết các bài toán luồng tối ưu trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Luận án tập trung vào nghiên cứu các đối tượng sau: - Lý thuyết đồ thị, quy hoạch tuyến tính. - Bài toán tìm đường đi ngắn nhất . - Bài toán luồng cực đại trên mạng truyền thống. - 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í. - 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í.
5. 2 3.2. Phạm vi nghiên cứu Luận án nghiên cứu trong phạm vi như sau: mạng, luồng trên mạng, bài toán toán luồng cực đại trên mạng, bài toán luồng cực đại trên mạng đa hàng hóa đơn chi phí. Trên cơ sở đó xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí để từ đó xây dựng các bài toán luồng tối ưu sau: - Bài toán luồng cực đại. - Bài toán luồng cực đại đồng thời. - Bài toán luồng cực đại với chi phí giới hạn. - Bài toán luồng cực đại đồng thời với chi phí giới hạn. - Bài toán luồng cực đại đồng thời với chi phí cực tiểu. 4. Phương pháp nghiên cứu - Tổng hợp, phân tích các kết quả nghiên cứu trước đây từ đó tìm ra các vấn đề cần phải giải quyết. - Tìm các phương pháp mở rộng bài toán, cải tiến, xây dựng các thuật toán mới để giải quyết các vấn đề đặt ra. - Từ thực nghiệm đến chứng minh bằng phương pháp toán học để đề xuất các thuật toán mới. 5. Các đóng góp của luận án Luận án có những đóng góp sau: - Đề xuất mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. - Đề xuất mô hình và thuật toán giải quyết bài toán luồng cực đại, 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í. - Đề xuất mô hình và thuật toán giải quyết bài toán luồng cực đại, 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. - Đề xuất mô hình và thuật toán giải quyết 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. 6. Bố cục của luận án Luận án bao gồm: Phần mở đầu, nội dung gồm ba chương, phần kết luận và phần phụ lục. Phần mở đầu Chương 1: Tổng quan. 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í. Chương 3: Ứng dụng các thuật toán luồng tối ưu phân luồng giao thông tại thành phố Đà Nẵng. Phần kết luận: Trình bày các kết quả nghiên cứu cũng như hướng nghiên cứu phát triển. Phần phụ lục: Các bảng dữ liệu để cài đặt cho các thuật toán.
6. 3 CHƯƠNG 1. TỔNG QUAN 1.1. Đồ thị 1.2. Mạng, luồng trên mạng 1.3. Bài toán luồng cực đại trên mạng 1.4. Bài toán quy hoạch tuyến tính 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í 1.5.1. Mạng hỗn hợp mở rộng Mạng truyền thống mới chỉ xét đến trọng số của các cạnh và các đỉnh một cách độc lập, độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Trong thực tế 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 đi đến và tuyến đi khỏi đỉnh đó. Ví dụ như ở Hình 1.1 thì thời gian đi qua ngã tư của một phương tiện giao thông phụ thuộc vào hướng di chuyển của phương tiện đó theo hướng rẽ phải, rẽ trái hay đi thẳng. Hình 1.1. Mô hình nút giao thông Vì vậy, để mô hình hóa các bài toán trong thực tế chính xác và hiệu quả hơn, cần xây dựng một mô hình mạng hỗn hợp mở rộng, trong đó ngoài hàm trọng số cạnh còn có thêm hàm trọng số đỉnh cv(v,e,e’), với v là đỉnh của đồ thị và e, e’ là các cạnh liên thuộc của đỉnh v. Khả năng thông hành là trọng số thể hiện khả năng tối đa mà hàng hóa có thể lưu hành qua cạnh hoặc đỉnh. Cho đồ thị hỗn hợp G =(V, E) Cho các hàm sau: Hàm khả năng thông hành cạnh ce:E R*, với ce(e) là khả năng thông hành cạnh e E. Hàm khả năng thông hành đỉnh cv:V R*, với cv(v) là khả năng thông hành đỉnh v V. Bộ G= (V, E, ce, cv) gọi là mạng hỗn hợp mở rộng. 1.5.2. Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 1.5.2.1. Giới thiệu 1.5.2.2. Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí Mạng đa hàng hóa là mạng trên đó có nhiều loại hàng hóa lưu hành trên mạng. Chi phí có thể hiểu là chi phí về thời gian, chi phí về nhiên liệu, chi phí ô nhiễm môi trường v.v phải trả để lưu hành một đơn vị hàng hóa trên mạng. Cho mạng hỗn hợp mở rộng G=(V, E, ce, cv) như đã trình bày ở mục 1.5.1.
7. 4 Ký hiệu Ev là tập các cạnh liên thuộc đỉnh v V. Trên mạng có nhiều loại hàng hóa lưu hành, các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Các cạnh vô hướng biểu diễn tuyến hai chiều, trong đó các loại hàng hóa lưu hành trên cùng tuyến nhưng ngược hướng chia sẻ khả năng thông hành của tuyến. Cho các hàm sau: Hàm chi phí cạnh be:E R*, với be(e) là chi phí phải trả để chuyển một đơn vị hàng hóa qua cạnh e. Lưu ý rằng với những tuyến hai chiều thì chi phí hai hướng có thể khác nhau. * Hàm chi phí đỉnh bv:V Ev Ev R , với bv(v,e,e’) là chi phí phải trả để chuyển một đơn vị hàng hóa từ tuyến e qua đỉnh v sang tuyến e’. Bộ G= (V, E, ce, cv, be, bv) gọi là mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. Cho p là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1, , h+1, và các đỉnh vj, j = 1, , h, như sau: p = v → e1→ v1→ e2→ v2, →, , eh→ vh→ eh+1→ w. Định nghĩa chi phí lưu hành một đơn vị hàng hóa qua đường đi p, ký hiệu b(p), theo công thức sau: hh 1 b()()(,,) p  be ej bv v j e j ej 1 (1) jj Vậy, mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí là mạng trên đó có nhiều loại hàng hóa lưu hành nhưng ở đó chi phí lưu hành của các loại hàng hóa được quy về theo chi phí lưu hành của loại hàng hóa chuẩn (đơn chi phí). 1.5.3. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí Cho G=(V, E, ce, cv, be, bv) là mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí như đã định nghĩa ở mục 1.5.2.2. Trên mạng có nhiều loại hàng hóa lưu hành, các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Giả thiết trên G có k cặp đỉnh nguồn-đích (sj, tj), mỗi cặp được gắn một loại hàng hóa cần chuyển từ đỉnh nguồn sj đến đỉnh đích tj, j=1, ,k. Ký hiệu Pj là tập hợp các đường đi từ sj đến tj trong G, j=1, , k và đặt k P =  Pj (2) j 1 Với mỗi đường đi p Pj, j=1, ,k, ký hiệu biến x(p) là luồng phương tiện đi từ sj đến tj lưu hành dọc theo đường đi p. Ký hiệu Pe là tập hợp các đường đi trong P đi qua cạnh e, e E. Ký hiệu Pv là tập hợp các đường đi trong P đi qua đỉnh v, v V. Tập hợp f={x(p) | p Pj, j =1, ,k } gọi là luồng trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí, nếu thỏa mãn các ràng buộc về khả năng thông hành trên cạnh và đỉnh như sau:
8. 5  x()p ce( e ), e E (3) pP e  x( p ) cv ( v ),  v V (4) pP v 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í Cho mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí G=(V, E, ce, cv, be, bv) đã định nghĩa ở mục 1.5.2.2. Trên mạng có nhiều loại hàng hóa lưu hành, các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Các cạnh vô hướng biểu diễn tuyến hai chiều, trong đó các loại hàng hóa lưu hành trên cùng tuyến nhưng ngược hướng chia sẻ khả năng thông hành của tuyến. Giả thiết trên G có k cặp đỉnh nguồn-đích (sj, tj), mỗi cặp được gán một loại hàng hóa cần chuyển từ đỉnh nguồn sj đến đỉnh đích tj, j = 1, ,k. Trên G có nhiều phương án phân luồng. Nhiệm vụ của bài toán là tìm luồng f trên G sao cho giá trị luồng f là lớn nhất. Ký hiệu (MSFP) là 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í. Bài toán được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau: fv  x() p max pP thỏa mãn các ràng buộc  x()p ce( e ), e E pP e (MSFP)  x( p ) cv ( v ),  v V pP v x( p) 0, p P 1.6. Kết luận chương Trong chương này luận án trình bày các khái niệm cơ bản về đồ thị, mạng, luồng trên mạng, bài toán luồng cực đại trong mạng, thuật toán Ford –Fulkerson tìm luồng cực đại trên mạng, mạng hỗn hợp mở rộng, bài toán quy hoạch tuyến tính, bài toán đối ngẫu trong quy hoạch tuyến tính và 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í. Cho đến nay, các nghiên cứu chỉ mới giải quyết được bài toán đa hàng hóa đơn chi phí, vì ở đó chi phí lưu hành của các loại hàng hóa quy về theo hệ số của chi phí lưu hành hàng hóa chuẩn. Tuy nhiên, trong thực tế trên mạng có nhiều loại hàng hóa lưu hành ứng với mỗi loại hàng hóa có chi phí lưu hành khác nhau, không thể quy đổi chi phí lưu hành của mỗi loại hàng hóa theo hệ số quy đổi của hàng hóa chuẩn. Vì vậy cần xây dựng một mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí để có thể mô hình hóa được các bài toán trong thực tế hiệu quả hơn. Do đó, để mô hình hóa được các bài toán trong thực tế một cách chính xác và hiệu quả trên cơ sở lý thuyết của Chương 1 luận án đề xuất mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và các bài toán luồng tối ưu trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ở Chương 2.
9. 6 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Í 2.1. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 2.1.1. Giới thiệu 2.1.2. Mạng hỗn hợp mở rộng đa hàng hóa đa chi phí Cho mạng hỗn hợp mở rộng G=(V, E, ce, cv) như đã định nghĩa ở mục 1.5.1. * Ký hiệu Ev là tập các cạnh liên thuộc đỉnh v V, r N là số loại hàng hóa lưu hành trên mạng, qi > 0 là hệ số quy đổi của hàng hóa loại i về hàng hóa chuẩn trên mạng với i =1, ,r. Trên mạng có r loại hàng hóa lưu hành, tương ứng với mỗi loại hàng hóa có chi phí lưu hành khác nhau. Các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Các cạnh vô hướng biểu diễn tuyến hai chiều, trong đó các loại hàng hóa lưu hành trên cùng tuyến nhưng ngược hướng lưu hành chia sẻ khả năng thông hành của tuyến. Cho các hàm sau. Hàm hệ số phục vụ cạnh ze:E R*, với ze(e) là tỉ lệ thông hành cạnh e E (khả năng thông hành thực tế của cạnh e là ce(e).ze(e)) Hàm hệ số phục vụ đỉnh zv:V R*, với zv(v) là tỉ lệ thông hành đỉnh v V (khả năng thông hành thực tế của đỉnh v là cv(v).zv(v)) * Hàm chi phí cạnh hàng hóa i, i=1, ,r, bei:E R , với bei(e) là chi phí phải trả để chuyển một đơn vị hàng hóa loại i quy đổi qua cạnh e. Lưu ý rằng với những tuyến hai chiều thì chi phí lưu hành hai hướng có thể khác nhau. * Hàm chi phí chuyển nhánh hàng hóa i, i=1, ,r, bvi:V Ev Ev R , với bvi(v,e,e’) là 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’. Bộ G=(V, E, ce, ze, cv, zv,{bei, bvi, qi |i=1 r}) gọi là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. Lưu ý: Nếu hàng hóa loại i có chi phí bei(e)= trên tuyến e thì hàng hóa loại i bị cấm lưu hành trên tuyến e. Nếu hàng hóa loại i có chi phí bvi(v,e,e’)= thì hàng hóa loại i bị cấm lưu hành từ tuyến e qua đỉnh v sang tuyến e’. 2.1.3. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí Cho G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1, ,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2. Trên mạng G với mỗi loại hàng hóa loại i với i=1, ,r có ki cặp đỉnh nguồn-đích (sij, tij), j=1, ,ki, tương ứng với mỗi cặp đỉnh nguồn-đích (sij, tij) được gán một lượng hàng hóa loại i cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij. Ký hiệu Pij là 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. ki Đặt Pi = Pij là 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 j 1
10. 7 r đỉnh nguồn-đích (sij, tij), i=1, ,r, j=1, ,ki và P = Pi là tập hợp các đường đi của Pi i 1 trên G, i=1, ,r. Với mỗi đường đi p Pij, i=1, ,r, j=1, ,ki, ký hiệu biến cfij(p) là 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, i=1, ,r, j=1, ,ki. Ký hiệu Pie là tập hợp các đường đi trong Pi đi qua cạnh e, e E. Ký hiệu Piv là tập hợp các đường đi trong Pi đi qua đỉnh v, v V. Tập hợp f ={cfij(p) | p Pij, i=1, ,r, j=1, ,ki } gọi là luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí, nếu thỏa mãn các ràng buộc sau : - Luồng trên e E không vượt quá khả năng thông hành thực tế của mỗi cạnh: r ki   cfij ()p ce( e ). ee( ), e Ez (5) i 11 j p Pie - Luồng trên v V không vượt quá khả năng thông hành thực tế của mỗi đỉnh: r ki   cfij ()p cv( v ). vv( ), v Vz (6) i 11 j p Piv Biểu thức fvij  cfij ()p , i 1, , r ,jk 1, , i gọi là giá trị luồng hàng hóa loại i pP ij của cặp nguồn-đích (sij,tij) của f. ki Biểu thức fvi  fvij , i1, , r gọi là giá trị luồng của loại hàng hóa i của f. j 1 r Biểu thức fv  fvi gọi là giá trị luồng của f. i 1 2.1.4. Kết luận 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í 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í 2.2.1.1. Giới thiệu bài toán 2.2.1.2. Phát biểu bài toán Cho G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1, ,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2. Ta gọi f={cfij(p) |p Pij, i=1, ,r, j=1, ,ki} là luồng trên mạng G. Tồn tại nhiều phương án phân luồng trên mạng G. r ki Như vậy, nhiệm vụ của bài toán là tìm luồng có giá trị fv   cfij () p trên i 11 j p Pij mạng G lớn nhất. Ký hiệu (MFP) là 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í. Bài toán được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau:
11. 8 r ki fv   cfij ()p axm i 11 j p Pij thỏa mãn các ràng buộc r ki   cfij ()p ce( e ). ee( ), e Ez (MFP) i 11 j p Pie r ki   cfij ()p cv( v ). vv( ), v Vz i 11 j p Piv cfij()p 0, i 1, , r , j 1, , k i , pP i Để giải được bài toán (MFP) ta xây dựng bài toán quy hoạch tuyến tính đối ngẫu gọi là bài toán (DM). Trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DM) được xây dựng như sau: r ki Mỗi ràng buộc   cfij ()p ce( e ). ee( ), e Ez được gán một biến le(e) của i 11 j p Pie bài toán đối ngẫu (DM). r ki Mỗi ràng buộc   cfij () p cv( v ). zv ( v ), v V được gán một biến lv(v) của i 11 j p Piv bài toán đối ngẫu (DM). Khi đó, bài toán (DM) phát biểu như sau: DM(, le lv) ce().().() e ze e le e cv ().() v zv v.( lv v ) min e E v V thỏa mãn các ràng buộc (DM) le( e ) lv (v) 1, p P e p v p le(e) ≥ 0, e E, lv(v) ≥ 0, v V Cho p Pi, i=1, ,r là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1, ,(h+1) và các đỉnh vj, j=1, ,h như sau: p = v→e1→ v1→ e2→v2,→, , eh→ vh→ eh+1→w. Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) theo công thức sau: hh 1 lengthi ()()p  le ejj lv()v (7) j 11j Ký hiệu distij(le,lv) là độ dài đường đi ngắn nhất từ đỉnh nguồn sij đến đỉnh đích tij tính theo hàm độ dài lengthi(p), i=1, ,r, j=1, ,ki. Đặt (le,lv)=min{distij(le,lv) | i=1, ,r, j=1, ,ki}, vậy (le,lv) là độ dài ngắn nhất trong mọi đường đi giữa các cặp nguồn-đích. Việc giải bài toán (DM) tương đương với DM (le,lv) tìm hàm le:E R* và hàm lv:V R* sao cho đạt cực tiểu. (le,lv) DM(,) le lv Xét bài toán (DM ):  min le : E R , lv : V R  (,le lv)
12. 9 Bổ đề 2.2.1.1. Bài toán (DM) tương đương với bài toán (DM ) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.2.1.3. Thuật toán MFMM (a).Thuật toán MFMM Đầu vào: Mạng G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1, ,r}) và tỉ lệ xấp xỉ  . Đầu ra: Luồng cực đại f biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f ={cfij(e) | e E, i=1, ,r, j=1, ,ki } Luồng cực đại rf biểu diễn dạng tập hợp luồng thực tế tại các cạnh. rf = {rfij(e) | e E, i=1, ,r, j=1, ,ki} Giá trị tổng luồng fv, tổng chi phí của luồng Bf Các bước: Bước 1: Tính  và  theo hệ số xấp xỉ  1  1 1/ (1  ) và  ()1 e ; 2 1/ ()1  (mn ) Bước 2: Khởi gán: fv =0; e E, le(e)= ; cfij(e)=0; v V, lv(v)= ; Bước 3: Tìm cặp nút nguồn-đích (sij, tij), 1 i r và 1 j ki, có đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi( ). Chú ý đường đi p phải hợp lệ với hàng hóa loại i, tức là không chứa cạnh có chi phí hoặc nút có chi phí chuyển nhánh . Giả sử (le,lv)=min{distij(le,lv)|i=1, ,r,j=1, ,ki}=distimin,jmin(le,lv) Ký hiệu: imin và jmin là chỉ số cặp nút nguồn-đích có đường đi ngắn nhất . p là đường đi ngắn nhất; là độ dài ngắn nhất ; c là khả năng thông hành cạnh, đỉnh tối thiểu của p, tức là c=min{min{ce(e).ze(e)|e p},min{cv(v).zv(v)|v p}}; Bước 4: Điều chỉnh luồng: e p, cfimin,jmin(e)=cfimin,jmin(e)+c; le(e)= le(e).(1+.c/(ce(e).ze(e))); fv= fv +c ;v p, lv(v)= lv(v).(1+.c/(cv(v).zv(v))); Bước 5: Nếu 1 qua Bước 6, ngược lại quay về Bước 3. Bước 6: Xử lí giá trị kết quả đạt được. Kết thúc. (b). Độ phức tạp của thuật toán MFMM: O( 2.k.n3.(m+n).ln(m+n)) 2.2.1.4. Kết luận 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í 2.2.2.1. Giới thiệu bài toán 2.2.2.2. Phát biểu bài toán Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1, ,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2.
13. 10 Trên G có r loại hàng hóa lưu hành. Giả thiết với mỗi loại hàng hóa i, i=1, ,r, có ki cặp đỉnh nguồn-đích (sij, tij), j=1, ,ki, mỗi cặp được gán một lượng hàng hóa loại i, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij. Dij là số lượng hàng hóa loại i, i=1, ,r, cần chuyển từ sij đến tij, j=1, , ki. Đặt dij=qi.Dij là số lượng hàng hóa quy đổi loại i, i=1, ,r, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j = 1, , ki. Nhiệm vụ của bài toán là tìm một số  lớn nhất sao cho tồn tại một luồng {cfij(e) |e E, i=1, ,r, j=1, ,ki } chuyển ít nhất .dij đơn vị hàng hóa quy đổi loại i, i=1, ,r cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j = 1, , ki, tức là:  cfij( p ) λ.d ij , i = 1, ., r, j = 1, ., k i (8) pP ij Ký hiệu (CMFP) là 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í. Bài toán này được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau:  max thỏa mãn các ràng buộc r ki   cfij ()p ce( e ).ze ( e ), e E i 11 j p P ie r ki (CMFP)   cfij ()p cv( v ). vv( ), v Vz i 11 j p P iv  cpfij () .dij , i 1, , r , j 1, , ki pP ij  ≥ 0, cfij(p) ≥ 0, i=1, ,r, j = 1, ,ki, p Pij Ký hiệu (DC) là bài toán đối ngẫu của bài toán (CMFP), trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DC) được xây dựng như sau: r ki Mỗi ràng buộc   cfij () p ce(e).ze(e), e E được gán một biến le(e) của i 11 j p Pie bài toán đối ngẫu (DC). r ki Mỗi ràng buộc   cfij () p cv(v).zv(v), v V được gán một biến lv(v) của i 11 j p Piv bài toán đối ngẫu (DC). Mỗi ràng buộc  cfij(). p  d ij được gán một biến zij của bài toán (DC). pP ij Khi đó, bài toán (DC) phát biểu như sau: DC(,)le lv ce(). e ze ().() e le e cv (). v zv (). v lv()v min e E v V thỏa mãn các ràng buộc le()() e lv v ziij, 1, ,r ,  j 1, , k i , p Pi j e p v p (DC) r ki dzij.1 ij ij 11 le(e) ≥ 0, e E, lv(v) ≥ 0, v V, zij ≥ 0, i=1, ,r, j=1, ,ki
14. 11 Cho p P là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1, ,(h+1), và các đỉnh vj, j=1, ,h như sau: p = v → e1→ v1→ e2→ v2, →, , eh→ vh→ eh+1→ w Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) theo công thức sau: hh 1 lengthi ()()()p  leevj l v j (9) jj 11 Ký hiệu disti,j(le,lv) là độ dài đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi (p), i=1, ,r, j=1, ,ki. r ki Đặt (le,lv)=  dij .dist ij (le,lv), vậy (le,lv) là số lượng hàng hóa vận chuyển i 1 j 1 qua đường đi ngắn nhất giữa các cặp nguồn-đích. Việc giải bài toán (DC) tương đương với tìm hàm le:E R* và hàm lv:V R* sao DC(le,lv) cho đạt cực tiểu. (le,lv) DC(le,lv) * *  Xét bài toán (DC ):  = min le: E R ,lv :V R  (le,lv)  Bổ đề 2.2.2.1. Bài toán (DC) tương đương với bài toán (DC ) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.2.2.3. Thuật toán CMF (a). Thuật toán CMF Đầu vào: Mạng G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1, ,r}) và  tỉ lệ xấp xỉ. Giả thiết với mỗi loại hàng hóa i, i=1, ,r, có ki cặp nút nguồn-đích (sij, tij), j=1, , ki, mỗi cặp được gán một lượng hàng hóa quy đổi dij loại i, cần chuyển từ nút nguồn sij đến nút đích tij. Đầu ra: Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f = {fij(e) | e E, i=1, ,r, j=1, ,ki } Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng thực tế tại các cạnh rf = {rfij(e) | e E, i=1 r, j=1 ki} Hệ số cực đại đồng thời , fv, Bf . Các bước Bước 1: Tính các giá trị ,  theo hệ số xấp xỉ  1 1 m n   1 3 và  = 1  1  Bước 2 : Khởi gán i=1, ,r, j=1, ,ki, dij = Dij.qi ; DC(le,lv) = (m+n) ; e E le(e)=  /(ce(e)ze(e)) ; v V lv(v) = /(cv(v)zv(v)) ; i=1, , r, j=1, ,ki, e E, cfij(e)=0; //Giá trị luồng cfij(e) lúc đầu t = 0 ;//bước đếm giai đoạn khi (DC(t) < 1) DC(0) = (m+n) ; le0(e) = le(e), e E ; lv0(v) = lv(v), v V;
15. 12 Bf= 0; fv=0; Bước 3 : i=1, ,r, j=1, ,ki, { d'ij = dij ; do { Tìm đường đi ngắn nhất p từ sij đến tij tính theo hàm độ dài lengthi(.). Chú ý đường đi p phải hợp lệ với hàng hóa loại i, tức không chứa cạnh có chi phí hoặc nút có chi phí chuyển nhánh . Gán distij(le,lv) là độ dài đường đi ngắn nhất từ si,j đến tij tính theo hàm độ dài lengthi (p). bei(p) là chi phí của một đơn vị hàng hóa loại i quy đổi trên đường đi. Đặt c =min{min{ce(e).ze(e)|e p}, min{cv(v).zv(v)|v p}, d’ij} // Điều chỉnh luồng e p, cfij(e) =cfij(e) + c; le(e) = le(e).(1+.c/(ce(e).ze(e))); v p, lv(v)= lv(v).(1+.c/(cv(v).zv(v))); d’ij = d’ij c; Bf = Bf + c.bei(p); DC(le,lv) = DC(le,lv) + .c.distij(le,lv); } while (d’ij > 0); }// for for Bước 4: Hiệu chỉnh các giá trị t = t + 1; DC(t)=DC(le,lv); let(e) = le(e) e E, lvt(v) = lv(v); v V. if (DC(t) = 1 qua Bước 6, ngược lại quay về Bước 3 Bước 6: Xử lí giá trị kết quả đạt được. Kết thúc. 2 3 (b). Độ phức tạp của thuật toán CMF: O( .(cemax/dmax).(+k).m.n .log2(m+n)) 2.2.2.4. Kết luận 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 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 2.3.1.1. Giới thiệu bài toán 2.3.1.2. Phát biểu bài toán Cho G=(V,E, ce, ze, cv, zv, {bei, bvi, qi |i=1, ,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2. Có r loại hàng hóa lưu hành trên G, mỗi loại hàng hóa lưu hành trên mạng G có chi phí khác nhau. Giả thiết với mỗi loại hàng hóa i, i=1, ,r có ki cặp đỉnh nguồn-đích (sij,tij), j=1, ,ki, mỗi cặp được gán một lượng hàng hóa loại i, cần chuyển từ sij đến tij. Cho chi phí giới hạn B. Nhiệm vụ của bài toán là tìm luồng sao cho giá trị luồng là lớn nhất và đồng thời tổng chi phí của luồng không vượt quá B. Ta gọi f =cfij(p) | p Pij, i=1, ,.r, j=1, ,k } là luồng trên G.
16. 13 Ký hiệu Bf là tổng chi phí của luồng f trên G. Bf không được vượt quá chi phí B cho trước, tức là: r ki   cfij() p. b i()p B, i 1, , r, j 1, . , ki , pP ij (10) i 11 j p Pij Ký hiệu (LMFP) là 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. Bài toán được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau: r ki fv   cfij () p max i 11 j p Pij thỏa mãn các ràng buộc r ki   cfij ()p ce( e ). ee( ), e Ez i 11 j p Pie r ki (LMFP)   cfij ( p) cv( v ). zv ( v ), v V i 11 j p Piv r ki   cfij( p ). b i ( p ) B i 11 j p Pij cfij( p) 0, i 1, , r , j 1, , k i, p P ij Ký hiệu (DL) là bài toán đối ngẫu với bài toán (LMFP), trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DL) được xây dựng như sau: r ki Mỗi ràng buộc   cfij () p ce(e).ze(e),e E được gán một biến le(e) của i 11 j p Pie bài toán đối ngẫu (DL). r ki Mỗi ràng buộc   cfij () p cv(v).zv(v),v V được gán một biến lv(v) của i 11 j p Piv bài toán đối ngẫu (DL). r ki Mỗi ràng buộc   cfij( p ). b i ( p ) B được gán một biến của bài toán đối i 11 j p Pij ngẫu (DL). Khi đó, bài toán (DL) phát biểu như sau: DL(,,) le lv  ce ().().() e ze e le e cv ().().() v zv v lv v B . min e E v V thỏa mãn các ràng buộc (DL) le( e ) lv ( v ) bi ( p ) . 1 ,  p P ij e p v p le()0, e  e E , lv()0, v  v V , 0 Bây giờ, cho p Pi, i=1, ,r là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej với j=1, ,(h+1) và các đỉnh vj với j=1, ,h như sau : p = v → e1→ v1→ e2→ v2, →, , eh→ vh→ eh+1→ w
17. 14 Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) và theo công thức sau: hh 1 lengthi (p) =  le( e j ) lv ( v j ) b i (p) . (11) jj 11 Ký hiệu distij(le,lv, ) là độ dài đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi(p), i=1, ,r và j=1, ,ki. Đặt (le,lv, ) = min{distij(le,lv, ) | i=1, ,r, j=1, ,ki}, vậy (le,lv, ) là độ dài ngắn nhất trong mọi đường đi giữa các cặp nguồn-đích. Việc giải bài toán (DL) tương DL(le,lv, ) đương với tìm hàm le:E R* và hàm lv:V R* sao cho đạt cực tiểu. (le,lv, ) DL(,,) le lv Xét bài toán (DL ):  min le : E R , lv : V R , 0  (,,)le lv Bổ đề 2.3.1.1. Bài toán (DL) tương đương với bài toán (DL ) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.3.1.3. Thuật toán LMF (a). Thuật toán LMF Đầu vào: Mạng G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1, ,r}). Cho tỉ lệ xấp xỉ  và chi phí giới hạn B. Đầu ra: Luồng cực đại f biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f = {cfij(e) | e E, i=1, ,r, j=1, ,ki } Luồng cực đại rf biểu diễn dạng tập hợp luồng thực tế tại các cạnh. rf = {rfij(e) | e E, i=1, ,r, j=1, ,ki} Tổng giá trị luồng fv, tổng chí phí của luồng Bf Các bước Bước 1: Tính các giá trị bmin, bmax, ,  Tính bmin là chi phí nhỏ nhất trong các đường đi từ đỉnh nguồn sij đến đỉnh đích tij, bmin = min{bi(p) | i=1, ,r, j=1, ,ki, p Pij }. Tính bmax là chi phí lớn nhất trong các đường đi từ đỉnh nguồn sij đến đỉnh đích tij, bmax = max{bi(p) | i=1, ,r, j=1, ,ki, p Pij }. Tính  và  theo hệ số xấp xỉ  =1 1/(1 ) và  = (1+) 1 ; 2 1/ (1  ) (m n b max/ b min) Bước 2 : Khởi gán = /bmin; fv=0; Bf=0; e E, le(e)=;cfij(e)=0; v V, lv(v)=; Bước 3: Tìm cặp nút nguồn-đích (sij, tij), 1 i r và 1 j ki, có đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi( ). Chú ý đường đi p phải hợp lệ với hàng hóa loại i, tức là không chứa cạnh có chi phí hoặc nút có chi phí chuyển nhánh . Ký hiệu:
18. 15 imin và jmin là chỉ số cặp nút nguồn đích có đường đi ngắn nhất; là độ dài đường đi ngắn nhất;p là đường đi ngắn nhất; c là khả năng thông hành cạnh, đỉnh tối thiểu của p, tức là c=min{min{ce(e).ze(e)|e p},min{cv(v).zv(v)|v p}}; B’ là tổng chi phí của luồng f qua p, tức là B’ = c.bimin(p); nếu (B’>B) thì {c = c.B / B’; B’ = B} Bước 4: Điều chỉnh luồng e p ta điều chỉnh như sau : cfimin,jmin(e)=cfimin,jmin(e)+c;//Thay đổi giá trị của luồng cfimin,jmin(e). le(e)= le(e).(1+.c/(ce(e).ze(e))); // Thay đổi giá trị của hàm le. v p ta điều chỉnh như sau : lv(v)= lv(v).(1+.c/(cv(v).zv(v))); // Thay đổi giá trị của hàm lv. fv = fv +c ;// Thay đổi giá trị của luồng f ; = .(1+.B’/B); // Thay đổi giá trị hàm ; Bf = Bf + B’ ; // Thay đổi chi phí của luồng Bf ; Bước 5: Nếu 1 qua Bước 6, ngược lại quay về Bước 3 Bước 6: Xử lí giá trị kết quả đạt được. Kết thúc. (b). Độ phức tạp của thuật toán LMF: O( 2.k.n3.(m+n).ln(m+n+bmax/bmin)) 2.3.1.4. Kết luận 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 2.3.2.1. Giới thiệu bài toán 2.3.2.2 Phát biểu bài toán Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1, ,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2 và cho chi phí giới hạn B. Trên G có r loại hàng hóa lưu hành. Giả thiết với mỗi loại hàng hóa i, i=1, ,r, có ki cặp đỉnh nguồn-đích (sij, tij), j=1, ,ki, mỗi cặp được gán một lượng hàng hóa loại i, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij. Dij là số lượng hàng hóa loại i, i=1, ,r, cần chuyển từ sij đến tij, j =1, ,ki. Đặt dij =qi.Dij là số lượng hàng hóa quy đổi loại i, i=1, ,r, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j = 1, , ki. Nhiệm vụ của bài toán là tìm một số  lớn nhất sao cho tồn tại một luồng chuyển ít nhất .dij đơn vị hàng hóa quy đổi loại i, i=1, ,r, từ đỉnh nguồn sij đến đỉnh đích tij, j =1, ,ki với tổng chi phí không vượt quá B, tức là: r ki   cfij( p ). b i (p ) B, i 1, , r , j 1, , ki , pP ij (12) i 11jP p ij Ký hiệu (LCMFP) là 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 chí phí với chi phí giới hạn. Bài toán này được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau:
19. 16  max thỏa mãn các ràng buộc r ki   cfij ()p ce( e ). ee( ), e Ez i 11 j p Pie r ki   cfpij () cv( v ). zv ( v ),  v V i 11 j p P iv (LCMF  cfij ()p .dij , i 1, , r , j 1, , k i pP ij r ki   cfij( p ). b i ( p ) B i 11 j p Pij  ≥ 0, cfij(p) ≥ 0, i=1, , r, j=1, , ki, p Pij Ký hiệu (DLC) là bài toán đối ngẫu với (LCMFP), trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DLC) được xây dựng như sau: r ki Mỗi ràng buộc   cfij () p ce ( e ).() ze e , e E được gán một biến le(e) của i 11 j p Pie bài toán đối ngẫu (DLC). r ki Mỗi ràng buộc   cfij () p cv ( v ).() zv v , v V được gán một biến lv(v) của i 11 j p Piv bài toán đối ngẫu (DLC). Mỗi ràng buộc  cpfij ( ) .dij được gán một biến zij của bài toán đối ngẫu (DLC). p Pij r ki Mỗi ràng buộc   cfij( p ). b i ( p ) B được gán biến của bài toán (DLC). i 11 j p Pij Khi đó, bài toán (DLC) được phát biểu như sau: DnLC(,,) lelv  ce(). e ze(e ) cv().()v z e vB . mi e E e E thỏa mãn các ràng buộc lve()() e lv ziij , i 1, ,r , j 1, , k ,  p Pij e p v p (DLC) r k i dzij.1 ij ij 11 0, le(e) ≥ 0, e E, lv(v) ≥ 0, v V, zij ≥ 0, i=1, ,.r, j=1, ,ki Cho p P là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1, ,(h+1), và các đỉnh vj, i=1, ,.h, như sau: p = v → e1→ v1→ e2→ v2, →, , eh→ vh→ eh+1→ w Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) theo công thức sau:
20. 17 k 1 h lbeng thi ()()()p  le ej lv() vj i p . (13) jj 11 Ký hiệu distij(le,lv, ) là độ dài đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi(p), i=1, ,r, j=1, ,ki. r ki Đặt ()(,,)le,, lv dij. dist ij lle v , vậy (le lv, ) là số lượng hàng hóa vận ij 11 chuyển qua đường đi ngắn nhất giữa các cặp nguồn đích. Việc giải bài toán (DLC) tương DLC(le,lv, ) đương với tìm hàm le:E R* và hàm lv:V R* sao cho đạt cực tiểu. (le,lv, ) DLC(,,) le lv  Xét bài toán (DLC ):  min le : E R , lv : V R , 0 (,,)le lv  Bổ đề 2.3.2.1. Bài toán (DLC) tương đương với bài toán (DLC ) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.3.2.3. Thuật toán LCMF (a). Thuật toán CMF Đầu vào: Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1, ,r}) Giả thiết với mỗi loại hàng hóa i, i=1, ,r, có ki cặp nút nguồn-đích (sij, tij), j=1, , ki, mỗi cặp được gán một lượng hàng hóa quy đổi dij loại i, cần chuyển từ nút nguồn sij đến nút đích tij. Cho  là tỉ lệ xấp xỉ cần đạt được và chi phí giới hạn B. ◊ Đầu ra: Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f = {cfi,j(e) | e E, i=1, ,r, j=1, ,ki } Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng thực tế tại các cạnh rf = {rfi,j(e) | e E, i=1, ,r, j=1, ,ki} Hệ số cực đại đồng thời , fv, Bf . 1 1 mn 1  ◊ Các bước: Bước 1: Tính các giá trị ,  ;  1 3 ;  = 1  1  Bước 2 : Khởi gán DLC(le,lv)=(m+n+1); =  /B ; i=1, ,r, j=1, ,ki, di,j= Di,j.qi ; eE le(e)=  /(ce(e)ze(e)) ; v V lv(v) = /(cv(v)zv(v)) ; i=1, , r, j=1, ,ki, e E, cfij(e)=0;//Giá trị luồng cfij(e) lúc đầu t = 0 ;//bước đếm giai đoạn khi (DLC(t) < 1) DLC(0) = (m+n+1) ; // Giá trị hàm DLC(t) tại giai đoạn t=0 le0(e) = le(e), e E ; lv0(v) = lv(v) ,v V ; 0 = ; Bước 3: i=1, ,r, j=1, ,ki, { d'ij = dij ; do
21. 18 { Tìm đường đi ngắn nhất p từ si,j đến ti,j tính theo hàm độ dài lengthi(.). Chú ý đường đi p phải hợp lệ với hàng hóa loại i, tức không chứa cạnh có chi phí hoặc nút có chi phí chuyển nhánh . Gán disti,j(le,lv) là độ dài đường đi ngắn nhất từ si,j đến ti,j tính theo hàm độ dài lengthi (p), bei(p) chi phí cho một đơn vị hàng hóa quy đổi loại i trên đường đi p. c =min{min{ce(e).ze(e)|e p},min{cv(v).zv(v)|v p}, d’i,j} B’ = c.bi(p); if (B’>B) { c = c.B / B’; B’ = B; } e p,cfij(e)=cfij(e)+c;le(e)= le(e).(1+.c/(ce(e).ze(e))); v p, lv(v)= lv(v).(1+.c/(cv(v).zv(v))); = .(1+.B’/B) ; Bf = Bf + B’; d’ij = d’ij c; DLC(le,lv, ) = DLC(le,lv, ) + .c.distij(le,lv, ); } while (d’ij > 0); }// for for Bước 4 : Hiệu chỉnh các giá trị t = t + 1; DC(t)=DC(le,lv); let(e) = le(e) e E, lvt(v) = lv(v); v V. if (D(t) = 1 qua Bước 6, ngược lại quay về Bước 3 Bước 6: Xử lí giá trị kết quả đạt được. Kết thúc. 2 3 (b). Độ phức tạp của thuật toán LCMF: O( .(cemax/dmax).(+k).m.n .log2(m+n+1)) 2.3.2.4. Kết luận 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 2.4.1. Giới thiệu bài toán 2.4.2. Phát biểu bài toán Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1, ,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2. Có r loại hàng hóa lưu hành trên mạng G. Giả thiết với mỗi loại hàng hóa i, i=1, ,r, có ki cặp đỉnh nguồn-đích (sij, tij), j=1, ,ki, mỗi cặp được gán một lượng hàng hóa loại i, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij. Dij là số lượng hàng hóa loại i, i=1, ,r, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j = 1, ,ki. Đặt dij=qi.Dij là số lượng hàng hóa quy đổi loại i, i=1, ,r, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j =1, ,ki. Nhiệm vụ của bài toán là tìm một số  lớn nhất sao cho tồn tại một luồng chuyển ít nhất .dij đơn vị hàng hóa quy đổi loại i, i=1, ,r, từ đỉnh nguồn sij đến đỉnh đích tij, j =1, ,ki với tổng chi phí cực tiểu.
22. 19 Ký hiệu (MCMFP) là 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. Bài toán này được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau:  max thỏa mãn các ràng buộc r ki   cfij ()p ce( e ). ee( ), e Ez i 11 j p P ie r ki   cfpij () cv( v ). zv ( v ), v V (MCMFP) i 11 j p P iv  cfij ()p .dij ,  i 1,  , r , j 1, , ki p Pij  ≥ 0, cfij(p) ≥ 0, i=1, ,r, j=1, , ki, p Pij r ki và tổng chi phí   cfij( p ). b i ( p ) nhỏ nhất có thể. i 11 j p Pij 2.4.3. Thuật toán MCMF (a). Thuật toán MCMF Đầu vào: Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1, ,r}) và  là tỉ lệ xấp xỉ. Giả thiết với mỗi loại hàng hóa i, i=1, ,r, có ki cặp nút nguồn-đích (sij, tij), j=1, , ki, mỗi cặp được gán một lượng hàng hóa quy đổi dij loại i, cần chuyển từ nút nguồn sij đến nút đích tij. ◊ Đầu ra: Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f = {cfij(e) | e E, i=1, ,r, j=1, ,ki } Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng thực tế tại các cạnh rf = {rfij(e) | e E, i=1, ,r, j=1, , ki} Hệ số cực đại đồng thời , fv, Bf ◊ Các bước: Bước 1:Sử dụng thuật toán CMF với tỉ lệ xấp xỉ  ta nhận được hệ số cực đại đồng thời , luồng cực đại đồng thời f0 và tổng chi phí Bf; Đặt: max=; B0 =Bf; Bước 2: Sử dụng thuật toán LCMF với tỉ lệ xấp xỉ  và chi phí giới hạn B0 ta nhận được hệ số cực đại đồng thời 1, luồng cực đại đồng thời f1 và tổng chi phí B1 ; // B1 = max) do { Sử dụng thuật toán LCMF với tỉ lệ xấp xỉ  và chi phí giới hạn Bi ta nhận được hệ số cực đại đồng thời i+1, luồng cực đại đồng thời f i+1 và tổng chi phí B i+1; i=i+1; } Bước 4: while (i < max) do { Sử dụng thuật toán LCMF với tỉ lệ xấp xỉ  và chi phí giới hạn Bi = Bi-1*(max/i) ta nhận được hệ số cực đại đồng thời i+1, luồng cực đại đồng thời f i+1 và tổng chi phí B i+1; i=i+1; } Kết quả: max ; fi ; Bi.
23. 20 (b). Độ phức tạp của thuật toán MCMF: 2 3 O((t1+t2). .(cemax/dmax).(+k).m.n .log2(m+n+1)) 2.4.4. Kết luận 2.5. Kết luận chương Nội dung của chương 2, luận án đã trình bày các nội dung sau: (1) mạng hỗn hợp mở rộng đa hàng hóa đa chí phí và luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí; (2) bài toán luồng cực đại, 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í; (3) bài toán luồng cực đại, bài toán luồng cực đại đồ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; (4) 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. Luận án sử dụng mô hình bài toán quy hoạch tuyến tính ẩn để định nghĩa các bài toán luồng đa hàng hóa đa chi phí tối ưu. Bài toán đối ngẫu và các vấn đề liên quan được nghiên cứu và trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính đã xây dựng được các thuật toán xấp xỉ có độ phức tạp đa thức. Tính đúng đắn của thuật toán và độ phức tạp thuật toán được chứng minh. Đặc biệt, nội dung chính của chương này được công bố trong 05 bài báo chuyên ngành Công nghệ thông tin và được liệt kê ở tài liệu (1), (3), (5), (7), (9) trong danh mục các công trình đã công bố của tác giả. CHƯƠNG 3 ỨNG DỤNG PHÂN LUỒNG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG 3.1. Sơ đồ một phần mạng lưới giao thông thành phố Đà nẵng Cho mô hình mạng như Hình 3.1 thể hiện mạng lưới giao thông thành phố Đà Nẵng của Việt Nam, nơi tổ chức các hội nghị của Diễn đàn Hợp tác Kinh tế Châu Á- Thái Bình Dương (APEC) năm 2017 và cơ sở dữ liệu trong các Bảng Phụ lục 1, Bảng Phụ lục 2, Bảng Phụ lục 3, Bảng Phụ lục 4, Bảng Phụ lục 5, Bảng Phụ lục 5 trong phần Phụ lục. Hàng hóa chuẩn là hàng hóa loại 1 (Motor car) có hệ số quy đổi q=1. Hình 3.1. Sơ đồ một phần mạng lưới giao thông thành phố Đà Nẵng
24. 21 3.2. Ứng dụng thuật toán MFMM phân luồng giao thông 3.2.1. Giới thiệu Thuật toán MFMM đã được xây dựng ở mục 2.2.1.3 trong Chương 2. Trong phần này sẽ ứng dụng thuật toán MFMM vào phân luồng phương tiện giao thông trên mạng lưới giao thông thành phố Đà Nẵng thể hiện ở Hình 3.1. Luận án sẽ sử dụng ngôn ngữ lập trình C++ để cài đặt và thử nghiệm thuật toán MFMM. 3.2.2. Cài đặt thuật toán MFMM 3.2.3. Kết quả chạy chương trình Với cơ sở dữ liệu đã cho trong các Bảng ở phần Phụ lục và tham số đầu vào  =0.050, =0.070 thì kết quả chạy chương trình cài đặt thuật toán MFMM thể hiện ở Bảng 3.1 như sau: Bảng 3.1. Kết quả chạy chương trình cài đặt thuật toán MFMM Approximation ratio  0.050 0.070 Total flow fv 2780.135 2774.467 Total cost Bf 69170.259 68816.810 3.2.4. Phân tích kết quả Khi chạy chương trình cài đặt thuật toán MFMM với tỷ lệ xấp xỉ =0.050 cho kết quả giá trị của tổng luồng là fv=2780.135, trong khi đó nếu tham số đầu vào =0.070 thì giá trị của tổng luồng là fv=2774.467<2780.135 (fv khi =0.050), như vậy giá trị của luồng cực đại phụ thuộc vào , khi  càng nhỏ thì giá trị của luồng tìm được càng lớn. 3.2.5. Kết luận Trong phần này luận án sử dụng ngôn ngữ C++ để cài đặt thuật toán MFMM và kiểm tra thuật toán với dữ liệu đã cho, chương trình cho kết quả thể hiện ở Bảng 3.1. Kết quả nghiên cứu của phần này được công báo tại bài báo được liệt kê ở tài liệu (2) trong danh mục các công trình đã công bố của tác giả. 3.3. Ứng dụng thuật toán CMF phân luồng giao thông 3.3.1. Giới thiệu Thuật toán CMF đã được xây dựng ở mục 2.2.2.3 trong Chương 2. Trong phần này sẽ ứng dụng thuật toán CMF vào phân luồng phương tiện giao thông trên mạng lưới giao thông thành phố Đà Nẵng thể hiện ở Hình 3.1. Luận án sẽ sử dụng ngôn ngữ lập trình C++ để cài đặt và thử nghiệm thuật toán CMF. 3.3.2. Cài đặt thuật toán CMF 3.3.3. Kết quả chạy chương trình Với sở dữ liệu trong các Bảng ở phần Phụ lục, khi tham số đầu vào  =0.050 và =0.070, khi chạy chương trình cài đặt thuật toán CMF sẽ cho kết quả thể hiện ở Bảng 3.2 như sau: Bảng 3.2. Kết quả chạy chương trình cài đặt thuật toán CMF Approximation ratio  0.050 0.070 Maximal concurrent ratio  0.837 0.834 Total flow fv 2208.696 2201.442 Total cost Bf 67258.531 66355.742
25. 22 3.3.4. Phân tích kết quả Khi chạy chương trình cài đặt thuật toán CMF với tỷ lệ xấp xỉ =0.050 ta nhận được hệ số cực đại đồng thời =0.837 trong khi với tham số =0.070 thi hệ số cực đại đồng thời =0.834 <0.837 dẫn đến giá trị tổng luồng fv =2208.696 khi =0.050 lớn hơn giá trị tổng luồng fv=2201.442 khi =0.070. 3.3.5. Kết luận Trong phần này luận án sử dụng ngôn ngữ C++ để cài đặt thuật toán CMF. Với dữ liệu trong các Bảng ở phần Phụ lục và khi chạy chương trình với tham số đầu vào  =0.050 và  =0.070 chương trình cho ra kết quả như Bảng 3.2 ở trên. Kết quả nghiên cứu của phần này được công báo tại bài báo được liệt kê ở tài liệu (6) trong danh mục các công trình đã công bố của tác giả. 3.4. Ứng dụng thuật toán LMF phân luồng giao thông 3.4.1. Giới thiệu Thuật toán LMF đã được xây dựng ở mục 2.3.1.3 trong Chương 2. Trong phần này sẽ ứng dụng thuật toán LMF vào phân luồng phương tiện giao thông trên mạng lưới giao thông thành phố Đà Nẵng thể hiện ở Hình 3.1. Luận án sẽ sử dụng ngôn ngữ lập trình C++ để cài đặt và thử nghiệm thuật toán LMF. 3.4.2. Cài đặt thuật toán LMF 3.4.3. Kết quả chạy chương trình Với cơ sở dữ liệu trong các Bảng ở phần Phụ lục, khi chạy chương trình cài đặt thuật toán LMF với  =0.050, B=60000.000 và =0.070, B=60000.000 thì chương trình sẽ cho kết quả như Bảrng 3.3 sau: Bảng 3.3. Kết quả chạy chương trình cài đặt thuật toán LMF Approximation ratio  0.050 0.070 Limited Cosst B 60000.000 60000.000 Total flow fv 2697.668 2692.060 Total cost Bf 59337.381 59087.459 3.4.4. Phân tích kết quả Khi chạy chương trình LMF cho kết quả như Bảng 3.3, ta thấy rằng cùng chi phí giới hạn B=60000.000 nhưng với =0.050 cho kết quả fv=2697.668, trong khi đó với =0.070 thì là fv=2692.060<2697.668 (fv khi =0.050), đồng thời chi phí luồng Bf <B (Bf =59337.381< B khi =0.050 và Bf =59087.459 < B khi =0.070) 3.4.5. Kết luận Trong phần này luận án sử dụng ngôn ngữ C++ để cài đặt thuật toán LMF. Với dữ liệu trong các Bảng ở phần Phụ lục và khi chạy chương trình với tỷ lệ xấp xỉ  =0.050 và B=60000.000,  =0.070 và B=60000.000 chương trình cho ra kết quả như Bảng 3.3 ở trên. Kết quả nghiên cứu của phần này được công báo tại bài báo được liệt kê ở tài liệu (4) trong danh mục các công trình đã công bố của tác giả. 3.5. Ứng dụng thuật toán LCMF phân luồng giao thông 3.5.1. Giới thiệu Thuật toán LCMF đã được xây dựng ở mục 2.3.2.3 trong Chương 2. Trong phần này luận án sử dụng ngôn ngữ lập trình C++ để cài đặt thuật toán LCMF ứng dụng vào
26. 23 phân luồng phương tiện giao thông trên mạng lưới giao thông thành phố Đà Nẵng thể hiện ở Hình 3.1. 3.5.2. Cài đặt thuật toán LCMF 3.5.3. Kết quả chạy chương trình Với cơ sở dữ liệu trong các Bảng ở phần Phụ lục, khi chạy chương trình LCMF với tỷ lệ xấp xỉ  =0.050 với chi phí giới hạn B =55000.000 và  =0.070 với chi phí giới hạn B =55000.000 thì chương trình sẽ cho kết quả như Bảng 3.4 sau: Bảng 3.4. Kết quả chạy chương trình cài đặt thuật toán LCMF Approximation ratio  0.050 0.070 Limited cost B 55000.000 55000.000 Maximal concurrent ratio  0.797 0.794 Total flow fv 2104.576 2097.192 Total cost Bf 54609.574 54459.871 3.5.4. Phân tích kết quả Khi chạy chương trình cài đặt thuật toán LCMF, ta thấy rằng cùng chi phí giới hạn B=55000.000 nhưng với =0.050 cho hệ số cực đại đồng thời =0.797, trong khi đó với =0.070 thì hệ số cực đại đồng thời là =0.794<0.797, dẫn đến giá trị tổng luồng fv=2097.192 khi =0.070 nhỏ hơn giá trị tổng luồng fv =2104.576 khi =0.050. 3.5.5. Kết luận Trong phần này luận án sử dụng ngôn ngữ C++ để cài đặt thuật toán LCMF. Với dữ liệu trong các Bảng ở phần Phụ lục, với tỷ lệ xấp xỉ =0.050, =0.070 và chi phí giới hạn B=55000.00 chương trình cho ra kết quả như Bảng 3.4 ở trên. Kết quả nghiên cứu của phần này được công báo tại bài báo được liệt kê ở tài liệu (8) trong danh mục các công trình đã công bố của tác giả. 3.6. Ứng dụng thuật toán MCMF phân luồng giao thông 3.6.1. Giới thiệu Thuật toán CMF đã được xây dựng ở mục 2.4.3 trong Chương 2. Trong phần này sẽ ứng dụng thuật toán CMF vào phân luồng phương tiện giao thông trên mạng lưới giao thông thành phố Đà Nẵng thể hiện ở Hình 3.1. Luận án sẽ sử dụng ngôn ngữ lập trình C++ để cài đặt và thử nghiệm thuật toán CMF. 2. Cài đặt thuật toán MCMF 3.6.3. Kết quả chạy chương trình Với cơ sở dữ liệu trong các Bảng ở phần Phụ lục, khi chạy chương trình MCMF với tỷ lệ xấp xỉ  =0.050 và  =0.070 chương trình sẽ cho kết quả như Bảng 3.5 sau: Bảng 3.5. Kết quả chạy chương trình cài đặt thuật toán MCMF Approximation ratio  0.050 0.070 Maximal concurrent ratio  0.837 0.834 Total flow fv 2208.696 2201.440 Minimal total cost Bf 58691.750 58325.582 3.6.4. Phân tích kết quả Với tỷ lệ xấp xỉ =0.050 và  =0.070 thì khi chạy chương trình cài đặt thuật toán MCMF sẽ cho ra hệ số cực đại đồng thời khác nhau, khi =0.050 thì ta có =0.837 lớn
27. 24 hơn giá trị = 0.834 khi =0.070, vậy khi  càng nhỏ thì thuật toán MCFM sẽ cho ra giá trị luồng càng lớn, đồng thời khi so sánh kết quả chạy thuật toán CMF thể hiện ở Bảng 3.3 và thuật toán MCMF thể hiện ở Bảng 3.5, ta thấy rằng cả hai thuật toán đều cho kết quả hệ số cực đại đồng thời bằng nhau (=0.837) nhưng tổng chi phí luồng (Bf =58691.750) của thuật toán MCFM nhỏ hơn so với tổng chi phí luồng (Bf= 67258.531) của thuật toán CMF, nghĩa là thuật toán MCMF cho kết quả là luồng cực đại đồng thời với chi phí của luồng nhỏ nhất có thể. 3.4.4. Kết luận Trong phần này luận án sử dụng ngôn ngữ lập trình để cài đặt thuật toán MCMF bằng cách dùng hai thuật toán CMF và LCMF kết hợp với một số bước lặp. Với dữ liệu trong các Bảng dữ liệu ở phần Phụ lục, và tham số đầu vào tỷ lệ xấp xỉ  =0.050 chương trình cho ra hệ số cực đại đồng thời = 0.837, chi phí cực tiểu Bf =58691.750 và minh họa phân luồng cho các loại hàng hóa như trên. Kết quả nghiên cứu của phần này được công báo tại bài báo được liệt kê ở tài liệu (9) trong danh mục các công trình đã công bố của tác giả. 3.7. Kết luận chương Trong chương này, luận án ứng dụng các thuật toán đã xây dựng ở Chương 2 để phân luồng phương tiện trên mạng lưới giao thông tại thành phố Đà Nẵng thể hiện ở Hình 3.1. Luận án sử dụng thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng đa trọng số tại công kết hợp với ngôn ngữ lập trình C++ để cài đặt các thuật toán và cho kết quả thử nghiệm chính xác, cụ thể các thuật toán sau: (1) thuậ toán MFMM ; (2) thuật toán CMF; (3) thuật toán LMF; (4) thuật toán LCMF; (5) thuật toán MCMF. Nội dung chính của chương này được tác giả công bố trong 05 bài báo chuyên ngành Công nghệ thông tin và được liệt kê trong danh mục các công trình đã công bố của tác giả. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. Kết luận Luận án, với đề tài “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” đã đạt được các kết quả chủ yếu như sau: - Đề xuất xây dựng mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí nhằm mô hình hóa các bài toán trong thực tế chính xác và hiệu quả hơn. - Đề xuất mô hình và thuật toán giải quyết bài toán luồng cực đại, 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í. - Đề xuất mô hình và thuật toán giải quyết bài toán luồng cực đại, 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. - Đề xuất mô hình và thuật toán giải quyết 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. 2. Hướng phát triển Ứng dụng 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ào giải quyết nhiều bài toán trong thực tế trong nhiều lĩnh vực như: logistic, giao thông, kinh tế, mạng truyền thông và máy tính.
28. 25 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ (1). Trần Quốc Chiến, Hồ Văn Hùng, Mạng đa hàng hóa đa chi phí tuyến tính mở rộng và bài toán tìm luồng cực đại, Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ X. FAIR 2017, Đà Nẵng, ISBN: 978-604-913-614, 2017, trang 385-395, doi:10.15625/vap.2017.00047. (2). Tran Quoc Chien, Ho Van Hung, Applying algorithm finding shortest path in the multiple- weighted graphs to find maximal flow in extended linear multicommodity multicost network, EAI Endorsed Transactions on Industrial Networks and Intelligent Systems 12/ 2017 , Volume 4, Issue 11, pp 1-6, doi: 10.4108/eai.21-12- 2017.153499 (3). Tran Quoc Chien, Ho Van Hung, Extended Linear Multi-Commodity Multi-Cost Network and Maximal Flow Limited Cost Problems, The International Journal of Computer Networks & Communications (IJCNC),Volume 10, No. 1, (2018), pp 79-93, doi:10.5121/ijcnc.2018.10106 (SCOPUS index). (4). Ho Van Hung, Tran Quoc Chien, Implement and Test Algorithm finding Maximal Flow Limited Cost in extended multicomodity multi-cost network, The International Journal of Computer Techniques (IJCT), Volume 6 Issue 3, (2019), p.p 1-9. (5). Ho Van Hung, Tran Quoc Chien, Extended Linear Multi-Commodity Multi-Cost Network and Maximal Concurrent Flow Problems, the International Journal of Mobile Network Communications & Telematics (IJMNCT), Vol.9, No.1, (2019), pp 1-14 doi:10.5121/ijmnct.2019.9101. (6). Ho Van Hung, Tran Quoc Chien, Installing Algorithm to find Maximal Concurrent Flow in Multi-cost Multi-commodity Extended, International Journal of Innovative Science and Research Technology (IJISRT), Volume 4, Issue 12, (2019), pp 1110- 1119. (7). Ho Van Hung, Tran Quoc Chien, Maximal Concurrent Limited Cost Flow Problems on Extended Linear Multi-Commodity Multi-Cost Networks, American Journal of Applied Mathematics, Vol. 8, No. 3, 2020, pp 74-82, doi:0.11648/j.ajam.20200803.11. (8). Ho Van Hung, Tran Quoc Chien, Implement Algorithm Finding Maximal Concurrent Limited Cost Flow on Extended Multi-commodity Multi-cost Network, IOSR Journal of Computer Engineering (IOSR-JCE), 22.2 (2020), pp 34-44, doi: 10.9790/0661-2202023444. (9). Ho Van Hung, Tran Quoc Chien, Maximal Concurent Minimal Cost Flow Problems on Extended Multi-cost Multi-commodity Networks, The University of Danang - Journal of Science and Technology (UD- SJT), vol. 19, no. 6.1, June 2021, pp. 29-35¸