广州地铁设计研究院股份有限公司
摘要：网络设计问题通常在研究中被构筑成一个双层规划模型，而在其下层规划问题中的交通平衡模型普遍通过Frank-Wolfe方法求解。然而，由于多目标优化的运行时间较长，我们需要一种更具时间效率的方法来求解网络设计问题，因此代理模型方法将是一个很好的选择。本文旨在研究基于代理模型的优化方法对解决城市道路网络设计问题的适应性，并通过数值实验证明其有效性。
关键词：网络设计问题；代理模型
一、网络设计问题及代理模型
1.1 网络设计问题
网络设计问题（Network Design Problem）指在一定的约束条件下，在交通网络中添加新的路段或改善某些路段等，要考虑出行者行为选择的同时，从而使整个交通网络达到预定的目标。[1]其主要可分为连续网络设计问题、离散型网络设计问题及混合型网络设计问题三种。
网络设计问题通常被描述为一个双层规划问题。在双层规划模型的公式中，上层规划的目标是在成本约束下寻找最优解，以最优化网络的性能。下层问题则通常是用户均衡问题（User Equilibrium）及随机用户均衡问题（Stochastic User Equilibrium）。
在求解下层规划中的用户均衡问题时，我们通常借助Frank-Wolfe方法。当求解的网络规模较小时，Frank-Wolfe方法可以在较少迭代次数的情况下得到收敛的解。然而，当网络变得复杂或设计是多目标时，用Frank-Wolfe求解用户问题将耗费大量时间。
1.2 代理模型
代理模型是一种利用已知点的信息来预测未知点目标值的方法。该模型的核心是在拟合误差和预测误差的约束下，采用近似方法对离散数据进行拟合。
为了实现基于已知点来预测未知点的目标值，通常采用数学方法，通过拟合和插值来建立代理模型。常见的代理模型包括多项式回归模型、级数拟合方法、克里格插值和径向基函数等方法。本次研究通过建立多项式回归模型代替网络设计问题中的下层模型。[2]
作为最常见的代理模型之一，多项式回归假设目标函数和变量之间存在以下关系：
.png)
其中
.png)
为向量
.png)
第i维度的值，
.png)
,
.png)
及
.png)
为待求解的参数。
二、模型测试
本章节中，基于给定的城市道路网络，建立网络设计问题，并分别通过Frank-Wolfe方法求解原下层规划问题和遗传算法求解通过代理模型替换的下层规划问题，最后分析比较两种求解方法的准确性及时间效益。
2.1 道路网络
本次研究中建立了一个具有24个节点及76条通道的城市道路网络，用于测试城市道路网络设计优化方法的适用性。如下图所示，每一条通道的通过能力为1800辆/小时。
.png)
图2.1-1 道路网络示意图
2.2 网络设计问题
基于上述城市道路网络，建立了一个以最小化城市道路交通排放量为目标的网络设计问题：
.png)
(2.1)
.png)
(2.2)
.png)
(2.3)
.png)
(2.4)
.png)
(2.5)
.png)
(2.6)
.png)
(2.7)
其中式(2.1)-(2.3)为上层模型，式(2.4)-(2.7)下层规划模型为用户平衡模型。
2.3 测试结果
通过分别多次使用Frank-Wolfe方法求解原下层规划问题和遗传算法求解通过代理模型替换的下层规划问题，将得到的两种下层规划问题的解反馈到上层模型中得到目标值并加以对比，对比结果如下：
.png)
图2.3-1 目标值对比
表2.3-1 模型精度及计算时间对比
.png)
由上述结果可知，由基于代理模型的优化方法所得到的结果与由Frank-Wolfe方法所得的解非常接近，运算平均值相差未超过0.06%，而基于代理模型的优化方法相较Frank-Wolfe方法在运算时间方面节约了超过99%。
三、结论
在本次研究中，通过建立双层城市道路网络设计问题，并使用Frank-Wolfe方法及基于代理模型的优化方法分别求解下层规划模型中的用户平衡问题，结果证明在较为复杂的路网模型中，基于代理模型的优化方法的计算精度与Frank-Wolfe方法相近，而在运算时间上能节省99%以上，因此基于代理模型的优化方法能较好的代替现有方法用于求解城市道路网络设计问题。在未来的研究中，将进一步测试基于代理模型的优化方法对于更为复杂的路网模型的适用性。
参考文献
[1]高自友,张好智,孙会君.城市交通网络设计问题中双层规划模型、方法及应用[J].交通运输系统工程与信息,2004(01):35-44.
[2] Chen, X. M., Zhang, L., He, X., Xiong, C., & Li, Z. (2014). Surrogate‐Based Optimization of Expensive‐to‐Evaluate Objective for Optimal Highway Toll Charges in Transportation Network. Computer‐Aided Civil and Infrastructure Engineering, 29(5), 359-381.