Coordinated optimization of operation routes and schedules for responsive feeder transit under simultaneous pick-up and delivery mode
-
摘要: 研究了同时接送模式下响应型接驳公交运行路径与车辆调度的协调优化问题, 考虑乘客出行时间窗的个性化, 构建了基于乘客而不是基于途经需求点的车辆路径表示方法; 综合车辆发车和行驶成本、车辆早到和晚到的惩罚成本、票价收入构建了表征系统效益的目标函数, 并以车辆容量、乘客时间窗、车辆运行时间、车辆保有量、发车时间等为约束, 构建了发车间隔、发出车型与车辆路径的一体化优化模型; 针对一体化优化模型的特点, 设计了双遗传算法, 其中染色体为多链编码结构, 染色体交叉方式包含个体内、个体间交叉2种方式; 为了验证同时接送模式的优越性、一体化优化模型及算法的有效性, 进行了算例分析, 对比了同时接送模式与单独接和单独送模式的计算结果, 分析了车辆运行车速、单程运行时间限制、车型比例对响应型接驳公交运营效率的影响。计算结果表明: 在给定的相同乘客需求下, 与单独送和单独接模式相比, 同时接送模式发车次数减少了1次, 所需车辆数减少了2辆, 平均座位利用率提高了8.3%, 运送单位乘客的平均车辆行驶距离降低了11.0%, 运行成本降低了15.9%, 因此, 同时接送模式有效地提高了运营效率; 同时接送模式下, 运行车速、单程运行时间限制、小型车比例分别在基准值附近上下波动15.0%、15.0%、12.5%时, 发车次数、座位平均利用率、目标函数值的最大变化率分别达到了20.0%、15.7%、27.1%, 这些参数对系统运营效率均有显著影响。Abstract: The coordinated optimization problem of operation routes and vehicle schedules for responsive feeder transit under the simultaneous pick-up and delivery mode was studied. The vehicle route representation method based on passengers rather than demand points was devised by considering the personalization of passenger travel time window. The objective function that represents system benefit was constructed by combining the costs of vehicle departure and travel, penalty costs of vehicle early and late arrival, and ticket fares. The vehicle capacity, passenger time window, vehicle running time, vehicle holding quantity and departure time were all taken as constraints, and the integrated optimization model of departure interval, vehicle type and running route was constructed. The double genetic algorithm was designed to solve the integrated optimization model. In this algorithm, the chromosome was coded by multi-chain coding structure, and the chromosome chiasma included two ways of inter-individual and intra-individual. In order to validate the superiority of the simultaneous pick-up and delivery mode, and the effectiveness of the integrated optimization model and the algorithm, several examples were designed to compare the calculation results of the simultaneous pick-up and delivery mode and the separate pick-up and deliver mode. The effects of vehicle speed, single trip running time limit and vehicle composition on the operation efficiency of responsive feeder transit were analyzed. Calculation result shows that under the same passenger demand, compared with the separate pick-up and deliver mode, under the simultaneous pick-up and delivery mode, the departure times reduce by 1, the number of required vehicles reduce by 2, the average seat utilization rate increases by 8.3%, the average vehicle distance required to transport unit passenger reduces by 11.0%, and the operation cost reduces by 15.9%. Therefore, the simultaneous pick-up and delivery mode can effectively improve the operation efficiency. At the same time, under the simultaneous pick-up and delivery mode, when vehicle speed, single trip running time limit, and small vehicle ratio fluctuate by 15.0%, 15.0%, and 12.5% near the reference values, respectively, the maximum change rate of the departure times, the average seat utilization rate, and the objective value reach 20.0%, 15.7%, and 27.1%, respectively, therefore, these parameters have a significant impact on the system operating efficiency.
-
表 2 乘客位置与时间窗
Table 2. Locations and time windows of passengers
乘客编号 乘客类型 站点编号 bi ai Dpkyi 乘客编号 乘客类型 站点编号 bi ai Dpkyi 1 1 20 7:08 7:13 无要求 41 1 13 7:13 7:18 无要求 2 1 20 7:19 7:23 无要求 42 1 13 7:24 7:29 无要求 3 1 20 7:38 7:43 无要求 43 1 13 7:35 7:40 无要求 4 1 20 7:19 7:24 无要求 44 1 5 7:11 7:16 无要求 5 1 21 7:06 7:10 无要求 45 -1 5 7:20 7:25 7:04 6 1 21 7:14 7:18 无要求 46 1 5 7:30 7:35 无要求 7 1 21 7:07 7:12 无要求 47 1 5 7:42 7:47 无要求 8 -1 22 7:23 7:28 7:06 48 -1 5 7:40 7:45 7:16 9 1 22 7:18 7:22 无要求 49 1 5 7:28 7:33 无要求 10 1 22 7:33 7:37 无要求 50 -1 6 7:18 7:23 7:03 11 -1 22 7:25 7:30 7:08 51 1 6 7:19 7:23 无要求 12 1 22 7:42 7:47 无要求 52 1 6 7:33 7:39 无要求 13 -1 19 7:09 7:14 7:00 53 -1 6 7:55 7:60 7:00 14 1 19 7:20 7:25 无要求 54 1 7 7:07 7:12 无要求 15 1 19 7:36 7:40 无要求 55 1 7 7:35 7:40 无要求 16 1 16 7:05 7:10 无要求 56 1 7 7:19 7:24 无要求 17 -1 16 7:22 7:27 7:05 57 1 4 7:10 7:14 无要求 18 1 16 7:07 7:12 无要求 58 1 4 7:18 7:23 无要求 19 -1 16 7:25 7:30 7:07 59 -1 4 7:52 7:57 7:20 20 1 16 7:49 7:53 无要求 60 1 4 7:37 7:42 无要求 21 -1 17 7:23 7:28 7:05 61 1 1 7:05 7:10 无要求 22 1 17 7:17 7:22 无要求 62 1 1 7:07 7:12 无要求 23 -1 17 7:52 7:57 7:24 63 1 1 7:34 7:39 无要求 24 1 17 7:33 7:37 无要求 64 1 2 7:18 7:22 无要求 25 1 18 7:12 7:17 无要求 65 1 2 7:42 7:47 无要求 26 1 18 7:26 7:31 无要求 66 1 3 7:14 7:19 无要求 27 1 18 7:41 7:46 无要求 67 -1 3 7:16 7:21 7:02 28 1 18 7:38 7:43 无要求 68 1 3 7:50 7:55 无要求 29 1 18 7:27 7:31 无要求 69 1 8 7:05 7:10 无要求 30 -1 23 7:25 7:30 7:06 70 -1 8 7:23 7:27 7:06 31 1 23 7:16 7:20 无要求 71 1 14 7:16 7:21 无要求 32 1 23 7:37 7:42 无要求 72 1 14 7:30 7:35 无要求 33 1 23 7:09 7:14 无要求 73 1 14 7:23 7:28 无要求 34 1 24 7:39 7:43 无要求 74 1 15 7:40 7:45 无要求 35 1 24 7:24 7:29 无要求 75 -1 12 7:23 7:28 7:04 36 1 24 7:22 7:27 无要求 76 -1 12 7:14 7:19 7:00 37 -1 25 7:45 7:50 7:14 77 -1 12 7:40 7:45 7:20 38 1 25 7:37 7:41 无要求 78 1 10 7:07 7:12 无要求 39 -1 25 7:30 7:35 7:12 79 1 10 7:28 7:32 无要求 40 1 25 7:19 7:24 无要求 80 1 11 7:39 7:43 无要求 
下载: 导出CSV
表 3 同时接送模式下乘客的路径
Table 3. Passenger routes under simultaneous pick-up and delivery mode
发车时间 车辆编号 乘客路径 距离/km 累计乘客数 座位利用率/% 到达时间 7:09 A1 0-61-62-25-7-14-13-0 8.12 6 60 7:23 7:14 B1 0-76-51-26-6-5-42-40-38-0 17.24 8 53 7:44 7:16 A2 0-33-18-56-67-32-3-0 17.60 6 60 7:46 7:20 A3 0-58-45-66-50-44-49-79-78-28-10-12-0 13.69 12 120 7:45 7:20 A4 0-4-2-73-71-17-80-0 9.96 6 60 7:39 7:23 B2 0-16-1-75-72-64-47-65-46-68-0 18.35 9 60 7:55 7:25 A1 0-35-36-54-70-69-52-60-57-55-43-27-0 13.48 11 110 7:46 7:30 B3 0-21-24-19-30-11-39-8-31-34-0 20.53 9 60 8:15 7:30 A5 0-23-15-59-37-53-22-0 22.18 6 60 8:08 7:40 A4 0-63-29-74-77-48-20-41-0 19.96 7 70 8:14
下载: 导出CSV
表 4 单独送模式下乘客的路径
Table 4. Passenger routes under separate delivery mode
发车时间 车辆编号 乘客路径 距离/km 累计载客数 座位利用率/% 到达时间 7:12 A1 0-67-70-11-39-8-13-30-0 14.73 7 70 7:42 7:24 A2 0-76-75-19-17-21-23-0 9.74 6 60 7:40 7:36 A3 0-77-45-48-59-53-37-50-0 12.79 7 47 8:03
下载: 导出CSV
表 5 单独接模式下乘客的路径
Table 5. Passenger routes under separate pick-up mode
发车时间 车辆编号 乘客路径 距离/km 累计载客数 座位利用率/% 到达时间 7:00 A4 0-5-7-18-2-22-42-36-0 19.20 7 70 7:38 7:03 A5 0-69-57-6-51-49-58-0 17.50 6 60 7:35 7:06 B1 0-44-62-66-79-33-43-54-0 17.77 7 47 7:45 7:10 B2 0-71-25-56-1-72-16-0 20.41 6 40 7:45 7:13 A6 0-31-41-29-73-0 14.88 4 40 7:41 7:15 A7 0-64-78-61-35-46-4-40-9-0 20.87 8 80 7:51 7:24 B3 0-26-32-15-28-27-14-12-10-3-24-20-74-0 13.66 12 80 7:58 7:38 A5 0-65-60-68-34-55-63-52-38-80-47-0 19.59 10 100 8:18
下载: 导出CSV
表 6 两种模式的比较
Table 6. Comparison of two modes
模式 发车次数 所需车辆数 座位平均利用率/% 运送单位乘客的平均行驶距离/km 目标值/元 同时接送模式 10 8 71 2.01 62.4 单独送和单独接模式 11 10 63 2.26 74.2
下载: 导出CSV
表 7 车速对运营效率的影响
Table 7. Impact of vehicle speed on operational efficiency
车速/(km·h-1) 发车次数 座位平均利用率/% 目标值/元 40.3 9 79 73.6 35.0 10 71 62.4 29.7 10 70 79.3
下载: 导出CSV
表 8 单程运行时间限制对运营效率的影响
Table 8. Impact of one-way running time limit on operational efficiency
最长运行时间/min 发车次数 座位平均利用率/% 目标值/元 46 8 87 54.2 40 10 71 62.4 34 10 70 64.6
下载: 导出CSV
表 9 车型比例对运营效率的影响
Table 9. Impact of vehicle composition on operational efficiency
车辆组成 发车次数 座位平均利用率/% 目标值/元 M为8辆, A型车占比50.0% 10 67 66.6 M为8辆, A型车占比62.5% 10 71 62.4 M为8辆, A型车占比75.0% 10 74 57.5
下载: 导出CSV
-
[1] 潘述亮, 俞洁, 卢小林, 等. 灵活型公交服务系统及其研究进展综述[J]. 城市交通, 2014, 12(2): 62-68, 58. doi: 10.3969/j.issn.1672-5328.2014.02.009PAN Shu-liang, YU Jie, LU Xiao-lin, et al. A review of flexible transit service[J]. Urban Transport of China, 2014, 12(2): 62-68, 58. (in Chinese). doi: 10.3969/j.issn.1672-5328.2014.02.009 [2] CHANDRA S, QUADRIFOGLIO L. A new street connectivity indicator to predict performance for feeder transit services[J]. Transportation Research Part C: Emerging Technologies, 2013, 30: 67-80. doi: 10.1016/j.trc.2013.02.004 [3] LI Xiu-gang, QUADRIFOGLIO L. Feeder transit services: choosing between fixed and demand responsive policy[J]. Transportation Research Part C: Emerging Technologies, 2010, 18(5): 770-780. doi: 10.1016/j.trc.2009.05.015 [4] QUADRIFOGLIO L, LI Xiu-gang. A methodology to derive the critical demand density for designing and operating feeder transit services[J]. Transportation Research Part B: Methodological, 2009, 43(10): 922-935. doi: 10.1016/j.trb.2009.04.003 [5] QUADRIFOGLIO L, DDESSOUKY M M, ORDÓÑEZ F. Asimulation study of demand responsive transit system design[J]. Transportation Research Part A: Policy and Practice, 2008, 42(4): 718-737. doi: 10.1016/j.tra.2008.01.018 [6] EDWARDS D, WATKINS K. Comparing fixed-route and demand responsive feeder transit systems in real-world settings[J]. Transportation Research Record, 2013(2352): 128-135. [7] LI Xiu-gang, QUADRIFOGLIO L. Optimal zone design for feeder transit services[J]. Transportation Research Record, 2009(2111): 100-108. [8] 苗一迪. 柔性路径公交车服务区域的决策模型研究[D]. 大连: 大连理工大学, 2011.MIAO Yi-di. A decision-making model for determining the service area of a flexible-route bus[D]. Dalian: Dalian University of Technology, 2011. (in Chinese). [9] 芒烈. 面向轨道交通站点的需求响应型接驳公交系统调度方法[D]. 长春: 吉林大学, 2017.MANG Lie. Scheduling method of railway transit station oriented demand responsive connector system[D]. Changchun: Jilin University, 2017. (in Chinese). [10] PAN Shu-liang, YU Jie, YANG Xian-feng, et al. Designing a flexible feeder transit system serving irregular shaped and gated communities: service area and feeder route planning[J]. Journal of Urban Planning and Development, 2015, 141(3): 04014028-1-9. [11] 范文豪. 需求响应式接驳公交路径优化模型研究[D]. 南京: 东南大学, 2017.FAN Wen-hao. Research on routing optimization model of demand-responsive connector[D]. Nanjing: Southeast University, 2017. (in Chinese). [12] 熊杰, 关伟, 黄爱玲. 社区公交接驳地铁路径优化研究[J]. 交通运输系统工程与信息, 2014, 14(1): 166-173. doi: 10.3969/j.issn.1009-6744.2014.01.026XIONG Jie, GUAN Wei, HUANG Ai-ling. Research on optimal routing of community shuttle connect rail transit line[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(1): 166-173. (in Chinese). doi: 10.3969/j.issn.1009-6744.2014.01.026 [13] YU Yao, MACHEMEHL R B, XIE Chi. Demand-responsive transit circulator service network design[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 76: 160-175. doi: 10.1016/j.tre.2015.02.009 [14] DESSOUKY M, RAHIMI M, WEIDNER M. Jointly optimizing cost, service, and environmental performance in demandresponsive transit scheduling[J]. Transportation Research Part D: Transport and Environment, 2003, 8(6): 433-465. doi: 10.1016/S1361-9209(03)00043-9 [15] NOURBAKHSH S M, OUYANG Yan-feng. A structured flexible transit system for low demand areas[J]. Transportation Research Part B: Methodological, 2012, 46(1): 204-216. doi: 10.1016/j.trb.2011.07.014 [16] NÚNEZ A, CORTÉSC E, SÁEZ D, et al. Multiobjective model predictive control for dynamic pickup and delivery problems[J]. Control Engineering Practice, 2014, 32: 73-86. doi: 10.1016/j.conengprac.2014.07.004 [17] KIRCHLER D, CALVO R W. A granular tabu search algorithm for the dial-a-ride problem[J]. Transportation Research Part B: Methodological, 2013, 56: 120-135. doi: 10.1016/j.trb.2013.07.014 [18] SCHILDE M, DOERNER K F, HARTL R F. Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem[J]. European Journal of Operational Research, 2014, 238(1): 18-30. doi: 10.1016/j.ejor.2014.03.005 [19] 潘述亮, 俞洁, 邹难, 等. 含特殊需求的灵活接驳公交服务区域与路径选择[J]. 东北大学学报(自然科学版), 2014, 35(11): 1650-1654. doi: 10.3969/j.issn.1005-3026.2014.11.029PAN Shu-liang, YU Jie, ZOU Nan, et al. Service area and route selection choice model for flexible feeder transit with special demands[J]. Journal of Northeastern University(Natural Science), 2014, 35(11): 1650-1654. (in Chinese). doi: 10.3969/j.issn.1005-3026.2014.11.029 [20] SHEU J B. A fuzzy clustering approach to real-time demandresponsive bus dispatching control[J]. Fuzzy Sets and Systems, 2005, 150(3): 437-455. doi: 10.1016/j.fss.2004.05.006 [21] 邱丰, 李文权, 沈金星. 可变线路式公交的两阶段车辆调度模型[J]. 东南大学学报(自然科学版), 2014, 44(5): 1078-1084. https://www.cnki.com.cn/Article/CJFDTOTAL-DNDX201405036.htmQIU Feng, LI Wen-quan, SHEN Jin-xing. Two-stage model for flex-route transit scheduling[J]. Journal of Southeast University(Natural Science Edition), 2014, 44(5): 1078-1084. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-DNDX201405036.htm [22] 高煦明. 固定站点需求响应式接驳公交调度模型研究[D]. 南京: 东南大学, 2015.GAO Xu-ming. Resaerch on dispatching system of demandresponsive connector with on-demand stations[D]. Nanjing: Southeast University, 2015. (in Chinese). [23] 赵伟忠. 随机用户需求下实时定制公交线路生成模型研究[D]. 西安: 长安大学, 2017.ZHAO Wei-zhong. The research on route generation model of real-time custom bus based on random user's demand[D]. Xi'an: Chang'an University, 2017. (in Chinese). [24] 陈坚, 李武, 吴丹, 等. 基于MAST的智慧公交系统调度优化模型[J]. 重庆交通大学学报(自然科学版), 2016, 35(5): 140-145. https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201605027.htmCHEN Jian, LI Wu, WU Dan, et al. Scheduling optimization model of intelligent public transport system based on MAST[J]. Journal of Chongqing Jiaotong University(Natural Science), 2016, 35(5): 140-145. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201605027.htm [25] GHANNADPOUR S F, NOORI S, TAVAKKOLI-MOGHADDAM R, et al. A multi-objective dynamic vehicle routing problem with fuzzy time windows: model, solution and application[J]. Applied Soft Computing Journal, 2014, 14(Part C): 504-527. [26] 易星. 基于用户需求的城市公交调度算法研究[J]. 智能计算机与应用, 2018, 8(4): 129-131, 135. doi: 10.3969/j.issn.2095-2163.2018.04.027YI Xing. Research on urban public transport scheduling algorithm based on user needs[J]. Intelligent Computer and Applications, 2018, 8(4): 129-131, 135. (in Chinese). doi: 10.3969/j.issn.2095-2163.2018.04.027 [27] 张鹏浩. 接驳高铁站的区域灵活型公交调度模型研究[D]. 北京: 北京交通大学, 2018.ZHANG Peng-hao. Research on scheduling model of regional flexible feeder bus for high-speed railway stations[D]. Beijing: Beijing Jiaotong University, 2018. (in Chinese). [28] 王正武, 易童翔, 高志波. 响应型接驳公交运行路径与车辆调度的协调优化[J]. 交通科学与工程, 2018, 34(1): 68-73. https://www.cnki.com.cn/Article/CJFDTOTAL-CSJX201801012.htmWANG Zheng-wu, YI Tong-xiang, GAO Zhi-bo. Coordinated optimization of running route and vehicle scheduling for responsive feeder transit[J]. Journal of Transport Science and Engineering, 2018, 34(1): 68-73. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CSJX201801012.htm [29] 王正武, 袁媛, 高志波. 高自由度响应公交分区路径与调度的协调优化[J]. 长沙理工大学学报(自然科学版), 2018, 15(1): 41-48. https://www.cnki.com.cn/Article/CJFDTOTAL-HNQG201801007.htmWANG Zheng-wu, YUAN Yuan, GAO Zhi-bo. Coordination optimization for partition path and scheduling with high degree of freedom demand response transit[J]. Journal of Changsha University of Science and Technology(Natural Science), 2018, 15(1): 41-48. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HNQG201801007.htm [30] 王正武, 刘安琪, 谭康康. 考虑乘客需求特性的DRC公交运行周期优化[J]. 长沙理工大学学报(自然科学版), 2016, 13(2): 19-25. https://www.cnki.com.cn/Article/CJFDTOTAL-HNQG201602005.htmWANG Zheng-wu, LIU An-qi, TAN Kang-kang. DRC bus operation cycle optimization corresponding to passenger demand characters[J]. Journal of Changsha University of Science and Technology(Natural Science), 2016, 13(2): 19-25. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HNQG201602005.htm [31] DENG Lian-bo, GAO Wei, ZHOU Wen-liang, et al. Optimal design of feeder-bus network related to urban rail line based on transfer system[J]. Procedia-Social and Behavioral Sciences, 2013, 96: 2383-2394. [32] 陈呈频, 韩胜军, 鲁建厦, 等. 多车场与多车型车辆路径问题的多染色体遗传算法[J]. 中国机械工程, 2018, 29(2): 218-223. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGJX201802014.htmCHEN Cheng-pin, HAN Sheng-jun, LU Jian-sha, et al. A multi-chromosome genetic algorithm for multi-depot and multi-type vehicle routing problems[J]. China Mechanical Engineering, 2018, 29(2): 218-223. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGJX201802014.htm -
点击查看大图
图(5) / 表(9)
计量
- 文章访问数: 1179
- HTML全文浏览量: 199
- PDF下载量: 677
- 被引次数: 0
