基于代理模型辅助NSGA-Ⅱ算法的地铁接驳公交优化

doi:10.12141/j.issn.1000-565X.230595

摘要/Abstract

摘要：

城市轨道交通与地面公交之间的便利衔接是满足居民多元化出行需求，促进城市公共交通系统发展的关键。现有研究在建立公交线路优化模型时缺少对一些重要微观指标的考虑，例如高峰期需等待多班公交的比例和车内拥挤度等。同时对线路运营中随机性和异质性要求的考虑也存在不足，导致其在实际应用中表现欠佳。为解决上述问题，该文从公交的服务过程出发，以乘客出行成本与企业成本最小化为目标，建立考虑运行速度、车辆类型、发车频率、线路票价、车辆拥挤程度、线路线型等影响因素的优化模型，使用非支配排序遗传算法（NSGA-Ⅱ）进行模型求解，并针对遗传操作部分进行改进。同时为提高求解精度，设计了一种微观仿真算法对解进行评估。在此基础上，采用Kriging代理模型进行辅助计算以提高算法求解效率。最后，以深圳市地铁公交接驳为例，采集地铁与公交IC卡刷卡数据，对提出的算法进行验证。同时，进一步对线路票价、运行速度、运营车型以及客流大小等因素进行了灵敏度分析，依据分析结果提出了运营线路的改善建议。结果表明，该算法相较于传统NSGA-Ⅱ算法能在相同的求解时间下得到更好的线路优化方案，方案平均节省约35.49%的总成本，且迭代速度提高26.94%。由此可见，该文提出的地铁接驳公交优化方法对提升接驳效率与运营水平均具有实际意义。

关键词: 城市交通, 接驳公交, 多目标优化, 线路设计, 代理模型

Abstract:

The connection between urban rail transit and bus transit is the key to meet the various urban travel demand and to promote the development of urban public transportation system. Existing studies lack the consideration of some important micro-indicators, such as the ratio of waiting for multiple buses during peak hours and the level of congestion inside the bus, when constructing the optimization model. Additionally, there is a lack of consideration for the stochastic and heterogeneous requirements in route operation, which results in poor performance in practical applications. To address these issues, this study firstly established an optimization model based on the service process of the bus transit, with the objective of minimizing the travel cost of passengers and the cost of enterprises. The model considers the influencing factors such as operating speed, vehicle type, departure frequency, route fare, vehicle crowdedness, and route line type and it is solved by the non-dominated sorting genetic algorithm (NSGA-Ⅱ), in which the genetic operation part is improved. Furthermore, a microscopic simulation algorithm was designed to evaluate the solution in order to improve the accuracy of the model solution. Accordingly, a Kriging surrogate model was used to assist the calculation to improve the solution efficiency of the algorithm. Finally, taking the connection between metro and bus system in Shenzhen city as an example, the proposed algorithm was validated with the IC card data collected in metro and bus system. The sensitivity analysis was conducted for the factors of route fare, operating speed, operating mode and passenger volume, and the operating improvement was proposed based on the analysis results. The results demonstrate that the algorithm produces superior route solutions compared to the conventional NSGA-Ⅱ, with the same solving time. There is a 35.49% reduction in total cost and a notable 26.94% increase in the iteration speed. The optimization method for connecting between metro and bus transit proposed in this study has practical significance in improving connecting efficiency and operational level.

Key words: urban transportation, feeder bus, multi-objective optimization, route design, surrogate model

中图分类号:

U491.1⁺7

唐进君, 任茂昕, 李志涛, 等. 基于代理模型辅助NSGA-Ⅱ算法的地铁接驳公交优化[J]. 华南理工大学学报(自然科学版), 2024, 52(11): 95-105.

