Origin-destination-based truncated quadratic programming algorithm for traffic assignment problem

Abstract

The solution of the static traffic assignment problem (TAP) with fixed origin-destination (OD) demands is considered. The original Frank and Wolfe (FW) algorithm is the most widely used in practice while suffering from a sublinear rate of convergence. The OD-based FW (ODBFW) algorithm was an attempt to speed up its convergence. The FW algorithm has been also used to compute search directions by partially solving a sequence of quadratic programming (QP) subproblems in a truncated QP (TQP) framework (FWTQP). In this study, we introduce an OD-based FWTQP (ODFWTQP) algorithm by embedding the decomposition and column generation in the FWTQP algorithm. The convergence rate of the ODFWTQP is investigated on the Chicago and Philadelphia test networks. A direct comparison is done between the proposed ODFWTQP and the algorithms of FW, ODBFW, FWTQP and the origin-based algorithm (OBA). Another direct comparison with a current commercial projected gradient (PG) algorithm is also provided. Based on the numerical results, the proposed algorithm shows a surprising performance.

Keywords:

• Traffic assignment
• truncated quadratic programming
• algorithms
• path-based formulation

Acknowledgments

The authors would like to thank Saeed Asadi Bagloee, PhD candidate at the Institute of Transport Studies at Monash University, for his assistance in providing the results regarding the Emme 4 software and the ODFWTQP code on his computer which made the direct comparisons of them possible. They, also, would like to sincerely thank Professor Michael Florian for sending copies of the results of the Emme 4 which helped to set the Emme 4 features for the test networks.

Notes

1. If a smaller value is specified in the path-based traffic assignment module of the Emme 4 software, it will be automatically converted to 1.0 × 10⁻⁷.