一种基于云计算的公交车实时调度算法改进

刘星程 丁伟峻 谢敬锐 王世玲 张江

摘要：经典的公交车调度算法都是在对公交调度的各种运行参数分时段做出经验性假设之后，通过建立数学模型来求解调度方案。这样的方式不能对不断变化的交通情况做出反馈。本文提出一种基于云计算和实时数据的公交车实时调度算法，该算法可以对公交线路运行做出更及时、更优化的分配，提高公交线路的运行效率。

关键词：云计算;实时数据;公交车调度

中图分类号：TN913        文献标识码：A

文章编号：1009-3044（2020）23-0037-02

Abstract： The classical bus scheduling algorithms are based on the empirical assumptions of various operation parameters of the bus scheduling in different periods， and then solve the scheduling scheme by establishing a mathematical model. Such a way can't give feedback on the changing traffic situation. In this paper， a real-time bus scheduling algorithm based on cloud computing and real-time data is proposed. This algorithm can make a more timely and optimized allocation of bus line operation， and improve the operation efficiency of bus line.

Key words：Cloud computing; real time data; bus scheduling

1 研究背景

隨着信息技术的不断发展，在公交调度领域使用算法来代替人工经验已经成为共识，但传统的公交调度算法采用的策略都是根据经验或统计值对各时段乘客数量进行假定之后建立调度模型，一旦实际情况与模型有较大出入，则会对乘客的候车体验造成较大影响。在云计算和4G通信技术已经成熟之际，本文提出一种根据公交车实时运载率作为判断依据的实时调度算法，和传统算法相比，该算法简单易行、并能实时对乘客的需求做出反馈，和原有算法相比可以更有效地提高公交车调度效益。

2 传统的公交调度算法

2.1传统调度算法的基本原理

多数公交车调度算法都部分基于如下的假设（3.2的改进算法仍然沿用这样的假设）：

（1）所有公交车载客量相等、行车速度相同;

（2）公交车在经过站点均即停即走，不熄火候客，乘客上下车时间也忽略不计;

（3）公交车发车间隔相等，始终保持匀速行驶。

在这种假设的基础上，调度算法根据历史经验或是统计值对各时段、各站点之间的乘客数量进行设定，继而求出某一时段某公交线路需要运送的最大乘客数量，并根据这一最大数量求出该时段需要的最小发车数量。

2.2传统算法的代表：基于求解最少发车次数的公交调度算法

该算法的基本思想是根据预先设定的数据，求出在某一时段公交车运送乘客的总运送量，再根据此量确定这一时段所需的最小公交车发车数量。

其中A（i，j）为第i时段在Aj站上车人数，Ti-1（i，j）为第i时段Aj站的乘客被第（i-1）时段公交车运走的人数，Ti（i+1，j）为第（i+1）时段到Aj站的乘客被第i时段公交车运走的人数。

则该线路i时段需要的最小公交车发车数量fi为：

其中C为每张车的满载载客数，C*1.2的意义为：根据经验，公交车的最大载客数为满载载客数的120%。

在该算法中，式（1）的所有参数均为模型给出的预设值，将所有预设值代入（1）和（2）即可求出某时段所需要的最小发车数量。表1为一个求解的示例。

2.3传统算法存在的弊端

传统的公交调度算法和以往完全依赖管理者经验的方法相比还是有很大优势，通过数学的方式求出最小值有助于实现公交运营的高效率和高效益。然而这些方法主要存在两个弊端：1）所有的参数均为人为设定的经验值，和实际情况相比必然会有出入，一旦出入比较大则会极大地影响乘客的候车体验;2）在传统方法中，诸如“i站登车的乘客在j站下车的人数”“第i时段Aj站的乘客被第（i-1）时段公交车运走的人数”等预设值设定过于复杂，这样的参数值甚至在实际运行中都根本统计不出来，数据的有效性完全取决于模型建立者的想象，会带来更大的误差。

3使用实时数据对公交调度进行改进

3.1通信系统及云计算平台

能够使用实时数据对公交调度进行实时控制一直都是公交运营者的设想，然而这种设想直到最近几年信息和通信技术取得巨大进展之后才真正具备了付诸实践的可能。

本文所设计的实时调度平台主要由通信系统和云计算平台两大部分构成，如图1所示。

系统中传输的实时数据为公交车上的乘客数量和该车驶离车站的候车乘客数量，由安装于公交车和车站的“客流量统计设备”实时获取，这种设备广泛应用于商场、医院、车站等场所的人流统计，技术上已成熟，精确率已能满足本系统的要求。云计算平台收到每一线路、每辆公交车的实时载客数量和驶离车站乘客数量后，根据改进的算法进行实时、统一的调度。

3.2使用实时数据改进传统算法

改进的算法采用（3）式计算某线路时段i所需的最少公交数量，其中Real（i，k）为某线路第k辆公交车在i时刻的实时乘客数。

之所以用实时乘客数来代替（2）中“需要被运送的乘客数”，是因为只有实时乘客数才是可以直接实时感知的。然而这样的替代在某些情况会和实际情况产生较大出入。例如当车站有大量乘客登不上车的情况下，（3）式将感知不到不能登车的乘客，仍然会按照实际登车人数来计算总需求。所以我们對（1）式中的Real（i，k）的计算方式进行改进。

公式（4）的实际含义是：当公交车未坐满时，“需要被运送的乘客数量”就视为登车的人数;当公交车已坐满时（Real（i，k）≥C*1.2），则认为“需要被运送的乘客数量”大于公交车的总载客数，而且是总载客数的（1+w）倍。其中w是一个实时确定的权重，由公交车驶离车站的乘客数量来确定（一般为车站乘客数量除以该车站公交线路数量再除以车辆最大载客量），虽然“驶离车站候车的乘客数量”和“想要乘坐本路车的乘客数量”并不完全一致，但是这两个变量是正相关的。

4结语

和传统的公交调度算法相比，改进的实时调度算法主要做出了两方面的改进：1）用实时数据代替预设数据。再精确的数学模型也无法模拟千变万化的交通情况，使用实时数据来调度公交运行必然比预设的调度方案更为合理、有效;2）摒弃了许多无意义或是无法获取的参数，将算法进行了简化。诸如“某车站所有人中想要乘坐某路公交车的人数”“i站上车乘客中将要在j站下车的人数”这样的参数在实际应用中无论再先进的设备都是无法获取的。实际上这样的参数也无须获取，有了类似于“某一时刻乘坐某一辆公交乘客数量”这样的真实数值，参数上的多少其实已经无关紧要。相比而言，多参数的传统算法，甚至还不如少参数的实时算法更精确，因为后者的参数是真实的。

参考文献：

[1] 张聪.基于并行计算的公交车调度优化研究[D]. 安徽理工大学，2014.

[2] 张春梅，王海晓，菅美英.基于多目标规划的公交车调度方法研究[J].内蒙古公路与运输，2010（1）：53-55.

[3] 陈翔宇，葛瀛龙，陈魏欣.基于双指标带权线性规划的公交车调度模型研究[J].计算机时代，2013（12）：1-3，6.

[4] 江国文.基于云计算的船舶大数据并行调度算法研究[J].舰船科学技术，2018，40（10X）：142-144.

[5] 罗娟，朱维钧.一种优化的公交车调度模型[J].平顶山学院学报，2010，25（2）：55-57.

[6] 谭泽光，姜启源.公交车调度问题的数学模型[J].工程数学学报，2002，19（S1）：101-106.

【通联编辑：唐一东】