TANG Jinjun, REN Maoxin, LI Zhitao, et al. Optimization of Metro Feeder Bus Routes Based on Surrogate-Assisted NSGA-Ⅱ Algorithm[J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(11): 95-105.

图/表 10

图1

表1

变量和集合定义"

类别	符号	释义	单位
集合	$L$	方案所含线路集合
	$D$	公交站点集合
	$U$	轨道站点集合
	$K$	$K = 1,2, ⋯, m$ ，单条线路站点集合
	$B$	$B = 1,2, ⋯, n$ ，单条线路使用车辆集合
参数	$t$	研究的时间长度	s
	$V$	接驳公交平均车速	km/h
	$c i$	车辆i最大载客数	人次
	$S i$	车辆i最大座位数	人次
	$λ k$	第k个站的乘客平均到站率与离站率	人次/h
	$d i, j$	站点i与j之间的距离	km
	$[f m i n, f m a x]$	接驳线路应满足的最小与最大发车频率	s/车次
	$[l m i n, l m a x]$	接驳线路应满足的最短与最长线路长度	km
	$μ w$	乘客候车单位时间成本	元/s
	$μ I$	乘客车上单位时间成本	元/s
	$μ c$	无座乘客车上单位时间拥挤成本	元/s
	$μ g$	车辆公里燃料成本	元/km
	$μ o t$	企业单位时间运营成本	元/s
	$μ f$	乘客单次乘坐公交票价	元
	$t (i) k$	第 $i$ 辆到达站点 $k$ 的公交运行时间	s
决策变量	$x i j l$	0~1决策变量，站点 $i$ 和 $j$ 在第 $l$ 条线路上且相邻为1，否则为0
	$y l i$	0~1决策变量，站点 $i$ 在第 $l$ 条线路上为1，否则为0
	$m k l$	0~1决策变量，站点 $k$ 是第 $l$ 条线的起点或终点时为1，否则为0
	$l k$	连续变量，接驳线路 $k$ 的线路长度	km
	$f l$	连续变量，接驳公交线路 $l$ 的发车频率	s/车次
	$p s r l$	连续变量，接驳线路 $l$ 上的有效服务率	%

表1

图2

图3

图4

表2

图5

图6

表3

图7

参考文献 32

1	陈廷照，陈艳艳，王子理，等．“轨道交通微中心”理念下的慢行影响区范围确定方法［J］．华南理工大学学报（自然科学版），2022，50（7）：56-65.
	CHEN Tingzhao， CHEN Yanyan， WANG Zili，et al ．Methods of determining the range of non-motorized travel influence area under the concept of “metro transit micro-center”［J］．Journal of South China University of Technology （Natural Science Edition），2022，50（7）：56-65.
2	SAM E F， DANIELS S， BRIJS K，et al ．Modelling public bus/minibus transport accident severity in Ghana［J］．Accident Analysis and Prevention，2018，119：114-121.
3	DOU X， WANG H， MENG Q ．Parallel shuttle bus service design for planned mass rapid transit shutdown：the Singapore experience［J］．Transportation Research Part C，2019，108（C）：340-356.
4	陈嘉超，宋程．基于聚类分析法的地铁与常规公交换乘客流分析［J］．科技和产业，2018，18（5）：100-104.
	CHEN Jiachao， SONG Cheng ．Analysis on the transfer passenger flow between bus and subway system based on cluster analysis［J］．Science Technology and Industry，2018，18（5）：100-104.
5	石兆，符卓．配送选址-多车型运输路径优化问题及求解算法［J］．计算机科学，2015，42（5）：245-250.
	SHI Zhao， FU Zhuo ．Distribution location-routing problem of heterotypic vehicles and its algorithms［J］．Computer Science，2015，42（5）：245-250.
6	LIANG J， WU J， GAO Z，et al ．Bus transit network design with uncertainties on the basis of a metro network：a two-step model framework［J］．Transportation Research Part B：Methodological，2019，126：115-138.
7	BORNDÖRFER R， GRÖTSCHEL M， PFETSCH M E ．A column-generation approach to line planning in public transport［J］．Transportation Science，2007，41（1）：123-132.
8	IBARRA-ROJAS O J， DELGADO F， GIESEN R，et al ．Planning，operation，and control of bus transport systems：a literature review［J］．Transportation Research Part B：Methodological，2015，77：38-75.
9	SUMAN H K， BOLIA N B ．Improvement in direct bus services through route planning［J］．Transport Policy，2019，81：263-274.
10	ZHENG M N， ZHOU R X， LIU S S，et al ．Route design model of multiple feeder bus service based on existing bus lines［J］．Journal of Advanced Transportation，2020，2020（8）：885387/1-12.
11	ALMASI M H， SADOLLAH A， KANG S，et al ．Optimization of an improved intermodal transit model equipped with feeder bus and railway systems using metaheuristics approaches［J］．Sustainability，2016，8（6）：537/1-27.
12	PATTNAIK S B， MOHAN S， TOM V M ．Urban bus transit route network design using genetic algorithm［J］．Journal of Transportation Engineering，1998，124（4）：368-375.
13	SHRIVASTAVA P， OMAHONY M ．A model for development of optimized feeder routes and coordinated schedules—a genetic algorithms approach［J］．Transport Policy，2006，13（5）：413-425.
14	XIONG J， HE Z， GUAN W，et al ．Optimal timetable development for community shuttle network with metro stations［J］．Transportation Research Part C：Emerging Technologies，2015，60：540-565.
15	邓连波，高伟，赖天珍，等．基于换乘网络的城市轨道交通关联公交接驳线网优化［J］．铁道科学与工程学报，2012，9（6）：77-83.
	DENG Lian-bo， GAO Wei， LAI Tian-zhen，et al ．Optimal design of feeder-bus network related to urban rail transit based on transfer network［J］．Journal of Railway Science and Engineering，2012，9（6）：77-83.
16	JIANG S， GUAN W， YANG L，et al ．Feeder bus accessibility modeling and evaluation［J］．Sustainability，2020，12（21）：8942/1-17.
17	CAO Y， JIANG D， WANG S ．Optimization for feeder bus route model design with station transfer［J］．Sustainability，2022，14（5）：2780/1-15.
18	韩月一，王登忠，王如杰，等．城市地铁站点接驳公交多目标优化方法［J］．交通运输工程与信息学报，2023，21（1）：80-93.
	HAN Yueyi， WANG Dengzhong， WANG Rujie，et al ．Multi-objective optimization method for connecting buses in urban subway stations［J］．Journal of Transportation Systems Engineering and Information，2023，21（1）：80-93.
19	BADIA H， JENELIUS E ．Design and operation of feeder systems in the era of automated and electric buses［J］．Transportation Research Part A：Policy and Practice，2021，152：146-172.
20	赵传林，孙正一．考虑乘客异质性的公交运行模型仿真研究［J］．计算机仿真，2023，40（7）：148-153.
	ZHAO Chuan-lin， SUN Zheng-yi ．Simulation study of bus operation model considering passenger heterogeneity［J］．Computer Simulation，2023，40（7）：148-153.
21	SEBASTIANI M T， LÜDERS R， FONSECA K V O ．Evaluating electric bus operation for a real-world BRT public transportation using simulation optimization［J］．IEEE Transactions on Intelligent Transportation Systems，2016，17（10）：2777-2786.
22	宋俪婧，白同舟，贺玉龙，等．基于混合整数非线性规划的接驳公交优化模型［J］．交通运输系统工程与信息，2022，22（3）：104-111.
	SONG Li-jing， BAI Tong-zhou， HE Yulong，et al ．Feeder bus routes and frequency optimization based on mixed integer nonlinear programming［J］．Journal of Transportation Systems Engineering and Information Technology，2022，22（3）：104-111.
23	HADAS Y， SHNAIDERMAN M ．Public-transit frequency setting using minimum-cost approach with stochastic demand and travel time［J］．Transportation Research Part B：Methodological，2012，46（8）：1068-1084.
24	张鑫．考虑舒适度的公交线网优化设计［D］．广州：华南理工大学，2018.
25	谭佳慧．接驳城市轨道的多模式公交线路优化研究［D］．济南：山东建筑大学，2022.
26	DEB K， PRATAP A， AGARWAL S，et al ．A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］．IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.
27	SZETO W Y， WU Y Z， HO S C ．An artificial bee colony algorithm for the capacitated vehicle routing problem［J］．European Journal of Operational Research，2011，215（1）：126-135.
28	王伟仲．基于代理模型的高代价问题优化算法［D］．广州：广东工业大学，2021.
29	任艳军．城市地铁与常规公交的协同研究——以青岛市为例［D］．西安：长安大学，2019.
30	刘珊珊．轨道接驳型社区公交线路优化方法研究［D］．南京：东南大学，2020.
31	宗芳，隽志才，张慧永，等．出行时间价值计算及应用研究［J］．交通运输系统工程与信息，2009，9（3）：114-119.
	ZONG Fang， JUAN Zhi-cai， ZHANG Hui-yong，et al ．Calculation and application of value of travel time［J］．Journal of Transportation Systems Engineering and Information Technology，2009，9（3）：114-119.
32	陈维亚，李泽宇，张衡鹏，等．智轨列车与常规公交共线组合发车间隔优化［J］．铁道科学与工程学报，2022，19（10）：2833-2841.
	CHEN Weiya， LI Zeyu， ZHANG Hengpeng，et al ．Optimization of the combined departure interval for joint operation of ART and conventional bus［J］．Journal of Railway Science and Engineering，2022，19（10）：2833-2841.

算法类型	平均乘客成本/元	平均企业成本/元	Pareto解个数	平均单次迭代时间/s
NSGA-Ⅱ	2 423.72	93.81	5	29.53
KRG-NSGA-Ⅱ	2 063.70	-2.79	3	21.50
MMM-NSGA-Ⅱ	2 269.85	46.48	3	29.82
KRG-MMM-NSGA-Ⅱ	1 679.10	-55.00	2	21.86

线路序号	接驳线路	线路线型	发车频率/（s·车次^-1）	客流需求/（人·h^-1）	线路长度/m	有效服务率/%
线路1	27-23-2-13-6-27	环型	720	30	3 222.261	100.00
线路2	28-26-20-24-10	放射型	780	40	3 491.666	97.96
线路3	28-19-3-17-7-21-1	放射型	360	97	5 097.731	91.21
线路4	28-15-9-4-25	放射型	840	51	7 096.012	100.00
线路5	28-18-22-8-12-28	环型	900	44	9 264.829	100.00
线路6	27-11-16-5-14-27	环型	840	42	7 924.427	98.43

[1]	何庆龄, 裴玉龙, 董春彤, 等. 基于混合策略改进ASO-LSSVM的风险驾驶行为分类识别[J]. 华南理工大学学报(自然科学版), 2024, 52(9): 131-141.
[2]	翁剑成, 吴明珠, 魏瑞聪, 等. 多因素协同的大型活动场馆周边路段速度预测[J]. 华南理工大学学报(自然科学版), 2024, 52(8): 34-44.
[3]	苏跃江, 温惠英, 袁敏贤, 吴德馨, 周芦芦, 漆巍巍. 基于居民属性数据的出行碳排放预测模型[J]. 华南理工大学学报(自然科学版), 2024, 52(8): 23-33.
[4]	张跃明, 李天宇, 纪姝婷. 摆线针轮减速机参数对传动效率的影响与参数优化[J]. 华南理工大学学报(自然科学版), 2024, 52(4): 77-87.
[5]	杨亚璪, 翁唐政. 时空约束对运动出行的影响[J]. 华南理工大学学报(自然科学版), 2024, 52(2): 113-123.
[6]	柳宁, 华天标, 王高, 等. 面向部分工序无序加工的柔性作业车间批量调度方法[J]. 华南理工大学学报(自然科学版), 2024, 52(10): 51-63.
[7]	庄焱, 董春娇, 米雪玉, 等. 基于改进网络核密度和负二项回归的事故黑点鉴别[J]. 华南理工大学学报(自然科学版), 2024, 52(1): 119-126.
[8]	赵小梅, 郝郭宇, 牛晓婧, 等. 不同降雨量下基于宏观基本图的边界控制策略[J]. 华南理工大学学报(自然科学版), 2024, 52(1): 72-82.
[9]	王学武, 方俊宇, 高进, 等. 基于改善解集分布性的多目标优化[J]. 华南理工大学学报(自然科学版), 2023, 51(8): 137-148.
[10]	陈小鸿, 田田甜, 张华. 城市居民活动韧性——新冠肺炎疫情期间轨道客流恢复的实证[J]. 华南理工大学学报(自然科学版), 2023, 51(7): 109-119.
[11]	李树勋, 胡迎港, 李成, 等. 基于代理模型的轴流式调节阀阀体型线优化[J]. 华南理工大学学报(自然科学版), 2023, 51(3): 41-52.
[12]	刘国勇, 张文鹏, 张铜鑫, 等. 大幅面SLM成型仓结构优化及其流场特性[J]. 华南理工大学学报(自然科学版), 2023, 51(12): 53-63.
[13]	胡兴华, 陈兴辉, 汪然, 等. 随机特性下考虑碳排放的公交优先控制优化模型[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 160-170.
[14]	许伦辉, 余佳芯, 裴明阳, 等. 基于几何路网结构和强化学习的车辆重定位策略[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 99-109.
[15]	沈羽桐, 李明, 崔志勇, 等. 混合服务模式车辆资源多时段分配方法研究[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 89-98.