Bài toán phân luồng giao thông và ứng dụng

BÀI TOÁN PHÂN LUỒNG GIAO THÔNG VÀ ỨNG DỤNG<br /> Trần Quốc Chiến1Hồ Văn Hùng2<br /> Tóm tắt: Kết quả của công trình bao gồm: (1) Xây dựng mô hình mạng giao thông mở rộng, trong<br /> đó chi phí tại một nút không giống nhau với mọi đường đi qua nút đó, mà còn phụ thuộc vào tuyến<br /> đi đến và tuyến đi khỏi đỉnh đó, thậm chí có hướng còn bị cấm. (2) Xây dựng mô hình bài toán<br /> luồng cực đại đồng thời chi phí giới hạn trên mạng giao thông mở rộng và phát triển thuật toán<br /> xấp xỉ giải bài toán này trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính và thuật toán tìm<br /> đường đi ngắn nhất trên đồ thị mở rộng. (3) Xây dựng mô hình bài toán phân luồng tối ưu trên<br /> mạng giao thông mở rộng và phát triển thuật toán hữu hiệu tìm luồng tối ưu. Các thuật toán được<br /> cài đặt bằng ngôn ngữ Java với cơ sở dữ liệu mạng giao thông trung tâm thành phố Đà Nẵng<br /> trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.<br /> Từ khóa: Đồ thị, Mạng, Luồng đa phương tiện, Xấp xỉ, Tối ưu.<br /> 1 . Mở đầu<br /> Đồ 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,<br /> công nghệ thông tin, kinh tế,…. Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các cạnh,<br /> các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và<br /> các đỉnh trên đường đi đó. Tuy nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không<br /> giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh<br /> đó. Ví dụ thời gian đi qua ngã tư trên mạng giao thông phụ thuộc vào hướng di chuyển của phương<br /> tiện giao thông: rẽ phải, đi thẳng hay rẽ trái, thậm chí có hướng bị cấm. Vì vậy cần xây dựng một<br /> mô hình đồ thị mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả<br /> hơn.<br /> Báo cáo trình bày kết quả khảo sát hạ tầng kỹ thuật mạng lưới giao thông khu vực trung tâm Đà<br /> Nẵng, nhu cầu đi lại giữa các nút giao thông trong phạm vi đề tài NCKH cấp thành phố “Bài toán<br /> mạng giao thông và ứng dụng quản lý quy hoạch phân luồng giao thông ở thành phố Đà Nẵng”<br /> do Trường Đại học Sư phạm - ĐHĐN, Trường Đại học Bách khoa – ĐHĐN và Sở Giao thông Vận<br /> tải TP. Đà Nẵng phối hợp thực hiện.<br /> Tiếp theo, báo cáo xây dựng mô hình hai bài toán phân luồng giao thông đa phương<br /> tiện tuyến tính trên mạng giao thông mở rộng:Bài toán luồng cực đại đồng thời chi phí giới hạn và<br /> bài toán phân luồng tối ưu. Các thuật toán hữu hiệu phân luồng tối ưu được phát triển và cài đặt<br /> bằng ngôn ngữ Java với cơ sở dữ liệu mạng giao thông trung tâm thành phố Đà Nẵng trong hệ<br /> quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.<br /> 2. Mạng giao thông Trung tâm Đà Nẵng<br /> <br /> 1<br /> 2<br /> <br /> . PGS.TS. Khoa Tin học, trường ĐHSP Đà Nẵng<br /> . ThS. Giám đốc Trung tâm TH-NN, trường ĐHQN<br /> <br /> Mạng lưới giao thông Trung tâm Đà Nẵng (xem bản đồ khu vực khảo sát) có 120 nút và 209 đoạn<br /> tuyến trên 49 tuyến phố và nhu cầu đi lại của 999 cặp nút nguồn và nút đích.<br /> <br /> Hình 1. Bản đồ khu vực khảo sát<br /> Mạng lưới giao thông trên được mô hình hóa bằng đồ thị mạng hỗn hợp mở rộng sau:<br /> <br /> Hình 2. Đồ thị mạng giao thông Trung tâm Đà Nẵng<br /> 3. Khả năng thông hành và chi phí thời gian qua đoạn tuyến<br /> Hệ thống các thông số biểu diễn khả năng thông hành (xe con quy đổi) và chi phí thời gian (phút)<br /> trên các đoạn tuyến như sau:<br /> Bảng 1. Hệ thống các thông số biểu diễn khả năng thông hành và chi phí thời gian trên các cung<br /> đoạn tuyến lưu trong bảng SUBLINE<br /> <br /> Mã số<br /> <br /> Nút đầu Nút cuối Khả năng thông hành Thời gian Có hướng<br /> <br /> 00001a<br /> <br /> 1<br /> <br /> 2<br /> <br /> 4320<br /> <br /> 2.82<br /> <br /> 1<br /> <br /> 00001b<br /> <br /> 2<br /> <br /> 1<br /> <br /> 4320<br /> <br /> 2.82<br /> <br /> 1<br /> <br /> 00002a<br /> <br /> 2<br /> <br /> 3<br /> <br /> 4320<br /> <br /> 1.96<br /> <br /> 1<br /> <br /> 00002b<br /> <br /> 3<br /> <br /> 2<br /> <br /> 4320<br /> <br /> 1.96<br /> <br /> 1<br /> <br /> 00003<br /> <br /> 4<br /> <br /> 5<br /> <br /> 2880<br /> <br /> 2.63<br /> <br /> 0<br /> <br /> 00004<br /> <br /> 6<br /> <br /> 7<br /> <br /> 2880<br /> <br /> 0.34<br /> <br /> 0<br /> <br /> 00005<br /> <br /> 8<br /> <br /> 9<br /> <br /> 3703<br /> <br /> 0.95<br /> <br /> 0<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> 00208<br /> <br /> 80<br /> <br /> 81<br /> <br /> 4320<br /> <br /> 0.33<br /> <br /> 0<br /> <br /> 00209<br /> <br /> 81<br /> <br /> 82<br /> <br /> 4320<br /> <br /> 0.34<br /> <br /> 0<br /> <br /> 00210<br /> <br /> 15<br /> <br /> 3<br /> <br /> 4320<br /> <br /> 2.50<br /> <br /> 1<br /> <br /> 00211<br /> <br /> 117<br /> <br /> 119<br /> <br /> 4320<br /> <br /> 1.00<br /> <br /> 1<br /> <br /> 4. Khả năng thông hành nút<br /> Hệ thống các thông số biểu diễn khả năng thông hành và chi phí thời gian qua các nút giao thông<br /> lưu trong bảng NODE.<br /> 5. Chi phí thời gian qua nút<br /> Hệ thống các thông số biểu diễn chi phí thời gian qua các nút giao thông như sau:<br /> Bảng 2. Hệ thống các thông số biểu diễn chi phí thời gian qua các nút giao thông lưu trong bảng<br /> NODESUBTIME.<br /> Node<br /> chính<br /> <br /> Node<br /> trước<br /> <br /> Node<br /> sau<br /> <br /> time<br /> giây<br /> <br /> 1<br /> <br /> 2<br /> <br /> 35<br /> <br /> 11<br /> <br /> 2<br /> <br /> 1<br /> <br /> 3<br /> <br /> 8<br /> <br /> 3<br /> <br /> 4<br /> <br /> 10,2<br /> <br /> 3<br /> <br /> 2<br /> <br /> 5<br /> <br /> 5,2<br /> <br /> 4<br /> <br /> 2<br /> <br /> 5<br /> <br /> 8,5<br /> <br /> bV<br /> phút<br /> <br /> Node<br /> trước<br /> <br /> Node<br /> sau<br /> <br /> time<br /> giây<br /> <br /> 2<br /> <br /> 6,2<br /> <br /> 1<br /> <br /> 4<br /> <br /> 4<br /> <br /> 35<br /> <br /> 15<br /> 2<br /> <br /> bV<br /> phút<br /> <br /> Node<br /> trước<br /> <br /> Node<br /> sau<br /> <br /> time<br /> giây<br /> <br /> 6,7<br /> <br /> 3<br /> <br /> 1<br /> <br /> 7,8<br /> <br /> 1<br /> <br /> 10,3<br /> <br /> 4<br /> <br /> 3<br /> <br /> 5,9<br /> <br /> 2<br /> <br /> 13 ,<br /> 1<br /> <br /> 6<br /> <br /> 6,2<br /> <br /> 5<br /> <br /> 2<br /> <br /> 5,9<br /> <br /> bV<br /> phút<br /> <br /> 5<br /> <br /> 5<br /> <br /> 6<br /> <br /> 7,5<br /> <br /> 6<br /> <br /> 3<br /> <br /> 4<br /> <br /> 6,6<br /> <br /> 3<br /> <br /> 6,2<br /> <br /> 6<br /> <br /> 15<br /> <br /> 7,1<br /> <br /> 4<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> 119<br /> <br /> 110<br /> <br /> 118<br /> <br /> 7,2<br /> <br /> 110<br /> <br /> 120<br /> <br /> 16 ,<br /> 9<br /> <br /> 117<br /> <br /> 120<br /> <br /> 8,5<br /> <br /> 120<br /> <br /> 118<br /> <br /> 10<br /> <br /> 119<br /> <br /> 106<br /> <br /> 15 ,<br /> 8<br /> <br /> 120<br /> <br /> …<br /> <br /> 2<br /> <br /> …<br /> <br /> …<br /> <br /> 5<br /> <br /> 5,2<br /> <br /> 15<br /> <br /> 4<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> 6. Nhu cầu đi lại<br /> Hệ thống các nhu cầu đi lại cho bởi 999 cặp đỉnh nguồn nguồn đích và số xe lưu hành trong bảng<br /> DEMAND.<br /> 7. Mô hình Mạng giao thông mở rộng<br /> Cho đồ thị hỗn hợp G=(V, E) với tập đỉnh V và tập cạnh E. Các cạnh có thể có hướng hoặc vô<br /> hướng. Có nhiều loại phương tiện giao thông lưu hành trên mạng. Những cạnh vô hướng biểu diễn<br /> tuyến hai chiều, trong đó các phương tiện trên cùng tuyến nhưng ngược hướng lưu hành chia sẻ<br /> khả năng thông hành của tuyến. Trên mạng cho các hàm sau.<br /> 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.<br /> Hàm khả năng thông hành đỉnh cV:V→R*, với cV(u) là khả năng thông hành đỉnh u ∈ V.<br /> 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ị phương tiện qua<br /> 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.<br /> Với mỗi đỉnh v∈V, ký hiệu Ev là tập các cạnh liên thuộc đỉnh v.<br /> Hàm chi phí đỉnhbV: V×Ev×Ev→R*, với bV(u,e, e’) là chi phí phải trả để chuyển một đơn vị phương<br /> tiện qua đỉnh u từ tuyến e sang tuyến e’.<br /> Bộ (V, E,<br /> <br /> c c b b<br /> E, V, E, V) gọi là mạng giao thông mở rộng.<br /> <br /> Cho p là đường đi từ đỉnh u đến đỉnh v qua các cạnh ei, i = 1, …, h+1, và các đỉnh ui, i = 1, …, h,<br /> như sau p = [u, e1, u1, e2, u2, …, eh, uh, eh+1, v]<br /> Định nghĩa chi phí vận chuyển một đơn vị phương tiện qua đường đi p, ký hiệu b(p) , theo công<br /> thức sau :<br /> h+1<br /> <br /> h<br /> <br /> b(p) = ∑bE(ei ) + ∑bV (ui,ei,ei+1)<br /> i=1<br /> <br /> (1)<br /> <br /> i=1<br /> <br /> Cho mạng giao thông mở rộng G=(V, E,<br /> <br /> c c b b<br /> E, V, E, V).<br /> <br />