کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1131991 1488975 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cost scaling based successive approximation algorithm for the traffic assignment problem
ترجمه فارسی عنوان
الگوریتم تقریبی پیوندی براساس مقیاس هزینه برای تخصیص ترافیک
کلمات کلیدی
تخصیص ترافیک، تقریب متوالی، مقیاس هزینه چرخه مینیمم، بوته
موضوعات مرتبط
علوم انسانی و اجتماعی علوم تصمیم گیری علوم مدیریت و مطالعات اجرایی
چکیده انگلیسی


• We propose a new algorithm that refines e-optimal flows to solve the TAP.
• A cost scaling method is used to select cycles by leveraging bush acyclicity.
• The number of flow operations is significantly less compared to a bush algorithm.
• The algorithm can solve highly precise solutions on large-scale networks.
• Cycle quality appears critical to the design of faster algorithms for the TAP.

This paper presents a cost scaling based successive approximation algorithm, called ε-BA (ε-optimal bush algorithm), to solve the user equilibrium traffic assignment problem by successively refining ε-optimal flows. As ε reduces to zero, the user equilibrium solution is reached. The proposed method is a variant of bush-based algorithms, and also a variant of the min-mean cycle algorithm to solve the min-cost flow by successive approximation. In ε-BA, the restricted master problem, implying traffic equilibration restricted on a bush, is solved to ε-optimality by cost scaling before bush reconstruction. We show that ε-BA can reduce the number of flow operations substantially in contrast to Dial’s Algorithm B, as the former operates flows on a set of deliberately selected cycles whose mean values are sufficiently small. Further, the bushes can be constructed effectively even if the restricted master problem is not solved to a high level of convergence, by leveraging the ε-optimality condition. As a result, the algorithm can solve a highly precise solution with faster convergence on large-scale networks compared to our implementation of Dial’s Algorithm B.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Transportation Research Part B: Methodological - Volume 68, October 2014, Pages 17–30
نویسندگان
, ,