复杂路网下灵活接驳公交路径优化研究

交通运输系统工程与信息 ›› 2016, Vol. 16 ›› Issue (6): 128-134.

复杂路网下灵活接驳公交路径优化研究

卢小林¹，潘述亮²，邹难*¹

1. 山东大学控制科学与工程学院，济南250061；2. 济南全通信息科技有限公司，济南250101

收稿日期:2016-04-20 修回日期:2016-08-02 出版日期:2016-12-25 发布日期:2016-12-26
作者简介:卢小林（1988-），女，山东冠县人，博士生.
基金资助:
国家科技支撑计划/National Natural Science Foundation of China (2014BAG03B04)；山东大学基本科研业务费专项项目/The Fundamental Research Funds of Shandong University(2014JC036).

Flexible Feeder Transit Route Design in Complex Road Network

LU Xiao-lin¹, PAN Shu-liang², ZOU Nan¹

1. School of Control Science and Engineering, Shandong University, Jinan 250061, China; 2. Jinan Quantong Technology and Information Ltd., Jinan 250101, China

Received:2016-04-20 Revised:2016-08-02 Online:2016-12-25 Published:2016-12-26

摘要/Abstract

摘要：

为解决现实路网中存在单行路，以及双向隔离的情况下灵活公交车辆路径优化问题，本文创新提出一种新型的公交车运营服务模式，允许公交车临时偏移基准线路服务乘客需求站点，途径特殊路段可同时服务道路两侧的乘客需求.同时提出一种以最小化公交车运营时间为目标的路径优化模型，在当多辆公交车运营在目标服务区域内时，模型可以用于寻找最短路径以便最近的车辆来服务乘客需求.其次，就模型的求解给出了一种三阶段求解算法，将待求解问题转化为旅行商问题，有效提升了求解速度.最后，利用案例分析验证了模型和算法的有效性，能在合理的时间范围内求解出运营车辆路径.

关键词: 交通工程, 路径优化, 遗传算法, 灵活接驳公交, 需求响应, 农村邮递员问题

Abstract:

To solve the flexible feeder transit route design problem in complex road network where exists separated two-way roads and one-way roads, a new operational mode is presented, which is capable of letting operating feeder buses temporarily deviate from their current route so as to serve passengers on both street sides. In addition, a transit route design model is proposed with an objective of minimizing total bus travel time. When multiple feeder buses are operating in the target service area, the proposed model can provide an optimal plan to locate the nearest one to response to the demands. A three-stage solution algorithm is also developed to improve solution efficiency by transforming the problem into a Traveling Salesman Problem (TSP). Numerical studies have demonstrated the effectiveness of the proposed model as well as the heuristic solution approach, the proposed algorithm can yield meta-optimal solutions to the problem in a reasonable amount of time.

Key words: traffic engineering, route design, genetic algorithm, flexible feeder transit, demand responsive, rural postman problem

中图分类号:

U491

卢小林，潘述亮，邹难. 复杂路网下灵活接驳公交路径优化研究[J]. 交通运输系统工程与信息, 2016, 16(6): 128-134.

LU Xiao-lin1, PAN Shu-liang2, ZOU Nan1. Flexible Feeder Transit Route Design in Complex Road Network[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(6): 128-134.

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

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

http://www.tseit.org.cn/CN/Y2016/V16/I6/128

参考文献

[1] STEVEN C, ZHAO W Y. Optimal feeder bus routes on irregular street networks[J]. Journal of Advanced Transportation, 2000, 34(2): 213-248.

[2] MISTRETTA M, et al. Best practices in transit service planning[R]. Report No. BD549- 38 prepared by the Center for Urban Transportation Research for the Florida Department of Transportation. 2009.

[3] PALMER K, MAGED D, TAMER A. Impacts of management practices and advanced technologies on demand responsive transit systems[J]. Transportation Research Part A: Policy and Practice, 2004, 38(7): 495- 509.

[4] Chira-Chavala T, Geofley G, Christoffel V.Automation of paratransit reservation, routing, and scheduling[J]. Journal of Advanced Transportation, 2000, 34(2): 191- 211.

[5] ALSHALALFAH B W. Planning, Design and scheduling of flex- route transit service[D]. Diss. University of Toronto, 2009.

[6] KOFFMAN D. Operational experiences with flexible transit services: a synthesis of transit practice[R]. TCRP Synthesis 53, Transportation Research Board, Washington, DC, 2004.

[7] LI X G. Optimal design of demand- responsive feeder transit services[M]. Diss. Texas A&M University, 2009.

[8] AVISHAI(AVI) C. Integrated smart feeder/shuttle transit service: simulation of new routing strategies[J]. Journal of Advanced Transportation, 2013(47): 595-618.

[9] LUCA Q. A hybrid fixed and flexible transportation service: description, viability, formulation, optimization and heuristic[M]. Diss. University of Southern California, 2005.

[10] QIU F, WENQUAN L, ALI H. A methodology for choosing between fixed-route and flex-route policies for transit services[J]. Journal of Advanced Transportation, 2015, 49(3): 496-509.

[11] MALUCELLI F, NONATO M, PALLOTTINO S. Demand adaptive systems: some proposals on flexible transit[J]. Operations Research in Industry, 1999: 157-182.

[12] QUADRIFOGLIO L, DESSOUKY M M. Mobility allowance shuttle transit (MAST) services: formulation and simulation comparison with conventional fixed route bus services. Modelling, simulation, and optimization[C]. Á Proceedings of the 4th IASTED international conference.Kauai, HI, USA, 17Á19 August. Calgary: Acta Press, 6pp. 2004

[13] QUADRIFOGLIO L, DESSOUKY M. Insertion heuristic for scheduling Mobility Allowance Shuttle Transit (MAST) services: sensitivity to service area[J]. Computer-Aided Systems in Public Transport, Springer Series: Lecture Notes in Economics and Mathematical Systems, 2007: 600.

[14] QUADRIFOGLIO L, DESSOUKY M M, PALMER K. An insertion heuristic for scheduling mobility allowance shuttle transit (MAST) services[J]. Journal of Scheduling, 2007, 1(10): 25-40.

[15] QUADRIFOGLIO L, DESSOUKY M M. Sensitivity analyses over the service area for mobility allowance shuttle transit (MAST) services[J]. Computeraided Systems in Public Transport, 2008: 419-432.

[16] QUADRIFOGLIO L, DESSOUKY M M, ORDÓÑEZ F. Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints[J]. European Journal of Operational Research, 2008, 2 (185): 481-494.

[17] QUADRIFOGLIO L, HALL R W, DESSOUKY M M. Performance and design of mobility allowance shuttle transit services: bounds on the maximum longitudinal velocity[J]. Transportation science, 2006, 3(40): 351- 363.

[18] KIM M E, SCHONFELD P. Integration of conventional and flexible bus services with timed transfers[J]. Transportation Research Part B: Methodological, 2014 (68): 76-97.

[19] CHANDRA S, QUADRIFOGLIO L. Critical street links for demand responsive feeder transit services[J]. Computers & Industrial Engineering, 2013, 66(3): 584- 592.

[20] PEARN, WEN LEA, T C WU. Algorithms for the rural postman problem[J]. Computers & Operations Research, 1995, 22(8): 819-828.

[21] CORBERÁN A, RAFAEL M. Heuristics for the mixed rural postman problem[J]. Computers & Operations Research, 2000, 27(2): 183-203.

[22] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematic, 1959, 1(1): 269-271.