Application of Paths Information in Network Design Problem
Publication: Journal of Transportation Engineering
Volume 138, Issue 7
Abstract
In a discrete network design problem, an optimal subset is chosen from a set of proposed link additions to an existing road network in order to minimize the total cost of users. The problem has been called as a complex issue in the transportation planning literature. The main source of complexity is that the problem is a bilevel program in which the lower-level program is a traffic assignment problem. In this paper, a path-based traffic assignment problem is used as the lower-level problem. The path-based algorithms not only provide the link-flow solution, but also the useful path-flow solution (path information) that may be required or used in certain applications, such as network design problem. To solve a network design problem, the traffic assignment problem will need to be solved many times. The main objective of this paper is to expedite the solution of the network design problem by initializing traffic assignment problems with path sets already found in previously performed traffic assignments. The rationale behind this idea is that the addition of a number of proposed links to a network will not change the used paths for the majority of origin-destination (OD) pairs. In this paper, the network design problem is solved by a branch and bound algorithm for a small network and a relatively large network. It is shown that the proposed method is capable of reducing the computation time to one-fifth in real-size networks.
Get full access to this article
View all available purchase options and get full access to this article.
References
Aashtiani, H. Z. (1979). “The multi-modal traffic assignment problem.” Ph.D. dissertation, MIT, Cambridge, MA.
Abdulaal, M., and LeBlanc, L. J. (1979). “Continuous equilibrium network design models.” Transp. Res. Part BTRBMDY, 13(1), 19–32.
Chen, A., and Jayakrishnan, R. (1998). “A path-based gradient projection algorithm: Effects of equilibration with restricted path set under two flow update policy.” 77th Transportation Research Board Annual Meetings (CD-ROM), Washington, DC.
Chen, A., and Lee, D. (1999). “Path-based algorithm for large scale traffic equilibrium problems: A comparison between DSD & GP.” 78th Transportation Research Board Annual Meetings (CD-ROM), Washington, DC.
Danzig, G. B., Harvey, R. P., Lansdowne, Z. F., Robinson, D. W., and Maier, S. F. (1979). “Formulating and solving the network design problem by decomposition.” Transp. Res. Part BTRBMDY, 13(1), 5–17.
Davis, G. A. (1994). “Exact local solution of the continuous network design problem via stochastic user equilibrium assignment.” Transp. Res. Part BTRBMDY, 28(1), 61–75.
Friesz, T. L., Cho, H. J., Mehta, N. J., Robin, R, and Anandalingam, G. (1992). “A simulated annealing approach to the network design problem with variation inequality constraints.” Transp. Sci.TRSCBJ, 26(1), 18–26.
Gao, Z., Wu, J., and Sun, H. (2005). “Solution algorithm for the bi-level discrete network design problem.” Transp. Res. Part BTRBMDY, 39(6), 479–495.
LeBlanc, L. J. (1975). “An algorithm for discrete network design problem.” Transp. Sci.TRSCBJ, 9(3), 183–199.
Lemke, C. E. (1965). “Bimatrix equilibrium points and mathematical programming.” Manage. Sci.MSCIAM, 11(7), 681–689.
Marcotte, P. (1983). “Network optimization with continuous control parameters.” Transp. Sci.TRSCBJ, 17(2), 181–197.
Mathew, T. V., and Sharma, S. (2009). “Capacity expansion problem for large urban transportation networks.” J. Transp. Eng.JTPEDI, 135(7), 406–415.
Meng, Q., and Yang, H. (2002). “Benefit distribution and equity in road network design.” Transp. Res. Part BTRBMDY, 36(1), 19–35.
Meng, Q., Yang, H., and Bell, M. G. H. (2001). “An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem.” Transp. Res. Part BTRBMDY, 35(1), 83–105.
Poorzahedy, H., and Turnquist, M. A. (1982). “Approximate algorithms for the discrete network design problem.” Transp. Res. Part BTRBMDY, 16(1), 45–56.
Steenbrink, P. A. (1974). “Transportation network optimization in the dutch integral transportation study.” Transp. Res.TRREBK, 8(1), 11–27.
Toobaie, S., Aashtiani, H. Z., Hamedi, M., and Haghani, A. (2010). “Application of complementarity approach to large-scale traffic equilibrium problems.” 89th Transportation Research Board Annual Meetings (CD-ROM), Washington, DC.
Wong, S. C., and Yang, H. (1997). “Reserve capacity of a signal controlled road network.” Transp. Res. Part BTRBMDY, 31(5), 397–402.
Yang, H., and Bell, M. G. H. (1998a). “A capacity paradox in network design and how to avoid it.” Transp. Res. Part ATRPPEC, 32(7), 539–545.
Yang, H., and Bell, M. G. H. (1998b). “Models and algorithms for road network design: A review and some developments.” Transp. Rev., 18(3), 257–278.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 138 • Issue 7 • July 2012
Pages: 863 - 870
Copyright
© 2012. American Society of Civil Engineers.
History
Received: Oct 10, 2008
Accepted: Dec 14, 2011
Published online: Dec 17, 2011
Published in print: Jul 1, 2012
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.