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

BÀI TỐN PHÂN LUỒNG GIAO THƠNG VÀ ỨNG DỤNG Trần Quốc Chiến1Hồ Văn Hùng2 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 đĩ 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 đ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 tốn 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 tốn xấp xỉ giải bài tốn này trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính và thuật tốn tìm đường đi ngắn nhất trên đồ thị mở rộng. (3) Xây dựng mơ hình bài tốn phân luồng tối ưu trên mạng giao thơng mở rộng và phát triển thuật tốn hữu hiệu tìm luồng tối ưu. Các thuật tốn được 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 trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác. Từ khĩa: Đồ thị, Mạng, Luồng đa phương tiện, Xấp xỉ, Tối ưu. 1 . Mở đầu Đồ thị là cơng cụ tố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ế,. Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các cạnh, 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à các đỉnh trên đường đi đĩ. Tuy nhiên, trong nhiều bài tốn thực tế, 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 cạnh đi đến và cạnh đi khỏi đỉnh đĩ. 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 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 mơ hình đồ thị mở rộng để cĩ thể áp dụng mơ hình hĩa các bài tốn thực tế chính xác và hiệu quả hơn. 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 Đà 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 tốn 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” 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 tải TP. Đà Nẵng phối hợp thực hiện. Tiếp theo, báo cáo xây dựng mơ hình hai bài tốn phân luồng giao thơng đa phương tiện tuyến tính trên mạng giao thơng mở rộng:Bài tốn luồng cực đại đồng thời chi phí giới hạn và bài tốn phân luồng tối ưu. Các thuật tốn hữu hiệu phân luồng tối ưu được phát triển và 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 trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác. 2. Mạng giao thơng Trung tâm Đà Nẵng 1 . PGS.TS. Khoa Tin học, trường ĐHSP Đà Nẵng 2 . ThS. Giám đốc Trung tâm TH-NN, trường ĐHQN 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 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. Hình 1. Bản đồ khu vực khảo sát 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: Hình 2. Đồ thị mạng giao thơng Trung tâm Đà Nẵng 3. Khả năng thơng hành và chi phí thời gian qua đoạn tuyến 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) trên các đoạn tuyến như sau: 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 đoạn tuyến lưu trong bảng SUBLINE Mã số Nút đầu Nút cuối Khả năng thơng hành Thời gian Cĩ hướng 00001a 1 2 4320 2.82 1 00001b 2 1 4320 2.82 1 00002a 2 3 4320 1.96 1 00002b 3 2 4320 1.96 1 00003 4 5 2880 2.63 0 00004 6 7 2880 0.34 0 00005 8 9 3703 0.95 0 00208 80 81 4320 0.33 0 00209 81 82 4320 0.34 0 00210 15 3 4320 2.50 1 00211 117 119 4320 1.00 1 4. Khả năng thơng hành nút 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 lưu trong bảng NODE. 5. Chi phí thời gian qua nút 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: 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 NODESUBTIME. Node chính Node trước Node sau time giây bV phút Node trước Node sau time giây bV phút Node trước Node sau time giây bV phút 1 2 35 11 35 2 6 , 2 2 1 3 8 1 4 6,7 3 1 7 , 8 3 4 10,2 4 1 10,3 4 3 5 , 9 3 2 5 5,2 15 2 13 , 1 4 2 5 8,5 2 6 6,2 5 2 5 , 9 5 6 7,5 6 2 6,2 6 5 5 , 2 5 3 4 6,6 3 15 7,1 4 15 4 119 110 118 7,2 110 120 16 , 9 117 120 8,5 120 118 10 120 119 106 15 , 8 6. Nhu cầu đi lại 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 DEMAND. 7. Mơ hình Mạng giao thơng mở rộng 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ơ 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 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ẻ khả năng thơng hành của tuyến. Trên mạng 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(u) là khả năng thơng hành đỉnh u ∈ V. 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 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. Với mỗi đỉnh v∈V, ký hiệu Ev là tập các cạnh liên thuộc đỉnh v. 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 tiện qua đỉnh u từ tuyến e sang tuyến e’. Bộ (V, E, c E, c V, b E, b V) gọi là mạng giao thơng mở rộng. 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, như sau p = [u, e1, u1, e2, u2, , eh, uh, eh+1, v] Đị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 thức sau : h+1 h b(p) = ∑bE(ei ) + ∑bV (ui,ei,ei+1) (1) i=1 i=1 Cho mạng giao thơng mở rộng G=(V, E, c E, c V, b E, b V). Ký hiệu S là tập hợp tất cả các cặp nút nguồn-đích (i,j) trong G cĩ nhu cầu đi lại d(i,j) > 0. Ký hiệu P(i,j) là tập hợp tất cả các đường đi từ nút nguồn i đến nút đích j trong G, (i,j)∈S. Đặt P = P(i, j). (i, j)∈S Với mỗi đường đi p∈P(i,j), ký hiệu biến x(i,j,p) là luồng xe của nhu cầu d(i,j) đi trên đường đi p từ đỉnh nguồn i đến đỉnh đích j. Ký hiệu PE(i,j,e) là tập hợp các đường đi trong P(i,j) đi qua cạnh e, ∀e∈E. Ký hiệu PV(i,j,v) là tập hợp các đường đi trong P(i,j) đi qua đỉnh v, ∀v∈V. Mỗi tập F = { x(i,j,p) | (i,j)∈S , p∈P(i,j) } gọi là luồng trên mạng giao thơng mở rộng, nếu thỏa mãn các điều kiện về khả năng thơng hành sau: ∑ ∑x(i, j, p ) E , ∀e∈ E (i, j)∈S p∈PE (i, j,e) ∑ ∑x(i, j, p ) V , ∀v∈ V (i, j)∈S p∈PV (i, j,v) Luồng F = { x(i,j,p) | (i,j)∈S , p∈P(i,j) } gọi là phương án phân luồng nếu nĩ thỏa mãn các ràng buộc về nhu cầu đi lại của các cặp đỉnh nguồn đích sau ∑x(i, j, p) = d(i,j), ∀(i, j)∈S p∈P(i, j) Với mỗi phương án phân luồng F = { x(i,j,p) | (i,j)∈S , p∈P(i,j) } ta định nghĩa hàm mục tiêu t( F) biểu diễn tổng chi phí của F như sau t(F) = 8 . Bài tốn luồng cực đại đồng thời chi phí giới hạn Cho mạng giao thơng mở rộng G=(V, E, cE, cV, bE, bV) với tập cặp nút nguồn-đích S và nhu cầu đi lại d(i,j), ∀(i, j)∈S. Cho giới hạn chi phí B. Nhiệm vụ của bài tốn là tìm một số λ lớn nhất sao cho cĩ một luồng chuyển λ.d(i,j) đơn vị phương tiện từ nút i đến nút j qua luồng, ∀(i,j)∈S. Đồng thời, tổng chi phí của luồng khơng vượt quá B. Bài tốn phát biểu thành mơ hình qui hoạch tuyến tính như sau: Tìm phương án phân luồng F = { x(i,j,p) | (i,j)∈S , p∈P(i,j) } thỏa λ→ max ∑ ∑x(i, j, p ) E ), ∀e∈ E (i, j)∈S p∈PE (i, j,e) ∑ ∑x(i, j, p ) V , ∀v∈ V (i, j)∈S p∈PV (i, j,v) ∑x(i, j, p)≥λ.d(i,j), ∀(i, j)∈S p∈P(i, j) ∑ ∑b(p). x(i, j, p) ≤ B (i, j)∈S p∈P(i, j) x ≥0, λ ≥ 0 •Thuật tốn tìm luồng cực đại đồng thời chi phí giới hạn * Đầu vào: Mạng mở rộng G = (V, E, cE, cV, bE, bV) với tập cặp nút nguồn-đích S và nhu cầu đi lại d(i,j), ∀(i, j)∈S. (nhu cầu đi lại lưu trong bảng DEMAND gồm các bản ghi (sj, tj, dj), j=1,,k với nhu cầu dj từ đỉnh nguồn sj đến đỉnh đích tj, khả năng thơng hành nút cV lưu trong bảng NODES, khả năng thơng hành cạnh cEvà chi phí cạnh bE (tính bằng phút) lưu trong bảng SUBLINE, chi phí qua nút bV (tính bằng giây) lưu trong bảng NODESUBTIME). Chi phí giới hạn B. Hệ số xấp xỉ ω> 0. * Đầu ra: 1) Hệ số λ cực đại: λmax 2) Luồng thực tế {fej(a), fvj(u,e,e‘)| a∈E, (e,u,e‘)∈Bảng bV, j=1,...,k}. 3) Chi phí thực tế Bf≤ B. * Thủ tục: // Khởi tạo các giá trị ban đầu Đặt ε = ; δ = ; // n là số nút, m là số đoạn tuyến le(e) = δ/cE(e),∀e∈ E; lv(v) = δ/cV(v),∀v∈ V; ϕ = δ/ B; D = (m+n+1)δ; fej(a) = 0; ∀a∈E, fvj(u,e,e‘) = 0; ∀u∈V,∀(e,u,e‘)∈Bảng bv, j=1,...,k t= 1;//biến đếm giai đoạn Bex = 0;// Chi phí tạm tính while D < 1 do // mức giai đoạn { for j = 1 to k do // mức vịng lặp ứng với j { d’ = dj // lượng phương tiện cần chuyển từ sj đến tj while d’> 0 do // mức các bước trong giai đoạn { Gọi thủ tục tìm đường đi ngắn nhất tìm đường đi ngắn Tính f’ = min{d’, cE(e), cV(v) | e∈p, v∈p}; B’ = b(p)*f’; // b(p) tính theo cơng thức (1) if B’ > B {f’ = f’*B/B’; B’ = B}; // hiệu chỉnh luồng fej(a) = fej(a) +f’;∀a∈p fvj(u,e,e‘) = fvj(u,e,e‘) +f’; ∀(e,u,e‘)∈p // hiệu chỉnh các tham số khác d’ = d’− f’;ϕ =ϕ*(1+ε*B’/B) , le(e) = le(e)*(1+ε*f’/cE(e)); ∀e∈p lv(v) = lv(v)*(1+ε*f’/cV(v)); ∀v∈p D = D + ε*f’*length(p) ; Bex = Bex + B’; } } nhất p từ s j đến t j theo hàm length sau length ( p ) = = t = t + 1; } // hiệu chỉnh luồng thực tế cex = log1+ε c’ ; fej(a) = fej(a)/cex;∀a∈E, j=1,...,k fvj(u,e,e‘) = fvj(u,e,e‘)/cex; ∀u∈V,∀(e,u,e‘)∈Bảng bv, j=1,...,k Bf = Bex/cex;// chi phí thực tế λmax = Tỉ lệ lớn nhất 9 . Bài tốn phân luồng tối ưu Tổ hợp các mục trên ta cĩ thể phát biểu bài tốn phân luồng tối ưu như sau •Thuật tốn phân luồng tối ưu * Đầu vào: Mạng mở rộng G = (V, E, cE, cV, bE, bV). Trong đĩ, nhu cầu đi lại lưu trong bảng DEMAND gồm các bản ghi (sj, tj, dj), j=1,,k với nhu cầu dj từ đỉnh nguồn sj đến đỉnh đích tj, khả năng thơng hành nút cV lưu trong bảng NODES, khả năng thơng hành cạnh cEvà chi phí cạnh bE (tính bằng phút) lưu trong bảng SUBLINE, chi phí qua nút bV (tính bằng giây) lưu trong bảng NODESUBTIME. * Đầu ra: 1) Luồng tối ưu {fej(a), fvj(u,e,e‘)| a∈E, (e,u,e‘)∈Bảng bv, j=1,...,k}. (luồng qua đoạn tuyến fej(a) lưu trong bảng LINEASSIGN, luồng qua nút fvj(u,e,e‘) lưu trong bảng NODEASSIGN ). 2) Chi phí cực tiểu Bmin. * Các bước: // Khởi tạo các giá trị ban đầu Chọn hệ số xấp xỉ ω> 0; //Khởi tạo chi phí giới hạn B: B = 0; for j = 1 to k do { tìm đường đi ngắn nhất p từ sj đến tj theo hàm chi phí b(p) ; B = B + dj*b(p) ; } λmax = 0; λ0= -1; while (λmaxλ0) do { λ0 = λmax; Gọi chương trình tìm luồng cực đại chi phí giới hạn với tham số B và ω; if λmax< 1 { B = B /λmax } } //Hiệu chỉnh luồng tối ưu và chi phí cực tiểu if (λmax> 1) { fej(a) = fej(a) / λmax;∀a∈E, j=1,...,k fvj(u,e,e‘) = fvj(u,e,e‘) / λmax; ∀u∈V,∀(e,u,e‘)∈Bảng bv, j=1,...,k Bmin = Bf/λmax;// chi phí thực tế } if λmax< 1 { thơng báo: mạng đáp ứng 100*λmax % nhu cầu đi lại } 10 . Kết luận Cơng trình giới thiệu kết quả nghiên cứu khảo sát hạ tầng kỹ thuật mạng lưới giao thơng khu vực trung tâm Đà Nẵng, nhu cầu đi lại giữa các nút giao thơng, xây dựng mơ hình mạng giao thơng và phương án phân luồng giao thơng tối ưu. Các thuật tốn được cài lập trình bằng ngơn ngữ Java với cơ sở dữ liệu thực tế cài đặt trong hệ quản trị cơ sở dữ liệu MySQL. Chương trình chạy thử cho kết quả chính xác và tin cậy. TÀI LIỆU THAM KHẢO [1] Trần Quốc Chiến (2007), Giáo trình lý thuyết đồ thị và ứng dụng, Đại học Đà Nẵng. [2] Trần Quốc Chiến (2012), Thuật tốn tìm đường đi ngắn nhất trên đồ thị tổng quát, Hội nghị khoa học ĐHĐN. [3] Trần Quốc Chiến, Trần Thị Mỹ Dung (2011),“Ứng dụng thuật tốn tìm đường đi ngắn nhất tìm luồng cực đại đa hàng hĩa”, Tạp chí Khoa học & Cơng nghệ, Đại học Đà Nẵng, 3(44). [4] Trần Quốc Chiến (2012),“Ứng dụng thuật tốn tìm đường đi ngắn nhất đa nguồn đích tìm luồng cực đại đa hàng hĩa đồng thời”, Tạp chí Khoa học & Cơng nghệ, Đại học Đà nẵng, 4(53). [5] Trần Quốc Chiến (2012),“Ứng dụng thuật tốn tìm đường đi ngắn nhất đa nguồn đích tìm luồng cực đại đa hàng hĩa đồng thời chi phí cực tiểu”, Tạp chí Khoa học & Cơng nghệ, Đại học Đà nẵng, 5(54) [6] Trần Quốc Chiến,“Bài tốn mạng giao thơng đa phương tiện tuyến tính”, Đề tài NCKH cấp Bộ, mã số B2010DN-03-52. [7] Trần Quốc Chiến (2012),“Thuật tốn tìm đường đi ngắn nhất trên đồ thị tổng quát”, Tạp chí Khoa học & Cơng nghệ, Đại học Đà Nẵng, 12(61)/2012, 16-21. [8] Naveen Garg, Jochen Kưnemann (2007),“Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems”, SIAMJ. Comput, Canada, 37(2), 2007, pp. 630-652. [9] TCXDVN 104: 2007 “Đường đơ thị- Yêu cầu thiết kế”. Title: THE TRAFFIC ASSIGNMENT PROBLEM AND APPLICATIONS TRAN QUOC CHIEN The University of Da Nang – University of Education HO VAN HUNG Quang Nam University Abstract: This paper presents the following results of research (1) It provides a model of an extended traffic network on which costs are not the same for all traffic passing through a particular node, but rather depend on the route taken to and/ or from the node, especially given that some routes are blocked (2) The problem of Maximum Concurrent Multi-commodity Flow with Bounded Cost (MCMFBC) on extended networks is defined. The paper presents an approximation algorithm for solving MCMFBC which is based on the duality theory of linear programming and the algorithm for finding shortest path on extended networks. (3) The Traffic Assignment Problem (TAP) on extended networks is defined. The paper finally offers an efficient approximation algorithm finding the optimal multi-commodity flows, which is based on the algorithm to solve MCMFBC. Both algorithms presented in the paper are programmed in Java language with the use of the MySQL traffic network database for the center of Danang for accurate results. Keywords: Graph, Network, Multi-commodity Flow, Approximation, Optimization