Top

Frontiers of Information Technology & Electronic Engineering

Published in:

01-11-2017

A surrogate-based optimization algorithm for network design problems

Authors: Meng Li, Xi Lin, Xi-qun Chen

Published in: Frontiers of Information Technology & Electronic Engineering | Issue 11/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Consensus-reaching methods for hesitant fuzzy multiple criteria group decision making with hesitant fuzzy decision making matrices

next article An optimized grey wolf optimizer based on a mutation operator and eliminating-reconstructing mechanism and its application

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Abdulaal, M., LeBlanc, L.J., 1979. Continuous equilibrium network design models. Transp. Res. B, 13(1): 19–32. https://doi.org/10.1016/0191-2615(79)90004-3CrossRef

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.

Cantarella, G.E., Vitetta, A., 2006. The multi-criteria road network design problem in an urban area. Transportation, 33(6): 567–588. https://doi.org/10.1007/s11116-006-7908-zCrossRef

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. https://doi.org/10.3141/2451-05CrossRef

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. https://doi.org/10.1111/mice.12058CrossRef

Chen, X.Q., Zhu, Z., Zhang, L., 2015a. Simulation-based optimization of mixed road pricing policies in a large realworld network. Transp. Res. Proc., 8: 215–226. https://doi.org/10.1016/j.trpro.2015.06.056CrossRef

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. https://doi.org/10.3141/2497-13CrossRef

Chiou, S.W., 2005. Bilevel programming for the continuous transport network design problem. Transp. Res. B, 39(4): 361–383. https://doi.org/10.1016/j.trb.2004.05.001CrossRef

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. https://doi.org/10.1007/s11081-013-9227-5MathSciNetCrossRef

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. https://doi.org/10.1016/0191-2615(94)90031-0CrossRef

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. https://doi.org/10.1016/j.tre.2011.02.001CrossRef

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. https://doi.org/10.1287/trsc.26.1.18CrossRef

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. https://doi.org/10.1016/j.ejor.2009.02.026CrossRef

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. https://doi.org/10.1016/j.trb.2004.06.004CrossRef

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. https://doi.org/10.1007/BF01582255MathSciNetCrossRef

Jones, D.R., Schonlau, M., Welch, W.J., 1998. Efficient global optimization of expensive black-box functions. J. Glob. Optim., 13(4): 455–492. https://doi.org/10.1023/A:1008306431147MathSciNetCrossRef

LeBlanc, L.J., 1975. An algorithm for the discrete network design problem. Transp. Sci., 9(3): 183–199. https://doi.org/10.1287/trsc.9.3.183CrossRef

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. https://doi.org/10.1016/j.trb.2012.05.003CrossRef

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. https://doi.org/10.1016/j.trb.2014.10.009CrossRef

Lo, H.K., Szeto, W.Y., 2009. Time-dependent transport network design under cost-recovery. Transp. Res. B, 43(1): 142–158. https://doi.org/10.1016/j.trb.2008.06.005CrossRef

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. https://doi.org/10.1016/j.trb.2011.02.002CrossRef

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. https://doi.org/10.1016/S0191-2615(00)00016-3CrossRef

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. https://doi.org/10.1016/j.cor.2012.08.022MathSciNetCrossRef

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].

Poorzahedy, H., Turnquist, M.A., 1982. Approximate algorithms for the discrete network design problem. Transp. Res. B, 16(1): 45–55. https://doi.org/10.1016/0191-2615(82)90040-6MathSciNetCrossRef

Poorzahedy, H., Abulghasemi, F., 2005. Application of ant system to network design problem. Transportation, 32(3): 251–273. https://doi.org/10.1007/s11116-004-8246-7CrossRef

Poorzahedy, H., Rouhani, O.M., 2007. Hybrid meta-heuristic algorithms for solving network design problem. Eur. J. Oper. Res., 182(2): 578–596. https://doi.org/10.1016/j.ejor.2006.07.038MathSciNetCrossRef

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. https://doi.org/10.1287/ijoc.1060.0182MathSciNetCrossRef

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. https://doi.org/10.1287/trsc.21.4.254CrossRef

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. https://doi.org/10.1016/j.trb.2009.10.003CrossRef

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. https://doi.org/10.1016/j.tre.2015.04.005CrossRef

Wang, S.A., Meng, Q., Yang, H., 2013. Global optimization methods for the discrete network design problem. Transp. Res. B, 50: 42–60. https://doi.org/10.1016/j.trb.2013.01.006CrossRef

Wardrop, J.G., 1952. Road Paper. Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng., 1(3): 325–362. https://doi.org/10.1680/ipeds.1952.11259

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. https://doi.org/10.1080/01441649808717016CrossRef

Yang, H., Yagar, S., 1995. Traffic assignment and signal control in saturated road networks. Transp. Res. A, 29(2): 125–139. https://doi.org/10.1016/0965-8564(94)E0007-VCrossRef

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

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. https://doi.org/10.1016/j.ejor.2008.09.008MathSciNetCrossRef

Title: A surrogate-based optimization algorithm for network design problems
Authors: Meng Li
Xi Lin
Xi-qun Chen
Publication date: 01-11-2017
Publisher: Zhejiang University Press
Published in: Frontiers of Information Technology & Electronic Engineering / Issue 11/2017
Print ISSN: 2095-9184
Electronic ISSN: 2095-9230
DOI: https://doi.org/10.1631/FITEE.1601403

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 11/2017

A virtual 3D interactive painting method for Chinese calligraphy and painting based on real-time force feedback technology

Miniaturized UWB multi-resonance patch antenna loaded with novel modified H-shape SRR metamaterial for microspacecraft applications

A novel energy-efficient ICI cancellation technique for bandwidth improvements through cyclic prefix reuse in an OFDM system

Laplacian sparse dictionary learning for image classification based on sparse representation

A highly efficient reconfigurable rotation unit based on an inverse butterfly network

Consensus-reaching methods for hesitant fuzzy multiple criteria group decision making with hesitant fuzzy decision making matrices

Premium Partner