Acceleration of Shortest-Path Search in Traffic Assignment by Memorizing Shortest-Path Trees
Kazutaka Takao, Yasuo Asakura · INFRASTRUCTURE PLANNING REVIEW · 2009
As the Frank-Wolfe algorithm repeats many iterations, it executes many repetitions of the shortest-path search. This paper describes acceleration of the shortest-path search by memorizing the shortest-path trees of previous iterations. After updating the travel times of the memorized trees for the current iteration, they are used as rejection borderlines to avoid setting long-routed labels in the label-correcting algorithm, contributing to reducing label correction. The performance is considerably improved because the counts of label correction are dramatically reduced. Although the required memory size becomes large, it is within the execution ability of recent PCs.