Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một Thuật Toán Heuristic cho Vấn Đề Lưu Lượng Đến Sớm Nhất với Nhiều Nguồn
Tóm tắt
Bài báo này trình bày một thuật toán heuristic cho vấn đề lưu lượng đến sớm nhất. Các thuật toán chính xác hiện có, ngay cả khi có bậc đa thức về kích thước đầu ra, đều chứa tối ưu hóa hàm con mô-đun như một tiểu trình thường được gọi, do đó không thực tiễn trong các ứng dụng thực tế. Trong bài báo này, chúng tôi đề xuất một thuật toán không liên quan đến tối ưu hóa hàm con mô-đun. Mặc dù giải quyết một EAF gần tối ưu, thuật toán rất đơn giản và hiệu quả vì nó chỉ liên quan đến việc tính toán đường đi ngắn nhất trên một mạng tĩnh. Một ví dụ số liệu minh họa cách thức hoạt động của thuật toán. Như một ứng dụng, chúng tôi chứng minh chất lượng giải pháp và hiệu suất tính toán của thuật toán bằng cách giải quyết một mạng có kích thước thực.
Từ khóa
#thuật toán heuristic #lưu lượng đến sớm nhất #tối ưu hóa hàm con mô-đun #mạng tĩnh #tính toán đường đi ngắn nhất #mạng có kích thước thựcTài liệu tham khảo
Ford, Jr., L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Oper. Res. 6(3), 419–433 (1958)
Aronson, J.E.: A survey of dynamic network flows. Ann. Oper. Res. 20, 1–66 (1989)
Bookbinder, J.H., Sethi, S.P.: The dynamic transportation problem: a survey. Nav. Res. Logist. Q. 27(3), 447–452 (1980)
Skutella, M.: An introduction to network flows over time. In: Cook, W.J., Lovasz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 451–482. Springer, Berlin Heidelberg (2008)
Fleischer, L., Tardos, E.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23(3–5), 71–80 (1998)
Gale, D.: Transient flows in networks. Mich. Math. J. 6(1), 59–63 (1959)
Philpott, A.B.: Continuous time flows in networks. Math. Oper. Res. 15(4), 640–661 (1990)
Fleischer, L.K.: Faster algorithms for the quickest transshipment problem. SIAM J. Optim. 12(1), 18–35 (2001)
Fleischer, L., Skutella, M.: Quickest flows over time. SIAM J. Comput. 36(5), 1600–1630 (2007)
Richardson, D., Tardos, E.: Cited as personal communication in Fleischer, L., Skutella, M. 2007 (2000)
Chalmet, L.G., Francis, R.L., Saunders, P.B.: Network models for building evaucation. Manag. Sci. 28(1), 86–105 (1982)
Jarvis, J.J., Ratliff, H.D.: Some equivalent objectives for dynamic network flow problems. Manag. Sci. 28(1), 106–109 (1982)
Hamacher, H.W., Tjandra, S.A.: Mathematical modelling of evacuation problems: a state of art. In: Schreckenberg, M., Sharma, S.D. (eds.) Pedestrian and Evacuation Dynamics, pp. 227–266. Springer (2002)
Kohler, E., Skutella, M.: Flows over time with load-dependent transit times. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 174–183. SIAM (2002)
Carey, M., Subrahmanian, E.: An approach to modelling time-varying flows on congested networks. Transp. Res. 34B(3), 157–183 (2000)
Ziliaskopoulos, A.K.: A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transp. Sci. 34(1), 37–49 (2000)
Daganzo, C.F.: The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp. Res. 28B(4), 269–287 (1994)
Daganzo, C.F.: The cell transmission model part ii: network traffic. Transp. Res. 29B(2), 79–93 (1995)
Chiu, Y.-C., Zheng, H., Villalobos, J., Gautam, B.: Modeling no-notice mass evacuation using a dynamic traffic flow optimization model. IIE Trans. 39(1), 83–94 (2007)
Cova, T.J., Johnson, J.P.: A network flow model for lane-based evacuation routing. Transp. Res. 37A, 579–604 (2003)
Tuydes, H., Ziliaskopoulos, A.: Network re-design to optimize evacuation contraflow. In: Proceeding of the 83rd Annual Meeting of the Transportation Research Board (CD-ROM), Article No. 04-4715(2004)
Shen, W., Nie, Y., Zhang, H.M.: Dynamic network simplex method for designing emergency evacuation plans. Transp. Res. Record 2022, 83–93 (2007)
Chiu, Y.-C., Zheng, H.: Real-time mobilization decisions for multi-priority emergency response resources and evacuation groups: model formulation and solution. Transp. Res. 43E(5), 710–736 (2007)
Zheng, H., Chiu, Y.-C.: A network flow algorithm for the cell based single destination system optimal dynamic traffic assignment problem. Transp. Sci. 45(1), 121–137 (2011)
Zheng, H., Chiu, Y.-C., Mirchandani, P.B.: On the system optimal dynamic traffic assignment and earliest arrival flow problems. Transp. Sci. (2013, in press)
Wilkinson, W.L.: An algorithm for universal maximal dynamic flows in a network. Oper. Res. 19(6), 1602–1612 (1971)
Minieka, E.: Maximal, lexicographic, and dynamic network flows. Oper. Res. 21(2), 517–527 (1973)
Hoppe, B., Tardos, E.: Polynomial time algorithms for some evacuation problems. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 433–441 (1994)
Hajek, B., Ogier, R.G.: Optimal dynamic routing in communication networks with continuous traffic. Networks 14(3), 457–487 (1984)
Rauf, I.: Earliest Arrival Flows with Multiple Sources, Master. Saarland University, Saarbrücken, Germany, Thesis (2005)
Fleischer, L., Skutella, M.: The quickest multicommodity flow problem. In: Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization, pp. 36–53 (2002)
Baumann, N., Skutella, M.: Earliest arrival flows with multiple sources. Math. Oper. Res. 34(2), 499–512 (2009)
Hoppe, B., Tardos, E.: The quickest transshipment problem. Math. Oper. Res. 25(1), 36–62 (2000)
Burkard, R.E., Dlaska, K., Klinz, B.: The quickest flow problem. ZOR - Methods Models Oper. Res. 37(1), 31–58 (1993)
Zadeh, N.: A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Program. 5, 255–266 (1973)
Baumann, N.: Evacuation by Earliest Arrival Flows. Ph.D. thesis, TU Dortmund, Dortmund, Germany (2007)