方云飞(1983—), 男, 副教授, 主要从事交通运输与规划研究, (E-mail)
为提高公共交通系统的吸引力,从公共自行车和公交车接驳的角度,提出以公交站点为中心的公共自行车选址及自行车道设置的网络构建问题。首先,建立以最大化满足用户需求量为优化目标的非线性优化模型,并与只考虑站点选址的传统模型进行比较分析;在分析问题基础上,构造基于问题特性的邻域结构和邻域解生成准则,并最终设计基于禁忌搜索的问题求解方法。通过MATLAB编程进行仿真实验测试大量算例,结果表明所设计算法能够高效地求解各类规模算例,并给出高质量的公共自行车网络构建近似最优方案;此外,敏感性分析实验为规划者制定决策方案提供参考依据。
To improve the attractiveness of public transportation system, optimal network layout of the public bike stations and bike lanes was studied from the point of view of transferring between buses and public bikes. In this paper, a nonlinear optimization model with the objective of maximizing the users' demand was formulated, and it was compared with the traditional location model. Based on the special designed neighborhood and its generation criterion, a tabu-search-based algorithm was proposed to solve the problem. Then simulation experiments by MATLAB program were conducted and the computational results show that the proposed algorithm efficiently solves different-sized instances and obtains high quality solutions for the network layout of public bicycle system. Furthermore, results of the sensitive experiments can provide useful information for planners' decision-making.
随着中国城市化、机动化的发展,城市交通拥堵越发严重,公共交通虽然可以缓解交通压力,但无法解决“最后一公里”问题。公共自行车作为新型的交通方式,以其灵活便捷、易与其他公共交通方式连接的特性,可以有效弥补传统交通方式的不足。
公共自行车主要服务于短距离出行,特别是作为公共交通的换乘方式解决远距离出行问题。因此,许多学者对公共自行车与公共交通的接驳展开研究。朱从坤, 等[
从上述研究可知,目前对公共自行车的接驳研究主要集中为在轨道交通方面,较少考虑公共自行车与公交车的接驳问题,并且对公共自行车系统的网络规划主要考虑站点的布局,很少考虑自行车道的规划。基于上述研究现状,笔者从公共自行车与公交车接驳的角度,对公共自行车系统的站点选址布局和专用道设置问题进行研究。首先构建模型,在比较传统模型基础上,通过分析问题特性基于禁忌搜索的智能算法求解问题。最后,通过大量仿真实验,验证模型及算法的有效性,通过敏感性分析实验进一步为构建合理公共自行车网络提供参考依据。
研究公共自行车站点选址问题旨在公交站点和周围区域设置公共自行车站点,以解决公共交通的短距离接驳问题,满足出行者较长距离的出行。与现有自行车站点选址问题不同,研究自行车站点选址问题还考虑在自行车站点之间设置自行车道,提高公共自行车出行比率,保障自行车用户出行的安全性、舒适性和快捷性。因此,对基于公交车接驳的公共自行车站点选址及专用道设置问题进行研究,即在投资成本有限情况下,通过合理选址自行车站点和设置自行车专用道,最大化满足用户的出行需求。
为更好地研究自行车站点选址问题,做出如下假设。1)每个候选站点的自行车出行需求量已知。2)设置在2个公交站点处的公共自行车站点之间的距离不能小于一定的距离。3)为实现公共自行车的短距离接驳,设置在公交站点处的公共自行车站点和周围区域的公共自行车站点的距离不能超过最大距离。4)自行车专用道设置在公交站点和其周围的公共自行车站点之间。笔者考虑的公共自行车主要用于公共交通出行的末端接驳,因此自行车站点设置在公交站位置及周围临近区域。
为了清晰明确地构建问题模型,定义参数和变量如下。令
根据定义的参数和变量,可将公共自行车站点及车道选址优化问题构建如下模型
目标函数(1)为最大化满足自行车用户的需求。当点
将模型
显然模型
在研究公共自行车站点选址的基础上,还考虑自行车道的设置,它是一个
禁忌搜索算法作为一种高效的元启发式算法,在过去的几十年中被广泛成功应用于求解旅行商问题[
初始解由
当前解的邻域由一系列邻域解构成。这些邻域解是对当前解进行“移动”操作所获得。由于问题的3类变量属于不同层次的决策,所以移动操作涉及的对象不是当前解的全部变量,而仅仅是选址变量
根据上述定义,经过移动操作后可首先确定邻域解中设置自行车站点的公交站
这样,对于close或open移动,首先根据移动的定义确定设置自行车站点的公交站的位置,然后计算剩余资金,再根据贪婪思想按照性价比选择原则确定在公交站周围设置的自行车站点及自行车道。对于swap移动,可看成是close和open移动的复合,依次计算关闭、开放公交站位置的自行车站点后的资金变化,再根据剩余资金和性价比选择原则确定邻域解。
根据上述定义的3类移动,对当前解进行每一个移动操作,都可获得一个可行邻域解。其中,open移动可增加目标值,使得当前解向最优解的方向移动;close移动虽然会降低目标值,但是搜索的空间更广,易于跳出局部解。通过close和open2种移动的操作,使得设置自行车站点的公交站达到一个合适的数量。此外,swap移动通过调整设置自行车站点的公交站的集合,可使邻域解趋向最优解。
为进行下一次迭代,需要在邻域中选择最佳的邻域解,用其更新当前解。根据禁忌搜索的思想,在最近若干次迭代过程中的一部分邻域移动是禁忌的,避免搜索陷入局部最优。另一方面,搜索过程是寻找全局最优解,若邻域解优于当前最好解,即使它是禁忌的,可以使用特赦准则取消禁忌,选取该邻域解作为最佳,从而使得搜索趋近于全局最优解。因此在当前解的邻域中选择最佳的邻域解不能简单地通过比较目标值得到,还需要考虑邻域解的禁忌状态。
通常做法是将所有的邻域解按照目标值升序或降序排列,然后根据目标值以及禁忌状态选择最佳邻域解。尽管排序算法的时间复杂度是多项式的(通常为
3种邻域移动对是否在公交站处设置自行车站点(即变量
与大多数迭代搜索类似,当算法完成最大迭代次数即被终止。此外,若当前最好解在一定迭代次数内未改进,为避免搜索陷入局部最优,对算法进行初始化,生成新的当前解。
综上基于禁忌搜索的求解方法总结为如下算法1。
算法1:
1) 初始化:设置当前最好解未改进的最大迭代次数impMax、未改进当前次数impIter=0、禁忌表;生成初始解,并赋给当前解、当前最优解。
2) 令impIter=impIter + 1。
3) 由当前解定义邻域移动,并求得邻域解及其目标值。
4) 对每一个邻域解:
a) 如果邻域解优于当前最优解:更新当前最优解、最佳邻域解。令impIter=0。
b) 如果当前最优解未被更新:如果邻域解优于最佳邻域解且为非禁忌状态,则更新最佳邻域解。
5) 更新当前解、禁忌表。
6) 如果impIter > impMax,重新产生当前解。
7) 如果满足终止条件,输出当前最好解以及目标值;否则转入步骤2。
采用MATLAB 2016a编写禁忌搜索算法,通过大量算例来评估算法1。仿真实验的计算机环境为Intel(R)Core(TM) i5-4590 CPU,8 GB RAM,Windows 7系统。实验共测试28组(5个/组)随机产生的算例,实验结果均为每组5个算例的均值。
为表述方便,用|
模型P和P′结果比较
Comparison results of model P and P′
Set | | |
| |
M | TP | ZP | TP′ | ZP′ |
1 | 5 | 21 | 100 | 1 | 123 | 1 | 101 |
2 | 10 | 43 | 200 | 1 | 280 | 1 | 255 |
3 | 15 | 63 | 300 | 2 | 396 | 2 | 364 |
4 | 20 | 80 | 400 | 3 | 546 | 13 | 470 |
5 | 25 | 105 | 600 | 4 | 893 | 14 | 753 |
6 | 30 | 124 | 700 | 8 | 1017 | 31 | 850 |
AVG | 3 | 543 | 10 | 466 |
基于禁忌搜索的算法实验结果
Computational results of tabu search based algorithm
Set | | |
| |
TP | ZP | TA | ZA | GA | TG | ZG | GG | TT | ZT | GT | |||||
7 | 30 | 124 | 700 | 8 | 1 017 | 16 | 987 | 2.99 | 38 | 991 | 2.58 | 8 | 1 007 | 0.98 | ||||
8 | 35 | 144 | 800 | 9 | 1 125 | 20 | 1 097 | 2.51 | 46 | 1 107 | 1.58 | 10 | 1 116 | 0.80 | ||||
9 | 40 | 163 | 1 000 | 25 | 1 388 | 28 | 1 353 | 2.52 | 57 | 1 360 | 2.02 | 13 | 1 377 | 0.79 | ||||
10 | 45 | 185 | 1 200 | 22 | 1 697 | 35 | 1 649 | 2.84 | 71 | 1 658 | 2.30 | 16 | 1 690 | 0.41 | ||||
11 | 50 | 209 | 1 500 | 26 | 2 122 | 43 | 2 043 | 3.74 | 85 | 2 062 | 2.84 | 21 | 2 109 | 0.61 | ||||
12 | 55 | 236 | 1 600 | 28 | 2 198 | 54 | 2 100 | 4.47 | 102 | 2 106 | 4.19 | 26 | 2 183 | 0.68 | ||||
13 | 60 | 247 | 1 800 | 41 | 2 539 | 64 | 2 432 | 4.21 | 114 | 2 437 | 4.03 | 30 | 2 525 | 0.55 | ||||
AVG | 23 | 1 727 | 37 | 1 666 | 3.33 | 73 | 1 674 | 2.79 | 18 | 1 715 | 0.69 | |||||||
14 | 65 | 263 | 2 000 | — | — | 72 | 2 605 | — | 125 | 2 619 | — | 37 | 2 692 | — |
设置自行车站点的最短距离(
Impact on users' demand by largest distance between bus station and bike station
Set | | |
|||||||||
| |
| |
| |
||||||||
15 | 40 | 1 000 | 2.0 | 1 270 | 4.5 | 1 377 | 6.0 | 866 | ||
16 | 50 | 1 500 | 1.9 | 1 769 | 4.8 | 2 109 | 6.0 | 1 342 | ||
17 | 60 | 1 800 | 2.0 | 2 098 | 4.1 | 2 525 | 6.0 | 1 613 | ||
18 | 70 | 2 200 | 2.0 | 2 748 | 4.1 | 2 843 | 6.0 | 1 854 | ||
19 | 80 | 2 500 | 2.1 | 3 065 | 4.1 | 3 452 | 6.0 | 1 854 | ||
20 | 90 | 2 800 | 2.0 | 3 352 | 4.1 | 3 997 | 6.0 | 2 167 | ||
21 | 100 | 3 200 | 2.0 | 3 755 | 4.0 | 4 209 | 6.0 | 2 761 | ||
AVG | 2 580 | 2 930 | 1 780 |
建设自行车道的成本(
Impact on users' demand by construction cost of bike lanes
Set | | |
| |
||||||||||
ZT | CL | CB | pL | ZT | CL | CB | pL | |||||
22 | 40 | 163 | 1 000 | 1 360 | 304 | 696 | 0.30 | 1 228 | 230 | 770 | 0.23 | |
23 | 50 | 209 | 1 500 | 2 062 | 432 | 1 068 | 0.29 | 1 918 | 323 | 1 177 | 0.22 | |
24 | 60 | 247 | 1 800 | 2 521 | 490 | 1 310 | 0.27 | 2 287 | 404 | 1 396 | 0.22 | |
25 | 70 | 287 | 2 200 | 2 957 | 614 | 1 586 | 0.28 | 2 722 | 516 | 1 684 | 0.23 | |
26 | 80 | 328 | 2 500 | 3 288 | 727 | 1 773 | 0.29 | 3 025 | 673 | 1 827 | 0.27 | |
27 | 90 | 362 | 2 800 | 3 816 | 792 | 2 008 | 0.28 | 3 492 | 741 | 2 059 | 0.26 | |
28 | 100 | 410 | 3 200 | 4 277 | 860 | 2 340 | 0.27 | 3 954 | 806 | 2 394 | 0.25 | |
AVG | 2 897 | 0.28 | 2 661 | 0.24 |
为验证设置自行车专用道的有效性,实验首先采用软件Lingo对非线性模型P和P′进行求解比较,实验结果如
为评估基于禁忌搜索的算法1的性能,实验2不仅与Lingo比较8组不同规模的算例求解结果,还与常见的模拟退火(SA, simulate anneal)、遗传算法(GA, genetic algorithm)进行比较。为公平地比较各方法,SA、GA的搜索迭代次数与算法1大体相同,且SA、GA的初始解(种群)、迭代搜索的算子操作采用算法1中类似操作。令
为进一步验证模型
此外,实验还对自行车道的建设成本
实验结果如
近年来,公共自行车系统得到较快发展,公共自行车系统的网络规划问题得到广泛关注。从“公共自行车公交车”接驳的角度,研究公共自行车的站点选址及自行车道设置的网络规划问题。通过运用运筹优化的思想,构建自行车网络非线性规划模型,通过决策公共自行车站点选址和站点间自行车道的设置,使得规划的自行车网络最大化满足自行车用户的需求。通过MATLAB软件实现基于禁忌搜索算法。并通过大量仿真实验表明,构建考虑自行车专用道的选址模型优于仅考虑站点布局的选址模型;在求解问题的计算时间和目标值方面,设计基于禁忌搜索的算法优于规划软件Lingo、模拟退火算法和遗传算法,充分验证模型和算法的可靠性和有效性。此外,通过对模型参数进行敏感性分析发现:a)公共自行车接驳公交的距离要在合理距离范围内以提高用户需求;b)自行车道是公共自行车网络的重要部分,合理规划站点与车道的投资比例,能够满足更多用户的出行需求。
公共自行车的发展促进低碳出行的发展,在后续研究中,可将减少碳排放因素考虑到公共自行车网络构建中,使得公共自行车系统更加符合可持续发展的目标。
朱从坤, 韩晓玉, 何承韡.基于城市轨道交通接驳的公共自行车租赁点规模确定方法[J].城市轨道交通研究, 2018, 21(9): 23-25.
ZHU Congkun, HAN Xiaoyu, HE Chengwei. On the scale of public bicycle rental point based on rail transit connection mode[J]. Urban Mass Transit, 2018, 21(9): 23-25. (in Chinese)
周强, 吴戈, 孙瀚.作为地铁接驳手段的公共自行车使用特性分析[J].交通运输系统工程与信息, 2015, 15(3): 179-184.
ZHOU Qiang, WU Ge, SUN Han. Characteristics of public bicycle as means of access/egress for metro[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(3): 179-184.(in Chinese)
甘勇华.自行车与城市轨道交通的换乘衔接[J].城市轨道交通研究, 2007, 10(4): 8-10.
GAN Yonghua. On the transfer between bicycle and urban mass transit[J]. Urban Mass Transit, 2007, 10(4): 8-10.(in Chinese)
陈景旭, 王炜, 陈学武, 等.轨道交通站点公共自行车租赁点布局研究[J].武汉理工大学学报(交通科学与工程版), 2013, 37(6): 1206-1210.
CHEN Jingxu, WANG Wei, CHEN Xuewu, et al. Research on the layout of bike rental stations around a railway station[J]. Journal of Wuhan University of Technology(Transportation Science & Engineering), 2013, 37(6): 1206-1210.(in Chinese)
He L, Li X H, Chen D W. An optimization model of the layout of public bike rental stations based on B+R mode[M]. Cham: Springer International Publishing, 2013: 1341-1348.
Chen Q, Sun T Y. A model for the layout of bike stations in public bike-sharing systems[J]. Journal of Advanced Transportation, 2015, 49(8): 884-900.
Frade I, Ribeiro A. Bike-sharing stations: A maximal covering location approach[J]. Transportation Research Part A: Policy and Practice, 2015, 82: 216-227.
韩强, 周勇.基于双层规划的一类自行车专用道路网络设计问题[J].系统科学与数学, 2015, 35(11): 1316-1326.
HAN Qiang, ZHOU Yong. Bike lane network design problem based on bi-level programming[J]. Journal of Systems Science and Mathematical Sciences, 2015, 35(11): 1316-1326.(in Chinese)
Lin J R, Yang T H, Chang Y C. A hub location inventory model for bicycle sharing system design: formulation and solution[J]. Computers & Industrial Engineering, 2013, 65(1): 77-86.
Ali Askari E, Bashiri M. Design of a public bicycle-sharing system with safety[J]. Computational and Applied Mathematics, 2017, 36(2): 1023-1041.
Li H T, Alidaee B. Tabu search for solving the black-and-white travelling salesman problem[J]. Journal of the Operational Research Society, 2016, 67(8): 1061-1079.
Basu S, Sharma M, Ghosh P S. Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem[J]. INFOR: Information Systems and Operational Research, 2017, 55(2): 134-158.
Ho S C. An iterated tabu search heuristic for the single source capacitated facility location problem[J]. Applied Soft Computing, 2015, 27: 169-178.
Abyazi-Sani R, Ghanbari R. An efficient tabu search for solving the uncapacitated single allocation hub location problem[J]. Computers & Industrial Engineering, 2016, 93: 99-109.
杨珺, 冯鹏祥, 孙昊, 等.电动汽车物流配送系统的换电站选址与路径优化问题研究[J].中国管理科学, 2015, 23(9): 87-96.
YANG Jun, FENG Pengxiang, SUN Hao, et al. Battery exchange station location and vehicle routing problem in electric vehicles distribution system[J]. Chinese Journal of Management Science, 2015, 23(9): 87-96.(in Chinese)
赵燕伟, 钱振宇, 张景玲, 等.考虑碳排放的选址-路径问题研究[J].浙江工业大学学报, 2018, 46(5): 550-557.
ZHAO Yanwei, QIAN Zhenyu, ZHANG Jingling, et al. Research on location routing problem considering carbon emissions[J]. Journal of Zhejiang University of Technology, 2018, 46(5): 550-557.(in Chinese)
柴森霖, 白润才, 刘光伟, 等.基于改进遗传算法的露天矿运输路径优化[J].重庆大学学报, 2018, 41(2): 87-95.
CHAI Senlin, BAI Runcai, LIU Guangwei, et al. Open-pit path optimization based on improved genetic algorithm[J]. Journal of Chongqing University, 2018, 41(2): 87-95.(in Chinese)
李建平, 宫耀华, 卢爱平, 等.改进的粒子群算法及在数值函数优化中应用[J].重庆大学学报, 2017, 40(5): 95-103.
LI Jianping, GONG Yaohua, LU Aiping, et al. Application of improved particle swarm optimization to numerical function optimization[J]. Journal of Chongqing University, 2017, 40(5): 95-103.(in Chinese)
Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computers & Operations Research, 1986, 13(5): 533-549.