求解连续网络设计问题的模拟退火算法灵敏度分析

交通运输系统工程与信息 ›› 2009, Vol. 9 ›› Issue (3): 64-70 .

求解连续网络设计问题的模拟退火算法灵敏度分析

杨进;徐猛^* ;高自友

北京交通大学交通运输学院，北京 100044

收稿日期:2008-11-06 修回日期:2009-04-13 出版日期:2009-06-25 发布日期:2009-06-25
通讯作者: 徐猛
作者简介:杨进（1983-），男，硕士生.
基金资助:
国家自然科学基金（70771005，,7631001）；国家重点基础研究发展计划（973计划）（2006CB705503）；教育部博士点新教师基金（20070004045）

Sensitivity Analysis of Simulated Annealing for Continuous Network Design Problems

YANG Jin; XU Meng; GAO Zi-you

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Received:2008-11-06 Revised:2009-04-13 Online:2009-06-25 Published:2009-06-25
Contact: XU Meng

摘要/Abstract

摘要： 研究了求解城市交通连续网络设计问题的模拟退火算法参数选择原则。采用双层规划模型来描述固定需求下的城市交通连续网络设计问题，其中上层问题的目标函数为整个网络的总阻抗和总投资额之和，下层问题则是用户平衡配流模型。利用模拟退火算法求解上层模型，下层模型则采用基于路径的GP算法进行求解。本文首次采用了灵敏度分析方法分析参数选择对模拟退火算法求解连续网络设计问题影响，比较了各个参数对算法结果及时间的影响，确定了参数的选择原则。根据上述分析方法得到的参数选择原则来设定参数的取值，能够提高算法的执行效率和收敛精度。

关键词: 连续网络设计问题, 双层规划模型, 模拟退火算法, 灵敏度分析

Abstract: In this paper, parameters choices of simulated annealing for continuous network design problems are discussed. A bi-level programming model for continuous network design problem is introduced. Objective function of the upper level is defined as the sum of the total travel time on the network and the total investment costs of link capacity expansions. The lower level problem is the user equilibrium assignment model, which is solved by the Gradient projection algorithm. Sensitivity analysis method is the first time used to analyze and compare the influence of the different selection of parameters to the implementation of simulated annealing algorithm. Suggestions of parameter selection are also given. Analysis demonstrates that the efficiency and precision of these methods can be improved clearly with the proposed suggestions.

Key words: continuous network design problem, bi-level programming model, simulated annealing, sensitivity analysis

中图分类号:

杨进,徐猛,高自友. 求解连续网络设计问题的模拟退火算法灵敏度分析[J]. 交通运输系统工程与信息, 2009, 9(3): 64-70 .

YANG Jin, XU Meng, GAO Zi-you. Sensitivity Analysis of Simulated Annealing for Continuous Network Design Problems[J]. Journal of Transportation Systems Engineering and Information Technology, 2009, 9(3): 64-70 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17813.shtml

http://www.tseit.org.cn/CN/Y2009/V9/I3/64

参考文献

[1] 高自友, 宋一凡, 四兵锋. 城市交通连续网络设计理论与方法[M].中国铁道出版社, 2000.

[Gao Ziyou, Song Yifan, Si Binfeng. Urban traffic network design problem: theory and Method[M], China Railway Publishing House, 2000.]

[2] Abdulaal M, LeBlanc L J. Continuous equilibrium network design models[J]. Transportation Research Part B, 1979, 13(1): 19-32.

[3] Boyce D E. Urban transportation network equilibrium and design models: Recent achievements and future prospectives[R]. Environment and Planning 16A, 1984:1445–1474.

[4] Yang H, Bell M G H. Models and algorithms for road network design: a review and some new developments[J]. Transport Review. 1998, 18(3), 257−278.

[5] 刘灿齐. 现代交通规划学[M]. 人民交通出版社, 2001.[LIU Chan-qi. Modern urban planning[M], China Communications Press,2001. ]

[6]张国强,陆键.连续网络设计问题的遗传算法[J],交通运输系统工程与信息, 2007, 7 (1) : 101-105. [ZHANG Guo-qiang, LU Jian, Genetic algorithm for continuous network design problem[J], Journal of Transportation Systems Engineering and Information Technology, 2007, 7(1): 101−105.]

[7] Friesz T L, Cho H J, Mehta N J, et al. A simulated annealing approach to network design problem with variational inequality constraints[J]. Transportation Science.1992, 26(1): 17-26.

[8] Friesz T L, Tobin R, Shah S, et al. The multi-objective equilibrium network design problem revisited: A simulated annealing approach[J]. European Journal of operations Research, 1993, 65: 44-57.

[9] 桂岚. 交通网络设计的优化模型及算法[J]. 系统工程. 2006, 24(12): 26-32.[GUI Lan. Optimization models and algorithms of traffic network design[J], System Engineering, 2006, 24(12): 26-32.]

[10] 刘灿齐.交通网络设计问题的模型与算法的研究[J].公路交通科技. 2003, 20(12): 57-67.

[LIU Chan-qi. Studies of models and algorithms of traffic network design problems[J], Journal of Highway and Transportation Research and Development. 2003, 20(12): 57-67.]

[11] XU T Z, WEI H, WANG Z D. Study on continuous network design problem using simulated annealing and genetic algorithm[J]. Expert Systems with Applications. 2009, 36(2), 2735-2741.

[12] Chen A, Lee D H. Jayakrishnan R. Computational study of state-of-the-art path-based traffic assignment algorithms[J]. Mathematics and Computers in Simulation. 2002, 59(6): 509-518.

[13] Saltelli A, Chan K, Scott E M. Sensitivity analysis[M]. New York, 2000.

[14] Suwansirikul C, Friesz T L, Tobin R L. Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem[J]. Transportation Science. 1987, 21: 254-263.

[1]	柳伍生, 李旺, 周清, 迭纤. “无人机-车辆”配送路径优化模型与算法[J]. 交通运输系统工程与信息, 2021, 21(6): 176-186.
[2]	何胜学, 马思涵, 程朝中, 崔允汀, 郁奇凡. 无人驾驶条件下共享停车匹配模型及算法[J]. 交通运输系统工程与信息, 2021, 21(4): 99-105.
[3]	邓连波，钟敏，蔡莉. 基于多速度调控的城轨列车区间运行策略优化[J]. 交通运输系统工程与信息, 2021, 21(2): 111-118.
[4]	蔡鉴明，欧阳姗. 考虑收益管理的高铁平行车次动态差别定价[J]. 交通运输系统工程与信息, 2020, 20(5): 1-8.
[5]	李晟东，吕红霞，吕苗苗，徐长安，倪少权. 日常动态货物列车开行方案优化研究[J]. 交通运输系统工程与信息, 2020, 20(5): 177-184.
[6]	任其亮，谭礼平. 逆向可变车道交叉口信号配时优化方法[J]. 交通运输系统工程与信息, 2020, 20(4): 63-70.
[7]	李兴华，张昕源，成诚，杨超，王洧. 考虑移步需求的无桩型共享单车动态调度研究[J]. 交通运输系统工程与信息, 2020, 20(3): 182-189.
[8]	薛运强，郭俊，安静，薛逻维，桑梓. 公交线路配车问题的不确定双层规划模型[J]. 交通运输系统工程与信息, 2020, 20(2): 145-150.
[9]	李雪梅，曹慧卓. 基于Epsilon 约束法的高速铁路客票多目标定价研究[J]. 交通运输系统工程与信息, 2020, 20(1): 6-11.
[10]	邓连波，徐毅梅，段科屹. 城市公交线网的一票制差异化票价策略优化[J]. 交通运输系统工程与信息, 2019, 19(5): 128-134.
[11]	罗清玉，杨金玲，吴文静，柳广照. 开放街区条件下的微循环道路网络设计[J]. 交通运输系统工程与信息, 2019, 19(3): 195-201.
[12]	唐继孟，李建，阳波. 补贴政策对集装箱公铁联运竞争力的影响分析[J]. 交通运输系统工程与信息, 2018, 18(6): 201-208.
[13]	李晟东，徐长安，吕红霞，李文新. 基于货物运到期限的编组站动态配流优化研究[J]. 交通运输系统工程与信息, 2018, 18(5): 164-169.
[14]	汤莲花，徐行方. 基于双层规划的市郊轨道交通多交路快慢车开行方案优化研究[J]. 交通运输系统工程与信息, 2018, 18(3): 152-159.
[15]	强生杰，贾斌，黄青霞. 基于模拟退火算法的快速登机序列特性研究[J]. 交通运输系统工程与信息, 2018, 18(2): 216-223.