28th Tokyo Tech TSU Seminar: Solving Path Problems in Network Traffic Assignment
東京工業大学 大岡山キャンパス 緑が丘６号館 Midorigaoka Build. #6, Ookayama Campus, Tokyo Institute of Technology
Date：13th July (Thu.) 2017
Time：14:00 - 17:00
Title：Another Alternative to Dial's Logit Assignment Algorithm on All Acyclic Paths
Speaker：Dr. Takeshi Nagae (Tohoku University) and Shin-ichi Inoue (The Institute of Behavioral Sciences)
Title：Why does proportionality matter in traffic assignment and how to achieve it?
Speaker：Prof. Yu (Marco) Nie (Northwestern University)
Abstract for Lecture 2：
The proportionality condition has been widely used to produce a unique path flow solution in the user equilibrium traffic assignment problem. In this talk I will first explain why proportionality offers a conceptually simple, practically viable and computationally efficient approach to determining a path flow solution that approximately conforms to the principle of entropy maximization. I will then address two hitherto open questions: (1) whether and to what extent does the proportionality condition accord to real travel behavior; and (2) how to develop an efficient algorithm that guarantees finding a solution to satisfy the proportionality condition strictly? To answer the first question, we mine a large taxi trajectory data set to obtain millions of route choice observations, and uncover hundreds of valid paired alternative segments (PAS) from the data. The results obtained by performing linear regression analysis and chi-square tests show that the majority of the PASs tested (up to 85%) satisfy the proportionality condition at a reasonable level of statistical significance. To answer the second question, we propose a novel algorithm. It alternates between constructing an origin-based and a destination-based bush representation of user equilibrium solutions, and iteratively solves the entropy maximization subproblem defined for each bush. Thanks to the special structure of bushes, these subproblems can be solved efficiently. The proposed algorithm thus obviates enumerating all UE paths or collecting a set of paired alternative segments (PAS) to cover them. We prove that the algorithm ensures convergence to a solution that perfectly satisfies the proportionality condition in general networks. The proposed algorithm solves the problem much faster than the known alternatives, with a speedup of 3 - 8 times on large networks.
Short Bio. of Dr. Yu (Marco) Nie：
Dr. Marco Nie is currently an Associate Professor of Civil and Environmental Engineering at Northwestern University. He received his B.S. in Structural Engineering from Tsinghua University, his M.Eng. from National University of Singapore and his Ph.D. from the University of California, Davis. Dr. Nie’s research covers a variety of topics in the areas of transportation systems analysis, transportation economics, sustainable transportation and traffic flow theory and simulation. Dr. Nie is currently a member of TRB committee on Transportation Network Modeling (ADB30). He also serves as an Associate Editor for Transportation Science, an Area Editor for Networks and Spatial Economics, and is a member of the Editorial Advisory Board for Transportmetrica-B and Transportation Research Part B. Dr. Nie’s research has been supported by National Science Foundation, Transportation Research Board, US Department of Transportation, US Department of Energy, and Illinois Department of Transportation.