Study on continuous network design problem using simulated annealing and genetic algorithm
Study on continuous network design problem using simulated annealing and genetic algorithm
复制标题
DOI：
10.1016/j.eswa.2008.01.071
复制
发表时间：
2009-03-01
影响因子：
8.5
通讯作者：
Wang, Zhuan-De
中科院分区：
文献类型：
--
作者：
Xu, Tianze;Wei, Heng;Wang, Zhuan-De
一般来说，连续网络设计问题（CNDP）被表述为双层程序。上层的目标函数定义为网络的总行程时间，加上链路容量扩展的总投资成本。较低层次的问题被表述为一定的交通分配模型。众所周知，这种双层规划是非凸且不可微的，并且最好使用寻找全局最优解的算法来求解。模拟退火（SA）和遗传算法（GA）是两种全局方法，可用于确定 CNDP 的最优解。由于SA和GA石油连续网络设计在实际交通网络中的应用需要在算法的每次迭代中多次求解交通分配模型，因此所需的计算时间是巨大的。在实践中比较两种方法的功效并选择更有效的一种作为参考方法非常重要。本文利用SA和GA模拟网络研究了连续网络设计问题。下层程序被制定为用户均衡流量分配模型，并采用Frank-Wolf方法进行求解。研究发现，当需求量较大时，SA 求解 CNDP 的效率比 GA 更高，并且 GA 需要更多的计算量才能达到与 SA 相同的最优解。然而，当需求较少时，GA 调用会以更多的计算时间为代价来达到更优化的解决方案。我们还发现，增加 SA 中每个温度的迭代次数并不一定会改善解。本例中的发现与 [Karoonsoontawong, A., & Waller, S. T. (2006) 不同。动态连续网络设计问题 - 线性双层规划和元启发式方法。网络建模 2006 年交通研究记录 (1964) (第 104-117 页)]。原因可能是本例中的双层模型是非线性的，而他们研究中的双层模型是线性的。 (C) 2008 年，爱思唯尔有限公司出版。
In general, a continuous network design problem (CNDP) is formulated its a bi-level program. The objective function at the upper level is defined as the total travel time oil the network, plus total investment costs of link capacity expansions. The lower level problem is formulated as it certain traffic assignment model. It is well known that such bi-level program is non-convex and non-differentiable and algorithms for finding global optimal solutions are preferable to be used in solving it. Simulated annealing (SA) and genetic algorithm (GA) are two global methods and can then be used to determine the optimal solution of CNDP. Since application of SA and GA oil continuous network design on real transportation network requires solving traffic assignment model many times at each iteration of the algorithm, computation time needed is tremendous. It is important to compare the efficacy of the two methods and choose the more efficient one as reference method in practice. In this paper, the continuous network design problem has been studied using SA and GA oil a simulated network. The lower level program is formulated as user equilibrium traffic assignment model and Frank-Wolf method is used to solve it. It is found that when demand is large, SA is more efficient than GA in solving CNDP, and much more computational effort is needed for GA to achieve the same optimal solution as SA. However, when demand is light, GA call reach a more optimal solution at the expense of more computation time. It is also found that increasing the iteration number at each temperature in SA does not necessarily improve solution. The finding in this example is different from [Karoonsoontawong, A., & Waller, S. T. (2006). Dynamic continuous network design problem - Linear bilevel programming and metaheuristic approaches. Network Modeling 2006 Transportation Research Record (1964) (pp. 104-117)]. The reason might be the bi-level model in this example is nonlinear while the bi-level model in their study is linear. (C) 2008 Published by Elsevier Ltd.