×

A modified active set algorithm for transportation discrete network design bi-level problem. (English) Zbl 1359.90144

Summary: Transportation discrete network design problem (DNDP) is about how to modify an existing network of roads and highways in order to improve its total system travel time, and the candidate road building or expansion plan can only be added as a whole. DNDP can be formulated into a bi-level problem with binary variables. An active set algorithm has been proposed to solve the bi-level discrete network design problem, while it made an assumption that the capacity increase and construction cost of each road are based on the number of lanes. This paper considers a more general case when the capacity increase and construction cost are specified for each candidate plan. This paper also uses numerical methods instead of solvers to solve each step, so it provides a more direct understanding and control of the algorithm and running procedure. By analyzing the differences and getting corresponding solving methods, a modified active set algorithm is proposed in the paper. In the implementation of the algorithm and the validation, we use binary numeral system and ternary numeral system to avoid too many layers of loop and save storage space. Numerical experiments show the correctness and efficiency of the proposed modified active set algorithm.

MSC:

90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows: theory, algorithms, and applications. Tech. rep., DTIC Document (1988) · Zbl 1201.90001
[2] Beckmann, M., McGuire, C., Winsten, C.B.: Studies in the economics of transportation. Tech. rep. (1956)
[3] Bertsekas, D.P.: Nonlinear programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[4] CPLEX, I.I.: V12. 1: Users manual for CPLEX. Int. Bus. Mach. Corp. 46(53), 157 (2009)
[5] Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269-271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390
[6] Drud, A.S.: Conopt a large-scale GRG code. ORSA J. Comput. 6(2), 207-216 (1994) · Zbl 0806.90113 · doi:10.1287/ijoc.6.2.207
[7] Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1-2), 95-110 (1956) · doi:10.1002/nav.3800030109
[8] Friesz, T.L., Bernstein, D., Smith, T.E., Tobin, R.L., Wie, B.: A variational inequality formulation of the dynamic network user equilibrium problem. Oper. Res. 41(1), 179-191 (1993) · Zbl 0771.90037 · doi:10.1287/opre.41.1.179
[9] Fukushima, M.: A modified frank-wolfe algorithm for solving the traffic assignment problem. Transp. Res. Part B Methodol. 18(2), 169-177 (1984) · doi:10.1016/0191-2615(84)90029-8
[10] Larsson, T., Patriksson, M.: Side constrained traffic equilibrium models analysis, computation and applications. Transp. Res. Part B Methodol. 33(4), 233-264 (1999) · doi:10.1016/S0191-2615(98)00024-1
[11] Rosenthal, R.E.: Gams—a user’s guide. GAMS Development Corporation, Washington, DC (2004) · Zbl 0092.16002
[12] Seref, O., Ahuja, R.K., Orlin, J.B.: Incremental network optimization: theory and algorithms. Oper. Res. 57(3), 586-594 (2009) · Zbl 1226.90125 · doi:10.1287/opre.1080.0607
[13] Sheffi, Y.: Urban transportation networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Inc., Englewood Cliffs (1984) · Zbl 0529.90063
[14] Skiena, S.: Dijkstra’s Algorithm. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Addison-Wesley, Reading (1990) · Zbl 0786.05004
[15] Yin, Y., Lawphongpanich, S.: A robust approach to continuous network designs with demand uncertainty. In: Transportation and Traffic Theory 2007. Papers Selected for Presentation at ISTTT17 (2007) · Zbl 0092.16002
[16] Zhang, L., Lawphongpanich, S., Yin, Y.: An active-set algorithm for discrete network design problems. In: Lam, W.H.K., Wong, H., Lo, H.K. (eds.) Transportation and Traffic Theory 2009: Golden Jubilee, pp. 283-300. Springer, Berlin (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.