Thuật toán tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí giới hạn trên mạng giao thông mở rộng với hệ số đơn điều tiết đường hai chiều

Algorithm to Find Maximum Concurent Multicommodity Linear Flow with Limited Cost on Extended Traffic Network with Single Regulating Coeffitient on Two-Side Lines
Nơi đăng: The International Journal of Computer Networks & Communications, Số: V 9 N2, Trang: 57-67, Năm: 2017, Loại bài viết: Bài báo, Quốc gia: Quốc tế.

Tóm tắt:

Đồ thị và mạng mở rộng 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ế, ….[1]. Thuật toán tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí giới hạn trên mạng giao thông mở rộng đã được trình bày trong các công trình [2, 3, 4, 5]. Tuy nhiên, trong các thuật toán trước, khả năng thông qua của các tuyến đường hai chiều được chia sẻ 100% cho cả hai hướng. Bài báo này sẽ nghiên cứu trường hợp tổng quát và phù hợp thực tế hơn, trong đó các luồng phương tiện sẽ bị giới hạn khả năng sử dụng đường hai chiều bằng tham số gọi là hệ số điều tiết. Thuật toán được trình bày tựa theo ngôn ngữ lập trình C.Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác

Abstract:

Graphs and extended networks are is powerful mathematical tools applied in many fields as transportation, communication, informatics, economy, …[1] Algorithms to find Maximum Concurent Multicommodity Flow with Limited Cost on extended traffic networks are introduced in the works [2, 3, 4, 5]. However, with those algorithms, capacities of two-sided lines are shared fully for two directions. This work studies the more general and practical case, where flows are limited to use two-sided lines with a single parameter called regulating coefficient. The algorithm is presented in the programming laguage C. The algorithm is coded in programming language Java with extended network database in database management system MySQL and offers exact results