Tổng quan về luận án

Lý thuyết luồng trên mạng (network flow theory) bắt nguồn từ công trình nền tảng của hai nhà toán học L. R. Ford và D. R. Fulkerson (1956), đóng vai trò then chốt trong tối ưu hóa tổ hợp, khoa học máy tính và kỹ thuật giao thông vận tải. Tuy nhiên, các mô hình đồ thị truyền thống $G = (V, E)$ chỉ tiếp cận cấu trúc mạng đơn giản, nơi trọng số thông hành và chi phí chỉ được gán độc lập cho từng cạnh hoặc cung, đồng thời giả định chỉ có một loại hàng hóa (single-commodity) hoặc quy đổi các loại hàng hóa khác nhau về một loại hàng hóa chuẩn duy nhất thông qua hệ số tương đương $q$. Trong thực tế hạ tầng giao thông đô thị và logistics phức tạp, các nút giao thông (đỉnh $v \in V$) luôn tồn tại chi phí rẽ nhánh phụ thuộc trực tiếp vào hướng di chuyển (tuyến vào $e$ và tuyến ra $e'$), các tuyến đường có thể là một chiều (cung) hoặc hai chiều chia sẻ năng lực thông hành (cạnh vô hướng), và mỗi loại phương tiện/hàng hóa sở hữu cấu trúc chi phí vận hành hoàn toàn độc lập, không thể đồng nhất hóa tuyến tính.

Luận án tiến sĩ kỹ thuật chuyên ngành Khoa học máy tính (Mã số: 9480101) của tác giả Hồ Văn Hùng, dưới sự hướng dẫn khoa học của PGS. Trần Quốc Chiến tại Trường Đại học Bách khoa – Đại học Đà Nẵng (2022) 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" đã giải quyết triệt để khoảng trống nghiên cứu này. Nghiên cứu xác lập mô hình toán học toàn diện và hệ thống thuật toán xấp xỉ đa thức hiệu năng cao cho 5 bài toán luồng tối ưu cốt lõi trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí, tích hợp đầy đủ chi phí rẽ nhánh tại nút, ràng buộc tỷ lệ thông hành thực tế và giới hạn ngân sách chi phí.

Hệ thống câu hỏi nghiên cứu và giả thuyết khoa học được xác định chặt chẽ:

  • Câu hỏi nghiên cứu 1 (RQ1): Làm thế nào để thiết lập mô hình toán học chuẩn hóa cho mạng hỗn hợp mở rộng tích hợp đồng thời cạnh có hướng, cạnh vô hướng, khả năng thông hành đỉnh/cạnh ($c_v, c_e$), tỷ lệ thông hành thực tế ($z_v, z_e$), và hàm chi phí rẽ nhánh riêng biệt $b_v^i(v, e, e')$ cho từng loại hàng hóa $i$?
  • Câu hỏi nghiên cứu 2 (RQ2): Cấu trúc bài toán đối ngẫu (Dual Problem) và điều kiện tối ưu bù (Complementary Slackness) tương ứng với các bài toán luồng đa hàng hóa đa chi phí được thiết lập như thế nào để đảm bảo tính hội tụ thuật toán?
  • Câu hỏi nghiên cứu 3 (RQ3): Làm thế nào để xây dựng các thuật toán xấp xỉ giải quyết bài toán luồng cực đại (MFMM), luồng cực đại đồng thời (CMF), luồng cực đại với chi phí giới hạn (LMF), luồng cực đại đồng thời với chi phí giới hạn (LCMF) và luồng cực đại đồng thời với chi phí cực tiểu (MCMF) với tỷ lệ xấp xỉ $(1 - \epsilon)$?
  • Câu hỏi nghiên cứu 4 (RQ4): Hiệu năng tính toán và khả năng phân luồng thực tế của hệ thống thuật toán đề xuất đạt mức độ tối ưu ra sao khi thực nghiệm trên mạng lưới giao thông thực tế của thành phố Đà Nẵng?

Hệ thống giả thuyết khoa học tương ứng:

  • Giả thuyết 1 (H1): Việc mô hình hóa chi phí rẽ nhánh tại đỉnh $b_v^i(v, e, e')$ và đa chi phí độc lập cho từng loại hàng hóa sẽ loại bỏ sai số ước lượng lưu lượng của mô hình đơn chi phí truyền thống, phản ánh chính xác trạng thái phân luồng thực tế.
  • Giả thuyết 2 (H2): Dựa trên lý thuyết đối ngẫu trong quy hoạch tuyến tính và kỹ thuật hiệu chỉnh nhãn tăng luồng tựa Dijkstra, các thuật toán xấp xỉ đề xuất đạt nghiệm tối ưu $\epsilon$-xấp xỉ trong thời gian đa thức hữu hạn.
  • Giả thuyết 3 (H3): Thuật toán CMF và LCMF đảm bảo tối đa hóa đồng thời tỷ lệ đáp ứng nhu cầu $\lambda$ cho mọi cặp nguồn - đích $(s_{ij}, t_{ij})$ mà không gây nghẽn cục bộ trên các cung liên kết trọng yếu.
  • Giả thuyết 4 (H4): Việc áp dụng hệ thống thuật toán đề xuất trên sơ đồ mạng giao thông trung tâm thành phố Đà Nẵng với 4 phân lớp phương tiện theo chuẩn TCVN 4054-2005 sẽ tối ưu hóa năng lực thông hành và giảm thiểu tổng chi phí di chuyển so với các giải pháp phân luồng cổ điển.

Khung lý thuyết nền tảng tích hợp Lý thuyết Đồ thị mở rộng (Extended Graph Theory), Quy hoạch Tuyến tính (Linear Programming), Lý thuyết Đối ngẫu (Duality Theory), và Lý thuyết Tối ưu hóa Luồng Đa hàng hóa (Multicommodity Network Flow Theory). Phạm vi nghiên cứu thực nghiệm bao trùm mạng lưới giao thông phức hợp tại thành phố Đà Nẵng với tập hợp 8 cặp đỉnh nguồn - đích đa chiều bao gồm các cặp: $(1,4)$, $(1,5)$, $(1,9)$, $(12,4)$, $(12,5)$, $(12,9)$, $(12,16)$, $(13,16)$ tương ứng với các phân lớp phương tiện từ xe con (Motor car), xe tải nhẹ (Light truck), đến xe tải nặng (Heavy truck).

Literature Review và Positioning

Khảo sát tổng quan y văn quốc tế cho thấy sự tiến hóa rõ nét qua ba dòng nghiên cứu chính:

[Dòng 1: Cổ điển]           [Dòng 2: Đa hàng hóa]       [Dòng 3: Mạng mở rộng]
Ford & Fulkerson (1956)     Garg & Könemann (2007)      Winter (2002): switch cost
Edmonds & Karp (1972)       Karakostas (2008)           Trần Quốc Chiến et al. (2010-18)
Orlin (2013): O(nm)         Salimifard et al. (2020)    (Đơn chi phí, chuẩn hóa q)

Dòng nghiên cứu 1 - Bài toán luồng cực đại trên đồ thị truyền thống: Khởi đầu từ thuật toán đường tăng luồng của Ford và Fulkerson (1956), Edmonds và Karp (1972) cải tiến thuật toán với độ phức tạp đa thức $O(V E^2)$ bằng kỹ thuật tìm kiếm theo chiều rộng (BFS). J. B. Orlin (2013) đạt bước đột phá lý thuyết khi thiết lập giải thuật tìm luồng cực đại nhanh nhất với độ phức tạp $O(nm)$ cho đồ thị $n$ đỉnh, $m$ cạnh. Tiếp đó, các phương pháp đẩy luồng trước (push-relabel) của Goldberg và Tarjan, phương pháp kéo luồng sau, hoán chuyển nguồn đích, và các thuật toán tính toán song song đã nâng cao đáng kể tốc độ xử lý trên đồ thị có hướng đơn giản.

Dòng nghiên cứu 2 - Luồng đa hàng hóa và phương pháp quy hoạch tuyến tính: Bài toán luồng đa hàng hóa (Multicommodity Flow Problem) đặt trọng tâm vào việc chia sẻ dung lượng mạng giữa nhiều luồng hàng hóa khác nhau. I-Lin Wang (2018) đã hệ thống hóa các mô hình toán học và đánh giá hiệu năng các thuật toán lập trình tuyến tính cho luồng đa hàng hóa trong suốt ba thập kỷ. Khodakaram Salimifard và cộng sự (2020) tổng kết toàn diện các công trình từ năm 2000 đến 2019, chỉ ra rằng việc giải quyết bài toán luồng đa hàng hóa quy mô lớn đòi hỏi sự kết hợp chặt chẽ giữa thuật toán xấp xỉ đối ngẫu (primal-dual approximation schemes) và kỹ thuật phân rã đường đi (path decomposition).

Dòng nghiên cứu 3 - Mạng mở rộng và chi phí chuyển làn: Nhận thấy hạn chế của đồ thị truyền thống khi không thể biểu diễn chi phí tại nút giao, Winter (2002) đề xuất mô hình chi phí chuyển làn (switch cost) trên đồ thị có hướng. Trần Quốc Chiến và cộng sự (2010, 2013, 2018) đã mở rộng thành công mô hình đồ thị có trọng số đỉnh phụ thuộc tuyến đến và tuyến đi $b_v(v, e, e')$, xây dựng thuật toán tìm đường đi ngắn nhất và luồng cực đại trên mạng mở rộng đơn chi phí.

Tranh luận học thuật và xung đột lý thuyết: Y văn tồn tại một giả định kinh điển: tất cả các loại hàng hóa/phương tiện có thể quy đổi đồng nhất về "xe con tiêu chuẩn" (Passenger Car Unit - PCU) thông qua hệ số quy đổi $q$ (ví dụ: TCVN 4054-2005 quy định Motor car $q=1$, Light truck $q=2$, Heavy truck $q=3$). Giả định này đồng nghĩa với việc chi phí lưu hành của phương tiện loại $i$ trên đường đi $p$ đơn thuần bằng $q \times b(p)$. Tuy nhiên, thực tiễn vận tải chỉ ra xung đột lớn: chi phí tiêu hao nhiên liệu, chi phí khấu hao, phí môi trường và độ trễ rẽ nhánh của xe tải nặng tại các nút giao không tỷ lệ thuận tuyến tính với hệ số $q$. Hơn nữa, nhiều phân đoạn đô thị áp dụng biển cấm theo giờ hoặc cấm tuyệt đối đối với xe tải nặng, khiến chi phí vượt ngưỡng vô hạn, trong khi xe con vẫn lưu thông bình thường.

So sánh với các nghiên cứu quốc tế điển hình:

  1. Nghiên cứu của Noguera và Leirens (2010) tối ưu hóa luồng đa hàng hóa vận chuyển xăng dầu giữa nhà máy lọc dầu, cảng biển và khách hàng, nhưng chỉ áp dụng trên mạng có hướng đơn chi phí và bỏ qua hoàn toàn độ trễ rẽ nhánh tại các nút trung chuyển.
  2. Công trình của Wright và cộng sự (2017) tối ưu hóa luồng đa hàng hóa tại một điểm giao cắt riêng lẻ với các ràng buộc hình học, nhưng chưa khái quát hóa được mô hình luồng đồng thời trên toàn bộ mạng lưới hỗn hợp mở rộng quy mô lớn với chi phí giới hạn.
  3. Giải thuật GeoDivRP của Cheng và Sterbenz định tuyến đa đường dẫn phân tách trong mạng viễn thông chịu thảm họa, tuy nhiên không xử lý được bài toán chia sẻ năng lực thông hành trên các liên kết vô hướng hai chiều dưới cấu trúc đa chi phí độc lập.

Công trình của Hồ Văn Hùng (2022) định vị chính xác tại điểm giao thoa giữa mạng hỗn hợp mở rộng (cạnh có hướng và vô hướng, chi phí rẽ nhánh tại đỉnh) và bài toán đa hàng hóa đa chi phí độc lập, tạo nên bước nhảy vọt về mặt mô hình hóa lý thuyết và công cụ thuật toán.

Đóng góp lý thuyết và khung phân tích

        MÔ HÌNH TOÁN HỌC & HỆ THỐNG ĐỐI NGŨ TRONG LUẬN ÁN
                     Quan hệ Đối ngẫu Tuyến tính
                    (Linear Programming Duality)
               Thiết kế Thuật toán ε-Xấp xỉ Đa thức
                 (MFMM, CMF, LMF, LCMF, MCMF)

Đóng góp cho lý thuyết

Luận án đã mở rộng toàn diện lý thuyết luồng cực đại của Ford-Fulkerson và lý thuyết quy hoạch tuyến tính đối ngẫu thông qua 5 mô hình toán học giải tích chặt chẽ:

  1. Mô hình Bài toán Luồng Cực đại Đa hàng hóa Đa chi phí (MFP): Hàm mục tiêu tối đa hóa tổng giá trị luồng quy đổi: $$\max f_v = \sum_{i=1}^r \sum_{j=1}^{k_i} \sum_{p \in P_{ij}} cf_{ij}(p)$$ Thỏa mãn các ràng buộc chia sẻ năng lực thông hành thực tế tại cạnh và đỉnh: $$\sum_{i=1}^r \sum_{p \in P_{ie}} cf_{ij}(p) \le z_e(e) \cdot c_e(e), \quad \forall e \in E$$ $$\sum_{i=1}^r \sum_{p \in P_{iv}} cf_{ij}(p) \le z_v(v) \cdot c_v(v), \quad \forall v \in V$$ $$cf_{ij}(p) \ge 0, \quad \forall p \in P_{ij}, , \forall j=1,\dots,k_i, , \forall i=1,\dots,r$$ Trong đó, $z_e(e) \in (0, 1]$ và $z_v(v) \in (0, 1]$ là tỷ lệ thông hành thực tế của cạnh $e$ và đỉnh $v$.

  2. Mô hình Luồng Cực đại Đồng thời Đa hàng hóa Đa chi phí (CMFP): Thiết lập hệ số cực đại đồng thời $\lambda$ nhằm tối đa hóa tỷ lệ đáp ứng nhu cầu vận chuyển $d_{ij}$ của tất cả các cặp nguồn - đích: $$\max \lambda$$ Thỏa mãn điều kiện cân bằng luồng theo nhu cầu: $$\sum_{p \in P_{ij}} cf_{ij}(p) \ge \lambda \cdot d_{ij}, \quad \forall j=1,\dots,k_i, , \forall i=1,\dots,r$$ cùng các ràng buộc năng lực thông hành trên cạnh và đỉnh.

  3. Mô hình Luồng Cực đại với Chi phí Giới hạn (LMFP): Bổ sung ràng buộc tổng chi phí lưu hành toàn mạng không vượt quá ngưỡng ngân sách trần $B$: $$B_f = \sum_{i=1}^r \sum_{j=1}^{k_i} \sum_{p \in P_{ij}} b_i(p) \cdot cf_{ij}(p) \le B$$

  4. Mô hình Luồng Cực đại Đồng thời với Chi phí Giới hạn (LCMFP): Tích hợp đồng thời mục tiêu tối đa hóa hệ số tỷ lệ $\lambda$ với ràng buộc trần chi phí $B_f \le B$.

  5. Mô hình Luồng Cực đại Đồng thời với Chi phí Cực tiểu (MCMFP): Tối ưu hóa đa mục tiêu: vừa tối đa hóa hệ số $\lambda$, vừa cực tiểu hóa hàm tổng chi phí $B_f$.

Luận án đã xây dựng bài toán đối ngẫu (Dual Problem) tương ứng cho từng lớp bài toán (ký hiệu lần lượt là DM, DC, DL, DLC), chứng minh Định lý Đối ngẫu yếu, Định lý Đối ngẫu mạnh và xác lập Mệnh đề tối ưu xấp xỉ: Với $x$ là phương án của bài toán gốc (P) và $y$ là phương án của bài toán đối ngẫu (D), nếu $\frac{g(y)}{z(x)} \le 1 + \epsilon$ thì $x$ là phương án tối ưu với tỷ lệ xấp xỉ $(1 - \epsilon)$.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp chặt chẽ ba trụ cột lý thuyết: Lý thuyết Đồ thị hỗn hợp mở rộng, Lý thuyết Quy hoạch tuyến tính đối ngẫu và Lý thuyết Thuật toán xấp xỉ tổ hợp. Điểm độc đáo mang tính cách mạng là sự phân rã đường đi và cấu trúc chi phí tuyến tính:

Chi phí lưu hành của một đơn vị hàng hóa loại $i$ quy đổi qua đường đi $p = v \to e_1 \to v_1 \to e_2 \to \dots \to e_h \to v_h \to e_{h+1} \to w$ được định nghĩa bằng hàm cộng hợp chính xác: $$b_i(p) = \sum_{j=1}^{h+1} be_i(e_j) + \sum_{j=1}^h bv_i(v_j, e_j, e_{j+1})$$

Trong đó:

  • $be_i(e_j)$ là chi phí chuyển một đơn vị hàng hóa loại $i$ qua cạnh $e_j$.
  • $bv_i(v_j, e_j, e_{j+1})$ là chi phí rẽ nhánh chuyển một đơn vị hàng hóa loại $i$ từ cạnh $e_j$ qua đỉnh $v_j$ sang cạnh $e_{j+1}$.

Điều kiện biên (boundary conditions) được xác định tường minh: Mạng không tồn tại chu trình có tổng chi phí âm, khả năng thông hành và tỷ lệ thông hành luôn dương ($c_e > 0, c_v > 0, z_e \in (0,1], z_v \in (0,1]$), và tính bảo toàn luồng tại tất cả các đỉnh trung gian được duy trì nghiêm ngặt.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Nghiên cứu tuân thủ thế giới quan thực chứng (positivism) với phương pháp tiếp cận định lượng tối ưu hóa tổ hợp (combinatorial quantitative optimization). Thiết kế nghiên cứu đa tầng (multi-level design) kết nối liền mạch từ mô hình toán học giải tích trừu tượng $\to$ biến đổi đối ngẫu quy hoạch tuyến tính $\to$ thiết kế thuật toán xấp xỉ $\to$ cài đặt phần mềm thực nghiệm trên dữ liệu không gian giao thông đô thị thực tế.

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu được thực hiện qua 4 pha nghiêm ngặt:

  • Pha 1 - Thiết lập mô hình toán học: Định nghĩa cấu trúc mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và chuyển hóa các ràng buộc vật lý (dung lượng nút, dung lượng cạnh, tỷ lệ suy giảm năng lực, chi phí rẽ, ngân sách) thành hệ phương trình và bất phương trình tuyến tính chuẩn tắc.
  • Pha 2 - Phân tích đối ngẫu và chứng minh toán học: Xây dựng bài toán đối ngẫu dạng chính tắc, sử dụng biến đối ngẫu đóng vai trò như các hàm chiều dài/chi phí ảo trên cạnh và đỉnh, chứng minh tính đúng đắn và chặn trên sai số $\epsilon$ của giải thuật.
  • Pha 3 - Thiết kế thuật toán xấp xỉ: Phát triển hệ thống 5 thuật toán chính:
    1. Thuật toán MFMM (Maximal Flow on Multicost Multi-commodity Extended Mixed Network): Khởi tạo luồng bằng 0, lặp cập nhật hàm độ dài cạnh/đỉnh dựa trên luồng hiện hành, tìm đường đi ngắn nhất đa chi phí bằng giải thuật cải biên Dijkstra, tăng luồng và cập nhật biến đối ngẫu cho đến khi đạt tỷ lệ $(1 - \epsilon)$.
    2. Thuật toán CMF (Maximal Concurrent Flow): Tối ưu hóa phân bổ luồng đồng thời theo nhu cầu $d_{ij}$ qua từng pha chia tỷ lệ.
    3. Thuật toán LMF (Maximal Flow with Limited Cost): Tích hợp nhân tử Lagrange cho ràng buộc chi phí trần $B$.
    4. Thuật toán LCMF (Maximal Concurrent Flow with Limited Cost): Điều phối luồng đồng thời dưới chặn chi phí nghiêm ngặt.
    5. Thuật toán MCMF (Maximal Concurrent Flow with Minimal Cost): Tìm nghiệm luồng đồng thời đạt chi phí cực tiểu toàn cục.
  • Pha 4 - Thực nghiệm và kiểm chuẩn: Cài đặt toàn bộ thuật toán bằng ngôn ngữ lập trình C++ trên cấu trúc dữ liệu danh sách kề mở rộng, kiểm tra tính bảo toàn luồng và đánh giá hiệu năng trên mạng lưới giao thông thành phố Đà Nẵng.

Data và phân tích

Dữ liệu đầu vào thực nghiệm được xây dựng chi tiết từ khảo sát giao thông thực địa tại Đà Nẵng và chuẩn hóa theo tiêu chuẩn thiết kế đường ô tô TCVN 4054-2005:

  • Phân loại hàng hóa/phương tiện và hệ số quy đổi ($q$):

    • Loại 1: Motor car ($q = 1$) - Hàng hóa chuẩn.
    • Loại 2: Light truck ($q = 2$) - Chiếm dụng dung lượng gấp 2 lần xe chuẩn.
    • Loại 3: Heavy truck ($q = 3$) - Chiếm dụng dung lượng gấp 3 lần xe chuẩn.
    • Loại 4: Phân lớp vận tải chuyên dụng đa phương thức.

  • Năng lực thông hành và chi phí mạng thử nghiệm mẫu (minh họa kiểm chứng):

    • Năng lực thông hành đỉnh ($c_v$): $c_v(s) = 70$, $c_v(b) = 50$, $c_v(c) = 50$, $c_v(t) = 70$.
    • Năng lực thông hành cạnh ($c_e$): $c_e(s,b) = 50$ (có hướng), $c_e(s,c) = 50$ (có hướng), $c_e(b,c) = 70$ (vô hướng hai chiều), $c_e(c,b) = 70$ (vô hướng hai chiều), $c_e(b,t) = 50$ (có hướng), $c_e(c,t) = 50$ (có hướng).
    • Chi phí cạnh ($be$): $be(s,b) = 4$, $be(s,c) = 4$, $be(b,c) = 4$, $be(c,b) = 3$, $be(b,t) = 3$, $be(c,t) = 4$.
    • Chi phí rẽ nhánh tại đỉnh ($bv$): $bv(b, (s,b), (b,c)) = 4$, $bv(b, (s,b), (b,t)) = 5$, $bv(b, (c,b), (b,t)) = 4$, $bv(c, (s,c), (c,b)) = 5$, $bv(c, (s,c), (c,t)) = 5$, $bv(c, (b,c), (c,t)) = 3$.

  • Tập các cặp nguồn - đích thực nghiệm tại Đà Nẵng: Bao gồm 8 cặp O-D trọng điểm: $(1,4)$, $(1,5)$, $(1,9)$ cho hàng hóa loại 1; $(12,4)$, $(12,5)$, $(12,9)$ cho hàng hóa loại 2; $(12,16)$ cho hàng hóa loại 3; và $(13,16)$ cho hàng hóa loại 4.

Phát hiện đột phá và implications

Những phát hiện then chốt

Phát hiện 1 - Sai số tích lũy nghiêm trọng của mô hình đơn chi phí: Trong mạng hỗn hợp mở rộng đơn chi phí truyền thống, xét đường đi $p = s \to b \to c \to t$, chi phí xe con ($q=1$) là $b(p) = be(s,b) + bv(b, (s,b), (b,c)) + be(b,c) + bv(c, (b,c), (c,t)) + be(c,t) = 4 + 4 + 4 + 3 + 4 = 19$ (hoặc 20 tùy tuyến). Khi đó, chi phí xe tải nhẹ ($q=2$) bị áp đặt cứng nhắc là $2 \times 20 = 40$, và xe tải nặng ($q=3$) là $60$. Luận án chứng minh rằng trong thực tế, chi phí xe tải nặng chịu hệ số cản rẽ nhánh $bv_3(b, (s,b), (b,c))$ cao hơn nhiều so với tỷ lệ $3 \times$, khiến mô hình đơn chi phí phân bổ sai lệch lưu lượng thực tế, gây nghẽn nghiêm trọng tại các nút giao hẹp.

Phát hiện 2 - Cơ chế chia sẻ dung lượng trên cạnh vô hướng hai chiều: Thực nghiệm thuật toán MFMM chỉ ra rằng các dòng phương tiện ngược chiều trên các đoạn đường hai chiều (cạnh vô hướng như $(b,c)$ và $(c,b)$) tự động điều tiết và chia sẻ dung lượng thông hành $c_e(b,c) = 70$ theo nguyên lý cân bằng động, triệt tiêu hiện tượng thắt cổ chai mà các thuật toán luồng trên đồ thị có hướng thuần túy không xử lý được.

Phát hiện 3 - Đảm bảo tỷ lệ đáp ứng đồng thời thông qua CMF: Thuật toán CMF giải quyết triệt để tình trạng "độc chiếm dung lượng" của các cặp O-D gần nhau. Khi phân luồng cho 8 cặp O-D tại Đà Nẵng, CMF nâng cao hệ số $\lambda$ đồng đều, đảm bảo phương tiện từ các vị trí xa như đỉnh 12, 13 đến đỉnh 16 vẫn đạt tỷ lệ đáp ứng nhu cầu tương đương với các tuyến ngắn $(1,4)$, $(1,5)$.

Phát hiện 4 - Hiệu quả kiểm soát chi phí của LMF và LCMF: Khi thiết lập ngưỡng ngân sách giới hạn $B$, thuật toán LMF và LCMF chủ động loại bỏ các đường đi vòng có chi phí rẽ nhánh cao, tái định tuyến dòng phương tiện vào các hành lang vận tải chính có năng lực thông hành lớn, duy trì tổng chi phí $B_f \le B$ mà vẫn bảo toàn tối đa hóa lưu lượng thông qua.

Phát hiện 5 - Tối ưu hóa kép của thuật toán MCMF: Thuật toán MCMF chứng minh tính ưu việt vượt trội khi đồng thời tìm được nghiệm có hệ số đáp ứng nhu cầu $\lambda$ cực đại và tổng chi phí vận hành $B_f$ đạt mức cực tiểu toàn cục, cung cấp lời giải hoàn hảo cho bài toán điều độ giao thông xanh và tiết kiệm năng lượng.

Implications đa chiều

  • Ý nghĩa Lý thuyết (Theoretical Implications): Đặt nền móng hoàn chỉnh cho lý thuyết luồng đa hàng hóa đa chi phí tuyến tính trên mạng hỗn hợp mở rộng; giải quyết trọn vẹn bài toán tích hợp đồng thời chi phí nút, chi phí cạnh, cạnh hai chiều và đa chi phí độc lập vào khung phân tích quy hoạch tuyến tính đối ngẫu.
  • Ý nghĩa Phương pháp luận (Methodological Innovations): Cung cấp khung thiết kế thuật toán xấp xỉ $(1 - \epsilon)$ với thời gian chạy đa thức, có khả năng mở rộng và áp dụng trực tiếp cho các lớp bài toán tối ưu tổ hợp phức tạp khác như định tuyến mạng viễn thông 5G/6G, mạng lưới cấp điện thông minh (Smart Grid) và chuỗi cung ứng cứu trợ khẩn cấp.
  • Ý nghĩa Thực tiễn ứng dụng (Practical Applications): Cung cấp công cụ phần mềm (C++) phục vụ trực tiếp cho các trung tâm điều hành giao thông đô thị thông minh (Intelligent Transportation Systems - ITS), giúp phân luồng động, tổ chức giao thông một chiều/hai chiều linh hoạt và điều chỉnh chu kỳ đèn tín hiệu tại các nút giao trọng điểm.
  • Khuyến nghị Chính sách (Policy Recommendations): Cung cấp luận cứ khoa học chuẩn xác để Sở Giao thông Vận tải và UBND thành phố Đà Nẵng ban hành các quy định cấm đường theo tải trọng, tối ưu hóa biểu giá thu phí đường bộ điện tử (ETC), và quy hoạch mở rộng các nút giao thông có chi phí rẽ nhánh cao.

Limitations và Future Research

Mặc dù đạt được những đột phá lý thuyết và thực tiễn quan trọng, luận án thẳng thắn chỉ ra các giới hạn nghiên cứu:

  • Giới hạn 1 - Giả định luồng tĩnh (Static Network Flow): Mô hình hiện tại xem xét khả năng thông hành $c_e, c_v$ và chi phí $be, bv$ là các giá trị tĩnh không phụ thuộc vào thời gian trong một khung phân tích xác định.
  • Giới hạn 2 - Hàm chi phí tuyến tính: Chi phí trên các cung và đỉnh được giả định là tuyến tính, chưa mô hình hóa hàm chi phí phi tuyến theo hàm trễ BPR (Bureau of Public Roads) khi mạng đạt trạng thái bão hòa tắc nghẽn.
  • Giới hạn 3 - Nhu cầu xác định (Deterministic Demands): Nhu cầu vận chuyển $d_{ij}$ được giả định biết trước, chưa tích hợp yếu tố biến động ngẫu nhiên theo thời gian thực (stochastic demands).

Chương trình nghiên cứu tương lai (Future Research Agenda) bao gồm 5 định hướng cụ thể:

  1. Phát triển mô hình luồng đa hàng hóa đa chi phí trên mạng động phụ thuộc thời gian (Time-Expanded Dynamic Networks).
  2. Xây dựng thuật toán giải cho bài toán với hàm chi phí phi tuyến lồi (Convex Non-linear Cost Functions) phản ánh chính xác hiệu ứng tắc nghẽn giao thông.
  3. Ứng dụng kỹ thuật tối ưu hóa ngẫu nhiên (Stochastic Optimization) và lý thuyết trò chơi (Game Theory - Cân bằng Wardrop / Nash) trong phân luồng phương tiện tự hành (Autonomous Vehicles).
  4. Tối ưu hóa tính toán song song quy mô lớn trên nền tảng GPU và điện toán phân tán để xử lý mạng lưới giao thông quốc gia hàng triệu đỉnh.
  5. Tích hợp chỉ số phát thải carbon ($CO_2$, $NO_x$) vào hàm chi phí đa mục tiêu phục vụ quy hoạch giao thông xanh và bền vững.

Tác động và ảnh hưởng

Công trình nghiên cứu tạo ra tác động sâu rộng trên nhiều bình diện:

  • Tác động Học thuật: Mở ra một nhánh nghiên cứu chuyên sâu về tối ưu hóa mạng mở rộng đa chi phí trong cộng đồng nghiên cứu Vận trù học (Operations Research) và Khoa học Máy tính tại Việt Nam và quốc tế; dự kiến tạo nguồn trích dẫn học thuật quan trọng trong lĩnh vực thuật toán mạng.
  • Chuyển đổi Ngành Giao thông & Logistics: Các doanh nghiệp vận tải và logistics có thể trực tiếp ứng dụng thuật toán để tối ưu hóa lộ trình xe tải đa tải trọng, cắt giảm từ 12% đến 18% chi phí nhiên liệu và khấu hao xe thông qua việc tránh các nút giao có chi phí rẽ nhánh cao.
  • Định hình Chính sách Công: Hỗ trợ cơ quan quản lý đô thị Đà Nẵng thiết kế chính sách phân luồng giao thông khoa học, giảm thiểu ùn tắc cục bộ tại các trục đường huyết mạch như cầu Rồng, cầu Sông Hàn và các nút giao trọng điểm phía Tây thành phố.
  • Lợi ích Xã hội & Môi trường: Việc giảm thiểu thời gian dừng chờ và xung đột rẽ nhánh tại các nút giao giúp cắt giảm đáng kể lượng phát thải khí nhà kính và ô nhiễm tiếng ồn đô thị.

Đối tượng hưởng lợi

  • Nghiên cứu sinh và Giảng viên ngành KHMT & Vận trù học: Tiếp cận mô hình toán học giải tích chuẩn mực, phương pháp đối ngẫu quy hoạch tuyến tính và kỹ thuật chứng minh thuật toán xấp xỉ tiên tiến.
  • Chuyên gia R&D và Kỹ sư Phần mềm Giao thông: Khai thác mã nguồn và cấu trúc thuật toán C++ (MFMM, CMF, LMF, LCMF, MCMF) để tích hợp vào các hệ sinh thái phần mềm ITS, GIS và định vị điều hướng thông minh.
  • Các Nhà Quản lý và Quy hoạch Đô thị: Sở hữu công cụ mô phỏng định lượng mạnh mẽ để đánh giá tác động trước khi quyết định đầu tư cải tạo hạ tầng nút giao hoặc thay đổi phương án tổ chức luồng giao thông.
  • Doanh nghiệp Vận tải & Logistics: Nâng cao hiệu suất điều phối đội xe đa chủng loại, tối ưu hóa lợi nhuận và giảm thiểu chi phí vận hành tổng thể.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và mở rộng lý thuyết nào?
Trả lời: Đóng góp lý thuyết độc đáo nhất là việc thiết lập mô hình toán học và hệ thống thuật toán xấp xỉ $(1 - \epsilon)$ cho bài toán luồng đa hàng hóa đa chi phí trên mạng hỗn hợp mở rộng, giải quyết đồng thời chi phí rẽ nhánh tại nút $bv_i(v, e, e')$, liên kết vô hướng chia sẻ dung lượng và cấu trúc đa chi phí độc lập cho từng loại hàng hóa. Công trình mở rộng trực tiếp Lý thuyết Luồng cực đại của Ford và Fulkerson (1956), Lý thuyết Đối ngẫu trong Quy hoạch Tuyến tính và mô hình Mạng mở rộng của Trần Quốc Chiến (2010, 2018) từ đơn chi phí sang đa chi phí phi quy đổi.

2. Điểm đổi mới phương pháp luận so với các công trình quốc tế tiền nhiệm?
Trả lời: So với Noguera & Leirens (2010) (chỉ xét mạng có hướng đơn chi phí không có độ trễ nút) và Wright et al. (2017) (chỉ tối ưu hóa một nút giao đơn lẻ), luận án đã thiết lập khung đối ngẫu hoàn chỉnh cho toàn mạng hỗn hợp mở rộng quy mô lớn, tích hợp hàm chiều dài ảo trên cả cạnh $l(e)$ và đỉnh $w(v)$, kết hợp biến đối ngẫu ngân sách $\varphi$, cho phép giải quyết đồng thời 5 bài toán luồng tối ưu trong thời gian đa thức với sai số chặn trên $\epsilon$.

3. Phát hiện bất ngờ nhất từ thực nghiệm dữ liệu là gì?
Trả lời: Phát hiện bất ngờ nhất là sự sai lệch lớn của phương pháp quy đổi tải trọng truyền thống ($q$). Trong khi các mô hình đơn chi phí giả định chi phí xe tải tăng tuyến tính theo $q \times b(p)$, thực nghiệm trên mạng Đà Nẵng chỉ ra rằng chi phí rẽ nhánh thực tế tại các nút giao có thể khiến tổng chi phí của xe tải nặng tăng phi tuyến gấp nhiều lần, dẫn đến việc phân luồng theo mô hình cũ gây tắc nghẽn trầm trọng tại các nút giao trung tâm.

4. Quy trình tái lập (Replication Protocol) có được cung cấp đầy đủ không?
Trả lời: Luận án cung cấp quy trình tái lập hoàn chỉnh 100%: mã giả chi tiết của 5 thuật toán, mô hình toán học giải tích tường minh, cấu trúc dữ liệu C++, cùng toàn bộ 6 phụ lục dữ liệu thực nghiệm bao gồm: Khả năng thông hành thực tế của đỉnh ($c_v$), Hệ số quy đổi ($q$), Các cặp nguồn - đích, Khả năng thông hành và chi phí cạnh ($c_e, be$), Chi phí rẽ nhánh ($bv$) và Lượng hàng cần chuyển ($d_{ij}$).

5. Chương trình nghiên cứu 10 năm tiếp theo được định hình ra sao?
Trả lời: Chương trình 10 năm tập trung chuyển đổi từ mô hình tĩnh sang mô hình luồng động ngẫu nhiên theo thời gian thực (Real-time Dynamic Stochastic Multi-cost Flows), tích hợp trí tuệ nhân tạo (Deep Reinforcement Learning) trong điều khiển đèn tín hiệu thích ứng, và mở rộng quy mô giải thuật song song trên GPU phục vụ điều phối giao thông thông minh cấp quốc gia.

Kết luận

Luận án tiến sĩ của tác giả Hồ Văn Hùng đã đạt được 6 đóng góp học thuật cốt lõi:

  1. Xây dựng hoàn chỉnh mô hình toán học Mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và Luồng đa hàng hóa đa chi phí tuyến tính.
  2. Đề xuất mô hình và thuật toán xấp xỉ MFMM giải quyết bài toán luồng cực đại đa hàng hóa đa chi phí.
  3. Đề xuất mô hình và thuật toán CMF giải quyết bài toán luồng cực đại đồng thời đa hàng hóa đa chi phí.
  4. Đề xuất mô hình và thuật toán LMF giải quyết bài toán luồng cực đại với chi phí giới hạn.
  5. Đề xuất mô hình và thuật toán LCMF giải quyết bài toán luồng cực đại đồng thời với chi phí giới hạn.
  6. Đề xuất mô hình và thuật toán MCMF giải quyết bài toán luồng cực đại đồng thời với chi phí cực tiểu.

Công trình tạo nên bước tiến quan trọng trong chuyên ngành Khoa học máy tính và Tối ưu hóa tổ hợp, mở ra ba hướng nghiên cứu mới về mạng động, tối ưu hóa phi tuyến và điều khiển giao thông đô thị thông minh, khẳng định giá trị khoa học vững chắc và khả năng ứng dụng thực tiễn cao tại Việt Nam và trên thế giới.