A surrogate-based optimization algorithm for network design problems

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个变量的较大规模的问题。本文提出的代理模型优化框架也能够用于解决交通领域的其他优化问题。