基于用户需求的城市公交调度算法研究

摘 要：本文从中国城市地面公共交通现状，分析居民出行需求的多样性和复杂性，提出一种基于动态分配模型的公交调度系统。探讨城市公交基于用户需求响应模式的理论意义和实际应用价值，并构建数学模型和系统工作流程。综合考虑乘客出行时间、线路距离及容量约束，构建以最短路径和A*算法为乘客进行个性化出行需求规划线路和站点，建立适合中国国情的混合式公交运行模式，是现代智能交通可持续发展新产物。

关键词：智能公交； 需求调度； 最短路径； A*算法

Abstract： In this paper， the present situation of urban public transportation in China is analyzed. A bus dispatching system based on dynamic distribution model is proposed. The theoretical significance and practical application value based on the user demand response model are discussed， the mathematical model and the system work flow are constructed， and the passenger travel time， line distance and capacity constraints are considered. The shortest path and A* algorithm are used to plan the route and site for passengers' personalized travel needs， and the establishment of a hybrid bus operation model suitable for China is a new product of the sustainable development of modern intelligent transportation.

Key words： intelligent public transport； demand scheduling； shortest path； A* algorithm

引言

公共交通是一個城市经济文化的标志，中国城市地面公交基础设施投入巨大，却依旧不能满足人们出行需求。公交车保持固定线路和班次的做法，显然已经不符合智慧城市发展条件。在计算机通讯技术迅猛发展的时代，应制订相应发展目标，满足“公交优先”原则。从“以人为本”的理念出发，降低运行时间，提高可靠性和舒适度，实现以不断扩张公交线路网、增加公交车辆为特征的粗放型阶段向“智能化”、“按需化”发展阶段转型，是实现经济效益、社会效益和环境效益统一的最佳方式[1]。

1 需求响应与常规公交的区别

从公交服务模式的角度看，城市公共交通系统可被分为常规公交系统与需求响应型公交系统，常规公交系统具有固定的运行线路、停靠站点及发车间隔，适合人口密度较高的大城市[2]，但可调性差、服务质量较低。基于用户需求响应公交调度是依托“移动互联网+智能公交”的基础，在对市民乘车差异化需求广泛调查的基础上[3]，为乘客量身打造的一种新型的出行方式。与常规公交相比，系统没有固定的发车时刻表、服务范围、固定站点。与出租车相比，享有路权优先、经济实惠和低碳环保等优点。公交个性化按需调度将是一个创新的按需增值服务，公交企业可推出一系列基于按需分配的定制服务，乘客享受“一人一座”、“一站到达”、“一路通行”等服务，从而扩大市民出行的公交使用率，提高乘客满意度。

2 需求响应公交调度模型

基于用户需求响应的公交调度简称按需调度（On-Demand Bus Dispatching），是一个多目标决策系统，可建立图论模型描述交通道路。如定义有向加权图G=（V，E），由节点V和路径权值E组成，从边到权值的映射W：E->R；定义乘客等待时间Tm；乘客响应权值PPm；以Hijk表示乘客在第k辆车上从站i到站j之间的车上乘车时间总和，累计达到规定数值后公交行驶终点。

3 系统特点及算法设计

3.1 系统特点

目前，基于传统公交模式的混合启发式算法，或遗传算法的单线公交车辆调度方案的研究较多，但少有动态分配模型的公交调度系统方面的研究。本调度算法的线路优化是构建模型的首要任务，动态调度系统需要对乘客请求进行乘车点筛选，因此需要进行线路规划。乘客需向调度系统提交出行起始地和目的地，由系统调度附近公交为其服务。车辆在行驶过程中若出现请求服务，则相当于在有向加权图G的相邻顶点（Vi、Vj）间插入一个新需求点（Vx）。公交车的行驶线路发生变化需通过公交选径模块判断插入点V x是否满足行程时间f（c）与行驶线路f（s）等约束条件，符合条件则接受请求，否则继续通过路径选择模块和公交分配模块为其提供其它满足条件的公交车。算法流程如图1所示。

3.2 算法设计

对一个核心目标求最优解，对其他目标以约束条件形式获得可行解，或保留多个最优解，进行多目标决策分析，如Christoph mandi（1979）提出的GF算法第一目标是路线最短等[4]。A.N.Bansal（1981）通过理论分析证明了最短路线接近最优解。

按需调度公交系统的出现可满足城市公共交通出行多样性需求，对低出行密度地区公交服务问题的解决能力十分突出[7]。首先，城郊居民出行具有高平峰差异，[JP1]较适合本调度系统灵活调度的特点。其次，可以解决用户地铁到家“最后一公里”的诉求，智能化，按需化公交能有效解决交通治理精细化的效率和准确性。再次，本算法仍存在很多不足和需改进的地方，比如没有综合考虑市民出行费用及驾驶员费用等。城市公共交通规划者可通过常规公交和按需公交相结合的模式，提高公共交通服务水平和类型，有效满足居民个性化出行需求。

参考文献

[1] 张生瑞，严海. 城市公共交通规划的理论与实践[M]. 北京：中国铁道出版社，2007.

[2] 王诗琪. 基于出行行为分析的灵活公交动态调度模型研究[D]. 北京：北京交通大学，2016.

[3] 过秀成，严亚丹. 地面公共交通运行可靠性分析与调度控制[M]. 南京：东南大学出版社，2013.

[4] 雷德明，严新平. 多目标智能优化算法及其应用[M]. 北京：科学出版社，2009.

[5] 任刚. 交通管理措施下的交通分配模型与算法[M]. 南京：东南大学出版社，2007.

[6] 易星. 改进的A*算法在物流配送中的车辆调度方法[J]. 金陵科技学院学报，2017，33（4）：31-34.