A surrogate-based optimization algorithm for network design problems

Meng LI; Xi LIN; Xi-qun CHEN

doi:10.1631/FITEE.1601403

Your Location：

Home >

Browse articles >

A surrogate-based optimization algorithm for network design problems

Regular Papers | Updated：2022-05-19

- A surrogate-based optimization algorithm for network design problems
- 网络设计问题的一种代理模型优化算法
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 11, Pages: 1693-1704(2017)
- Affiliations：
  
  Department of Civil Engineering, Tsinghua University, Beijing 100084, China
  College of Civil Engineering and Architecture, Zhejiang University, Hangzhou 310058, China
- Author bio：
  
  Xi-qun CHEN, E-mail: chenxiqun@zju.edu.cn
- Funds：
- DOI：10.1631/FITEE.1601403
  CLC： U491;TP202
- Received：08 July 2016，
  
  Revised：2017-11-22，
  
  Published：2017-11
- Accepted：
Scan QR Code
Meng LI, Xi LIN, Xi-qun CHEN. A surrogate-based optimization algorithm for network design problems[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1693-1704.
DOI：

Meng LI, Xi LIN, Xi-qun CHEN. A surrogate-based optimization algorithm for network design problems[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1693-1704. DOI： 10.1631/FITEE.1601403.

摘要

由于其双层规划结构本质上的非凸性，交通网络设计问题一直以来都是交通规划领域中最为困难的问题之一。尤其在考虑混合了连续变量与离散变量的决策变量时，得到的混合网络设计形式进一步增加了问题的难度。本文引入了一种代理模型优化算法，用以解决三种不同种类的网络设计问题，包括连续、离散与混合的情形。我们证明了提出的算法在解决连续网络设计问题时，能够确保"渐进完全收敛"的性质，即在给定足够长的计算时间时，算法能够以概率1收敛到全局最优解。为了展示本文提出的框架在实际问题中的表现，我们用大量的算例对比了代理模型算法与大量用于解决网络设计问题的经典算法、启发式算法的效果。结果表明，以效率与精确度而论，代理模型算法是其中最优秀之一，同时它还能够有效地解决超过20个变量的较大规模的问题。本文提出的代理模型优化框架也能够用于解决交通领域的其他优化问题。

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.

关键词

Keywords

references

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

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

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

X.Q. Chen , , , M.G. Yin , , , M.Z. Song , , , 等 . . Social welfare maximization of multimodal transportation . . Transp. Res. Rec. J. Transp. Res. Board , , 2014a . . 2451 36 - - 49 . . DOI: 10.3141/2451-05 http://doi.org/10.3141/2451-05 . .

X.Q. Chen , , , L. Zhang , , , X. He , , , 等 . . Surrogate-based optimization of expensive-to-evaluate objective for optimal highway toll charges in transportation network . . Comput.-Aid. Civil Infrastr. Eng. , , 2014b . . 29 ( ( 5 ): ): 359 - - 381 . . DOI: 10.1111/mice.12058 http://doi.org/10.1111/mice.12058 . .

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

X.Q. Chen , , , Z. Zhu , , , X. He , , , 等 . . Surrogate-based optimization for solving a mixed integer network design problem . . Transp. Res. Rec. J. Transp. Res. Board , , 2015b . . 2497 124 - - 134 . . DOI: 10.3141/2497-13 http://doi.org/10.3141/2497-13 . .

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

J.Y.J. Chow , , , A.C. Regan . . A surrogate-based multiobjective metaheuristic and network degradation simulation model for robust toll pricing . . Optim. Eng. , , 2014 . . 15 ( ( 1 ): ): 137 - - 165 . . DOI: 10.1007/s11081-013-9227-5 http://doi.org/10.1007/s11081-013-9227-5 . .

G.A. Davis . . Exact local solution of the continuous network design problem via stochastic user equilibrium assignment . . Transp. Res. B , , 1994 . . 28 ( ( 1 ): ): 61 - - 75 . . DOI: 10.1016/0191-2615(94)90031-0 http://doi.org/10.1016/0191-2615(94)90031-0 . .

H. Farvaresh , , , M.M. Sepehri . . A single-level mixed integer linear formulation for a bi-level discrete network design problem . . Transp. Res. E , , 2011 . . 47 ( ( 5 ): ): 623 - - 640 . . DOI: 10.1016/j.tre.2011.02.001 http://doi.org/10.1016/j.tre.2011.02.001 . .

T.L. Friesz , , , H.J. Cho , , , N.J. Mehta , , , 等 . . A simulated annealing approach to the network design problem with variational inequality constraints . . Transp. Sci. , , 1992 . . 26 ( ( 1 ): ): 18 - - 26 . . DOI: 10.1287/trsc.26.1.18 http://doi.org/10.1287/trsc.26.1.18 . .

M. Gallo , , , L. D'Acierno , , , B. Montella . . A meta-heuristic approach for solving the urban network design problem . . Eur. J. Oper. Res. , , 2010 . . 201 ( ( 1 ): ): 144 - - 157 . . DOI: 10.1016/j.ejor.2009.02.026 http://doi.org/10.1016/j.ejor.2009.02.026 . .

Z.Y. Gao , , , J.J. Wu , , , H.J. Sun . . Solution algorithm for the bi-level discrete network design problem . . Transp. Res. B , , 2005 . . 39 ( ( 6 ): ): 479 - - 495 . . DOI: 10.1016/j.trb.2004.06.004 http://doi.org/10.1016/j.trb.2004.06.004 . .

P.T. Harker , , , J.S. Pang . . Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications . . Math. Program. , , 1990 . . 48 ( ( 1-3 ): ): 161 - - 220 . . DOI: 10.1007/BF01582255 http://doi.org/10.1007/BF01582255 . .

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

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

C.M. Li , , , H. Yang , , , D.L. Zhu , , , 等 . . A global optimization method for continuous network design problems . . Transp. Res. B , , 2012 . . 46 ( ( 9 ): ): 1144 - - 1158 . . DOI: 10.1016/j.trb.2012.05.003 http://doi.org/10.1016/j.trb.2012.05.003 . .

H.X. Liu , , , D.Z.W. Wang . . Global optimization method for network design problem with stochastic user equilibrium . . Transp. Res. B , , 2015 . . 72 20 - - 39 . . DOI: 10.1016/j.trb.2014.10.009 http://doi.org/10.1016/j.trb.2014.10.009 . .

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

P. Luathep , , , A. Sumalee , , , W.H.K. Lam , , , 等 . . Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach . . Transp. Res. B , , 2011 . . 45 ( ( 5 ): ): 808 - - 827 . . DOI: 10.1016/j.trb.2011.02.002 http://doi.org/10.1016/j.trb.2011.02.002 . .

Q. Meng , , , H. Yang , , , M.G.H. Bell . . An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem . . Transp. Res. B , , 2001 . . 35 ( ( 1 ): ): 83 - - 105 . . DOI: 10.1016/S0191-2615(00)00016-3 http://doi.org/10.1016/S0191-2615(00)00016-3 . .

J. Müller , , , C.A. Shoemaker , , , R. Piché . . SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems . . Comput. Oper. Res. , , 2013 . . 40 ( ( 5 ): ): 1383 - - 1400 . . DOI: 10.1016/j.cor.2012.08.022 http://doi.org/10.1016/j.cor.2012.08.022 . .

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

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

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

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

R.G. Regis , , , C.A. Shoemaker . . A stochastic radial basis function method for the global optimization of expensive functions . . INFORMS J. Comput. , , 2007 . . 19 ( ( 4 ): ): 497 - - 509 . . DOI: 10.1287/ijoc.1060.0182 http://doi.org/10.1287/ijoc.1060.0182 . .

C. Suwansirikul , , , T.L. Friesz , , , R.L. Tobin . . Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem . . Transp. Sci. , , 1987 . . 21 ( ( 4 ): ): 254 - - 263 . . DOI: 10.1287/trsc.21.4.254 http://doi.org/10.1287/trsc.21.4.254 . .

D.Z.W. Wang , , , H.K. Lo . . Global optimum of the linearized network design problem with equilibrium flows . . Transp. Res. B , , 2010 . . 44 ( ( 4 ): ): 482 - - 492 . . DOI: 10.1016/j.trb.2009.10.003 http://doi.org/10.1016/j.trb.2009.10.003 . .

D.Z.W. Wang , , , H.X. Liu , , , W.Y. Szeto . . A novel discrete network design problem formulation and its global optimization solution algorithm . . Transp. Res. E , , 2015 . . 79 213 - - 230 . . DOI: 10.1016/j.tre.2015.04.005 http://doi.org/10.1016/j.tre.2015.04.005 . .

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

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

H. Yang , , , M.G.H. Bell . . Models and algorithms for road network design: a review and some new developments . . Transp. Rev. , , 1998 . . 18 ( ( 3 ): ): 257 - - 278 . . DOI: 10.1080/01441649808717016 http://doi.org/10.1080/01441649808717016 . .

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

Y.F. Yin . . Genetic-algorithms-based approach for bilevel programming models . . J. Transp. Eng. , , 2000 . . 126 ( ( 2 ): ): 115 - - 120 . . DOI: 10.1061/(ASCE)0733-947X(2000)126:2(115) http://doi.org/10.1061/(ASCE)0733-947X(2000)126:2(115) . .

Y.F. Yin , , , S.M. Madanat , , , X.Y. Lu . . Robust improvement schemes for road networks under demand uncertainty . . Eur. J. Oper. Res. , , 2009 . . 198 ( ( 2 ): ): 470 - - 479 . . DOI: 10.1016/j.ejor.2008.09.008 http://doi.org/10.1016/j.ejor.2008.09.008 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