Full Text:   <1742>

Summary:  <1197>

CLC number: U491; TP202

On-line Access: 2018-01-12

Received: 2016-07-08

Revision Accepted: 2016-10-27

Crosschecked: 2017-11-22

Cited: 0

Clicked: 5266

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Xi-qun Chen

http://orcid.org/0000-0001-8285-084X

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.11 P.1693-1704

http://doi.org/10.1631/FITEE.1601403


A surrogate-based optimization algorithm for network design problems


Author(s):  Meng Li, Xi Lin, Xi-qun Chen

Affiliation(s):  Department of Civil Engineering, Tsinghua University, Beijing 100084, China; more

Corresponding email(s):   chenxiqun@zju.edu.cn

Key Words:  Network design problem, Surrogate-based optimization, Transportation planning, Heuristics


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.

@article{title="A surrogate-based optimization algorithm for network design problems",
author="Meng Li, Xi Lin, Xi-qun Chen",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="18",
number="11",
pages="1693-1704",
year="2017",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1601403"
}

%0 Journal Article
%T A surrogate-based optimization algorithm for network design problems
%A Meng Li
%A Xi Lin
%A Xi-qun Chen
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 11
%P 1693-1704
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1601403

TY - JOUR
T1 - A surrogate-based optimization algorithm for network design problems
A1 - Meng Li
A1 - Xi Lin
A1 - Xi-qun Chen
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 11
SP - 1693
EP - 1704
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1601403


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收敛到全局最优解。为了展示本文提出的框架在实际问题中的表现,我们用大量的算例对比了代理模型算法与大量用于解决网络设计问题的经典算法、启发式算法的效果。结果表明,以效率与精确度而论,代理模型算法是其中最优秀之一,同时它还能够有效地解决超过20个变量的较大规模的问题。本文提出的代理模型优化框架也能够用于解决交通领域的其他优化问题。

关键词:网络设计问题;代理模型优化;交通规划;启发式算法

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

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

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE