﻿ 公交网络优化设计方法的最新进展 The Latest Development of Bus Network Optimization Design Method

Vol.07 No.05(2018), Article ID:25065,9 pages
10.12677/AAM.2018.75070

The Latest Development of Bus Network Optimization Design Method

Yutao Guan1, Guotao Lin2, Qian Peng1, He Yin1, Lu Wang1, Xiang Gao1*

1School of Mathematical Sciences, Ocean University of China, Qingdao Shandong

2Basic Teaching Center, Ocean University of China, Qingdao Shandong

Received: Apr. 30th, 2018; accepted: May 18th, 2018; published: May 25th, 2018

ABSTRACT

Transit Network Design Problem refers to the transportation resources under a certain limitation to a target bus system as the optimization objective, which is to solve the layout and scheduling of traffic line network. The purpose of Transit Network Design Problem is to rise up the operation efficiency of the public transit and relieve the traffic pressure in our daily life. Meanwhile, the practical significance of the Transit Network Design Problem has also made it an important problem in the development of the city. In the process of actual manipulation, the optimal line is obtained through a series of algorithms, and then the visual operation is carried out by software. In this paper, we briefly reviewed a series of achievements in the field of Transit Network Design Problem in recent decades, which cover mainly three aspects of algorithm, software and application.

Keywords:Transportation Planning, Combinatorial Optimization, Optimization Model, Heuristic Algorithm

1中国海洋大学数学科学学院，山东 青岛

2中国海洋大学基础教学中心，山东 青岛

1. 引言

2. 公交网络设计问题的概述

3. 公交网络设计问题

3.1. 研究方法

3.2. 求解算法

TNDP的模型通常涉及到组合最优化问题，这是TNDP问题本身的内在原因决定的，而这些模型的最优解又是不容易得到的，有些模型目前无法求得最优解，因此，我们考虑用启发式算法来解决TNDP的模型求解问题。

G：终止进化次数

M：种群规模

P- old：父代种群

P-new：子代种群

f(x)：计算个体x的适应度

Fmax：满意的适应度

Pc：交叉发生的概率

Pm：变异发生的概率

for n = 1: G

for i = 1: M

ifmin(f(P-new(j))) < f(P-old(i))

end

if max(f(P-new(j))) > Fmax

end

end

while没有生成够M个新个体

ifrand(0,1) > Pc

end

ifrand(0,1) > Pm

end

end

end

G Fusco等人 [8] 提出了采用遗传算法选择次优的路线的方法，在理论上解释了遗传算法在TNDP中的可行性。韩印 [9] 从公交线网发车间隔这一角度出发，构造了公交调度优化模型，将遗传算法引入到模型求解中，证明了遗传算法在这一问题求解上的实用性和可靠性。

1) 初始化：取蚂蚁m只，路径n条，将蚂蚁随机分配到路径上

2) 对蚁群整体做出评价，满足条件则输出路径，否则继续

3) 按蚂蚁经历的路径释放信息素

4) 根据信息素浓度按概率选择合适的路径

5) 降低全局信息素浓度，回到2)

3.3. 模型构建

$\underset{x}{opt}F\left(x,y\right)$

$s.t.$ $G\left(x,y\right)\le 0$

$\left(P2\right)$ $\underset{y}{opt}F\left(x,y\right)$

$s.t.$ $g\left(x,y\right)\le 0$

TNDP的模型建立通常依实际问题采取不同的策略，在分步求解问题时也可能会构建多个模型，除了双层规划模型还有许多有效实用的模型。

4. 轨道交通影响下的公交网络设计

4.1. 问题描述

1) 起止点均在轨道交通一次吸引范围内，轨道交通覆盖出行全过程，常规公交客流量转移至轨道交通，且注意比例随着出行距离而增加；

2) 起止点一端在轨道交通一次吸引范围内，轨道交通与常规公交配合完成出行，与轨道交通接驳的公交站客流量增加，单纯使用公交出行的客流量随着出行距离的减少而减少；

3) 起止点均不在轨道交通一次吸引范围内，时间和票价的阻扰作用较大，常规公交客流量转移到轨道交通的可能性小。

4.2. 模型与算法

5. 公交网络设计实例

5.1. 都江堰城市公交网络设计方法应用

5.2. 西安市公交线网设计研究及其运用

20世纪90年代以来，西安市的公共交通事业有了长足的发展，公交营运线路由1990年的54条增加到2007年的234条，营运线路总长度由1994年的804.8 km增加到2007年的3312 km，线路网长度由1996年的441.4 km增加到1999年的3726 km。

5.3. 保定市公交网络设计的具体运用

The Latest Development of Bus Network Optimization Design Method[J]. 应用数学进展, 2018, 07(05): 593-601. https://doi.org/10.12677/AAM.2018.75070

1. 1. 李博, 石小法. 城市公交系统的评价方法和应用[J]. 交通运输研究, 2012(19): 89-93.

2. 2. Lampkin, W. and Saalmans, P.D. (1967) The Design of Routes, Service Frequencies, and Schedules for a Municipal Bus Undertaking: A Case Study. Journal of the Operational Research Society, 18, 375-397.
https://doi.org/10.1057/jors.1967.70

3. 3. Ceder, A. and Wilson, N.H.M. (1986) Bus Network Design. Transportation Research Part B, 20, 331-344.
https://doi.org/10.1016/0191-2615(86)90047-0

4. 4. Baaj, M.H. and Mahmassani, H.S. (1995) Hybrid Route Generation Heu-ristic Algorithm for the Design of Transit Networks. Transportation Research Part C Emerging Technologies, 3, 31-50.
https://doi.org/10.1016/0968-090X(94)00011-S

5. 5. Mauttone, A. and Urquhart, M.E. (2009) A Route Set Construction Algo-rithm for the Transit Network Design Problem. Computers & Operations Research, 36, 2440-2449.
https://doi.org/10.1016/j.cor.2008.09.014

6. 6. Lee, Y.J. (1998) Analysis and Optimization of Transit Network Design with Integrated Routing and Scheduling. 1998(98-40212).

7. 7. 王炜. 实用公交线网规划方法研究[J]. 东南大学学报, 1990, 20(4): 81-88.

8. 8. Fusco, G., Gori, S. and Petrelli, M. (2002) A Heuristic Transit Network Design Algorithm for Medium Size Towns. Proceedings of Euro Working Group on Transportation, 652-656.

9. 9. 韩印. 基于遗传算法的智能公交发车频率优化研究[J]. 计算机工程与应用, 2008, 44(33): 243-245.

10. 10. Dorigo, M., Maniezzo, V. and Colorni, A. (1996) Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics: A Publication of the IEEE Systems Man & Cybernetics Society, 26, 29.
https://doi.org/10.1109/3477.484436

11. 11. 于景飞. 大城市常规公交线网优化方法研究及应用[D]: [硕士学位论文]. 合肥: 合肥工业大学, 2005.

12. 12. 于滨, 杨忠振, 程春田. 并行蚁群算法在公交线网优化中应用[J]. 大连理工大学学报, 2007, 47(2): 211-214.

13. 13. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., et al. (2004) Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21, 1087-1092.
https://doi.org/10.1063/1.1699114

14. 14. Kirkpatrick, S. and Vecchi, M.P. (1987) Optimization by Simulated Annealing. Readings in Computer Vision: Issues, Problems, Principles, and Paradigms. Morgan Kaufmann Publishers Inc., 339-348.

15. 15. Fan, W. and Machemehl, R.B. (2006) Using a Simulated Annealing Algorithm to Solve the Transit Route Network Design Problem. Journal of Transportation Engineering, 132, 122-132.
https://doi.org/10.1061/(ASCE)0733-947X(2006)132:2(122)

16. 16. 郑小花, 陈淑燕, 武林芝. 模拟退火算法在公交调度中的应用[J]. 信息化研究, 2009, 35(9): 45-47.

17. 17. Glover, F. (1986) Future Paths for Integer Programming and Links to Artificial In-telligence. Computers & Operations Research, 13, 533-549.
https://doi.org/10.1016/0305-0548(86)90048-1

18. 18. 白子建, 贺国光, 赵淑芝, 等. 快速公交车辆调度优化的禁忌算法设计与实现[J]. 计算机工程与应用, 2007, 43(23): 229-232.

19. 19. 周媛, 邓卫, 胡启洲. 基于遗传禁忌算法的城市公交线网优化研究[J]. 武汉理工大学学报(交通科学与工程版), 2011, 35(1): 42-45.

20. 20. 任传祥, 张海, 范跃祖. 混合遗传–模拟退火算法在公交智能调度中的应用[J]. 系统仿真学报, 2005, 17(9): 2075-2077.

21. 21. 赵志军. 融合蚁群算法的遗传算法在智能公交调度中的应用[D]: [硕士学位论文]. 长春: 吉林大学, 2007.

22. 22. Leblanc, L.J. (1975) An Algorithm for the Discrete Network Design Problem. Transportation Science, 9, 183-199.
https://doi.org/10.1287/trsc.9.3.183

23. 23. Bard, J.F. (1998) Practical Bilevel Optimization: Algorithms and Applications. Springer Publishing Company, Incorporated, 144-146.
https://doi.org/10.1007/978-1-4757-2836-1

24. 24. 单连龙, 高自友. 城市公交系统连续平衡网络设计的双层规划模型及求解算法[J]. 系统工程理论与实践, 2000, 20(7): 85-93.

25. 25. 于滨, 杨忠振, 程春田, 等. 公交线路发车频率优化的双层规划模型及其解法[J]. 吉林大学学报(工), 2006, 36(5): 664-668.

26. 26. 胡启洲, 张卫华. 城市公交线网优化的灰色关联度决策模型[J]. 系统工程学报, 2007, 22(6): 607-612.

27. 27. 张东旭. 基于聚类算法的定制公交线路模型设计研究[J]. 信息化建设, 2016(11): 344.

28. 28. 付波飞. 公交停靠站点优化模型[J]. 金田, 2015(10): 431.

29. 29. 胡列格, 段胜楠, 唐量, 等. 基于城市轨道交通的常规公交线网优化调整[J]. 徐州工程学院学报(自然科学版), 2015(1): 56-61.

30. 30. 李铁军. 基于地铁网络和车站的客运交通换乘枢纽体系研究[D]: [博士学位论文]. 西安: 长安大学, 2016.

31. 31. 罗艺, 钱大琳. 公交—地铁复合网络构建及网络特性分析[J]. 交通运输系统工程与信息, 2015, 15(5): 39-44.

32. 32. 徐勇, 贾欣, 王哲, 等. 公交地铁一体化下的网络模型与最优路选择算法[J]. 智能系统学报, 2015, 10(3): 482-487.

33. 33. 魏超, 龙建成. 城市轨道交通接驳公交线路优化设计[J]. 山东科学, 2015, 28(3): 65-73.

34. 34. 孙杨, 孙小年, 孔庆峰, 等. 轨道交通新线投入运营下常规公交网络优化调整方法研究[J]. 铁道学报, 2014(3): 1-8.

35. 35. 徐勇, 贾欣, 王哲, 等. 地铁环境下时变公交网络的最优路算法[J]. 计算机系统应用, 2015, 24(1): 104-108.

36. 36. 徐志强, 张欢, 周祥. 轨道交通接运公交线网优化研究[J]. 城市建设理论研究(电子版), 2013(16).

37. 37. 吴亮. 城市公交线网优化研究[D]: [硕士学位论文]. 兰州: 兰州交通大学, 2014.

38. 38. 李发宗, 涂先库, 訾琨. 基于TransCAD的城市交通分配模型研究[J]. 宁波工程学院学报, 2007, 19(4): 10-13.

39. 39. 马骥, 裴玉龙. TransCAD软件在城市交通规划中的开发与应用[J]. 哈尔滨建筑大学学报, 2002, 35(5): 118-122.

40. NOTES

*通讯作者。