Abstract: Network design problems (NDPs) have long been regarded as one of the most challenging problems in the field of transportation planning due to the intrinsic non-convexity of their bi-level programming form. Furthermore, a mixture of continuous/discrete decision variables makes the mixed network design problem (MNDP) more complicated and difficult to solve. We adopt a surrogate-based optimization (SBO) framework to solve three featured categories of NDPs (continuous, discrete, and mixed-integer). We prove that the method is asymptotically completely convergent when solving continuous NDPs, guaranteeing a global optimum with probability one through an indefinitely long run. To demonstrate the practical performance of the proposed framework, numerical examples are provided to compare SBO with some existing solving algorithms and other heuristics in the literature for NDP. The results show that SBO is one of the best algorithms in terms of both accuracy and efficiency, and it is efficient for solving large-scale problems with more than 20 decision variables. The SBO approach presented in this paper is a general algorithm of solving other optimization problems in the transportation field.

网络设计问题的一种代理模型优化算法

[1]Abdulaal, M., LeBlanc, L.J., 1979. Continuous equilibrium network design models. Transp. Res. B, 13(1):19-32.

[2]Allsop, R.E., 1974. Some possibilities for using traffic control to influence trip distribution and route choice. Proc. 6th Int. Symp. on Transportation and Traffic Theory, p. 345-373.

[3]Cantarella, G.E., Vitetta, A., 2006. The multi-criteria road network design problem in an urban area. Transportation, 33(6):567-588.

[4]Chen, X.Q., Yin, M.G., Song, M.Z., et al., 2014a. Social welfare maximization of multimodal transportation. Transp. Res. Rec. J. Transp. Res. Board, 2451:36-49.

[5]Chen, X.Q., Zhang, L., He, X., et al., 2014b. Surrogate-based optimization of expensive-to-evaluate objective for optimal highway toll charges in transportation network. Comput.-Aid. Civil Infrastr. Eng., 29(5):359-381.

[6]Chen, X.Q., Zhu, Z., Zhang, L., 2015a. Simulation-based optimization of mixed road pricing policies in a large real- world network. Transp. Res. Proc., 8:215-226.

[7]Chen, X.Q., Zhu, Z., He, X., et al., 2015b. Surrogate-based optimization for solving a mixed integer network design problem. Transp. Res. Rec. J. Transp. Res. Board, 2497: 124-134.

[8]Chiou, S.W., 2005. Bilevel programming for the continuous transport network design problem. Transp. Res. B, 39(4): 361-383.

[9]Chow, J.Y.J., Regan, A.C., 2014. A surrogate-based multiobjective metaheuristic and network degradation simulation model for robust toll pricing. Optim. Eng., 15(1): 137-165.

[10]Davis, G.A., 1994. Exact local solution of the continuous network design problem via stochastic user equilibrium assignment. Transp. Res. B, 28(1):61-75.

[11]Farvaresh, H., Sepehri, M.M., 2011. A single-level mixed integer linear formulation for a bi-level discrete network design problem. Transp. Res. E, 47(5):623-640.

[12]Friesz, T.L., Cho, H.J., Mehta, N.J., et al., 1992. A simulated annealing approach to the network design problem with variational inequality constraints. Transp. Sci., 26(1):18-26.

[13]Gallo, M., D’Acierno, L., Montella, B., 2010. A meta-heuristic approach for solving the urban network design problem. Eur. J. Oper. Res., 201(1):144-157.

[14]Gao, Z.Y., Wu, J.J., Sun, H.J., 2005. Solution algorithm for the bi-level discrete network design problem. Transp. Res. B, 39(6):479-495.

[15]Harker, P.T., Pang, J.S., 1990. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math. Program., 48(1-3):161-220.

[16]Jones, D.R., Schonlau, M., Welch, W.J., 1998. Efficient global optimization of expensive black-box functions. J. Glob. Optim., 13(4):455-492.

[17]LeBlanc, L.J., 1975. An algorithm for the discrete network design problem. Transp. Sci., 9(3):183-199.

[18]Li, C.M., Yang, H., Zhu, D.L., et al., 2012. A global optimization method for continuous network design problems. Transp. Res. B, 46(9):1144-1158.

[19]Liu, H.X., Wang, D.Z.W., 2015. Global optimization method for network design problem with stochastic user equilibrium. Transp. Res. B, 72:20-39.

[20]Lo, H.K., Szeto, W.Y., 2009. Time-dependent transport network design under cost-recovery. Transp. Res. B, 43(1): 142-158.

[21]Luathep, P., Sumalee, A., Lam, W.H.K., et al., 2011. Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach. Transp. Res. B, 45(5):808-827.

[22]Meng, Q., Yang, H., Bell, M.G.H., 2001. An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem. Transp. Res. B, 35(1):83-105.

[23]Müller, J., Shoemaker, C.A., Piché, R., 2013. SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems. Comput. Oper. Res., 40(5):1383-1400.

[24]Nielsen, H.B., Lophaven, S.N., Søndergaard, J., 2002. DACE—a MATLAB Kriging Toolbox. Technical University of Denmark. Available from http://www2.imm.dtu.dk/projects/dace [Accessed on July 8, 2016].

[25]Poorzahedy, H., Turnquist, M.A., 1982. Approximate algorithms for the discrete network design problem. Transp. Res. B, 16(1):45-55.

[26]Poorzahedy, H., Abulghasemi, F., 2005. Application of ant system to network design problem. Transportation, 32 (3):251-273.

[27]Poorzahedy, H., Rouhani, O.M., 2007. Hybrid meta-heuristic algorithms for solving network design problem. Eur. J. Oper. Res., 182(2):578-596.

[28]Regis, R.G., Shoemaker, C.A., 2007. A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J. Comput., 19(4):497-509.

[29]Suwansirikul, C., Friesz, T.L., Tobin, R.L., 1987. Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem. Transp. Sci., 21(4): 254-263.

[30]Wang, D.Z.W., Lo, H.K., 2010. Global optimum of the linearized network design problem with equilibrium flows. Transp. Res. B, 44(4):482-492.

[31]Wang, D.Z.W., Liu, H.X., Szeto, W.Y., 2015. A novel discrete network design problem formulation and its global optimization solution algorithm. Transp. Res. E, 79:213-230.

[32]Wang, S.A., Meng, Q., Yang, H., 2013. Global optimization methods for the discrete network design problem. Transp. Res. B, 50:42-60.

[33]Wardrop, J.G., 1952. Road Paper. Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng., 1(3):325-362.

[34]Yang, H., Bell, M.G.H., 1998. Models and algorithms for road network design: a review and some new developments. Transp. Rev., 18(3):257-278.

[35]Yang, H., Yagar, S., 1995. Traffic assignment and signal control in saturated road networks. Transp. Res. A, 29(2):125-139.

[36]Yin, Y.F., 2000. Genetic-algorithms-based approach for bilevel programming models. J. Transp. Eng., 126(2):115-120.

[37]Yin, Y.F., Madanat, S.M., Lu, X.Y., 2009. Robust improvement schemes for road networks under demand uncertainty. Eur. J. Oper. Res., 198(2):470-479.