一種基于云計算的公交車實時調(diào)度算法改進

劉星程 丁偉峻 謝敬銳 王世玲 張江

摘要：經(jīng)典的公交車調(diào)度算法都是在對公交調(diào)度的各種運行參數(shù)分時段做出經(jīng)驗性假設之后，通過建立數(shù)學模型來求解調(diào)度方案。這樣的方式不能對不斷變化的交通情況做出反饋。本文提出一種基于云計算和實時數(shù)據(jù)的公交車實時調(diào)度算法，該算法可以對公交線路運行做出更及時、更優(yōu)化的分配，提高公交線路的運行效率。

關鍵詞：云計算;實時數(shù)據(jù);公交車調(diào)度

中圖分類號：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 研究背景

隨著信息技術的不斷發(fā)展，在公交調(diào)度領域使用算法來代替人工經(jīng)驗已經(jīng)成為共識，但傳統(tǒng)的公交調(diào)度算法采用的策略都是根據(jù)經(jīng)驗或統(tǒng)計值對各時段乘客數(shù)量進行假定之后建立調(diào)度模型，一旦實際情況與模型有較大出入，則會對乘客的候車體驗造成較大影響。在云計算和4G通信技術已經(jīng)成熟之際，本文提出一種根據(jù)公交車實時運載率作為判斷依據(jù)的實時調(diào)度算法，和傳統(tǒng)算法相比，該算法簡單易行、并能實時對乘客的需求做出反饋，和原有算法相比可以更有效地提高公交車調(diào)度效益。

2 傳統(tǒng)的公交調(diào)度算法

2.1傳統(tǒng)調(diào)度算法的基本原理

多數(shù)公交車調(diào)度算法都部分基于如下的假設（3.2的改進算法仍然沿用這樣的假設）：

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

（2）公交車在經(jīng)過站點均即停即走，不熄火候客，乘客上下車時間也忽略不計;

（3）公交車發(fā)車間隔相等，始終保持勻速行駛。

在這種假設的基礎上，調(diào)度算法根據(jù)歷史經(jīng)驗或是統(tǒng)計值對各時段、各站點之間的乘客數(shù)量進行設定，繼而求出某一時段某公交線路需要運送的最大乘客數(shù)量，并根據(jù)這一最大數(shù)量求出該時段需要的最小發(fā)車數(shù)量。

2.2傳統(tǒng)算法的代表：基于求解最少發(fā)車次數(shù)的公交調(diào)度算法

該算法的基本思想是根據(jù)預先設定的數(shù)據(jù)，求出在某一時段公交車運送乘客的總運送量，再根據(jù)此量確定這一時段所需的最小公交車發(fā)車數(shù)量。

其中A（i，j）為第i時段在Aj站上車人數(shù)，Ti-1（i，j）為第i時段Aj站的乘客被第（i-1）時段公交車運走的人數(shù)，Ti（i+1，j）為第（i+1）時段到Aj站的乘客被第i時段公交車運走的人數(shù)。

則該線路i時段需要的最小公交車發(fā)車數(shù)量fi為：

其中C為每張車的滿載載客數(shù)，C*1.2的意義為：根據(jù)經(jīng)驗，公交車的最大載客數(shù)為滿載載客數(shù)的120%。

在該算法中，式（1）的所有參數(shù)均為模型給出的預設值，將所有預設值代入（1）和（2）即可求出某時段所需要的最小發(fā)車數(shù)量。表1為一個求解的示例。

2.3傳統(tǒng)算法存在的弊端

傳統(tǒng)的公交調(diào)度算法和以往完全依賴管理者經(jīng)驗的方法相比還是有很大優(yōu)勢，通過數(shù)學的方式求出最小值有助于實現(xiàn)公交運營的高效率和高效益。然而這些方法主要存在兩個弊端：1）所有的參數(shù)均為人為設定的經(jīng)驗值，和實際情況相比必然會有出入，一旦出入比較大則會極大地影響乘客的候車體驗;2）在傳統(tǒng)方法中，諸如“i站登車的乘客在j站下車的人數(shù)”“第i時段Aj站的乘客被第（i-1）時段公交車運走的人數(shù)”等預設值設定過于復雜，這樣的參數(shù)值甚至在實際運行中都根本統(tǒng)計不出來，數(shù)據(jù)的有效性完全取決于模型建立者的想象，會帶來更大的誤差。

3使用實時數(shù)據(jù)對公交調(diào)度進行改進

3.1通信系統(tǒng)及云計算平臺

能夠使用實時數(shù)據(jù)對公交調(diào)度進行實時控制一直都是公交運營者的設想，然而這種設想直到最近幾年信息和通信技術取得巨大進展之后才真正具備了付諸實踐的可能。

本文所設計的實時調(diào)度平臺主要由通信系統(tǒng)和云計算平臺兩大部分構成，如圖1所示。

系統(tǒng)中傳輸?shù)膶崟r數(shù)據(jù)為公交車上的乘客數(shù)量和該車駛離車站的候車乘客數(shù)量，由安裝于公交車和車站的“客流量統(tǒng)計設備”實時獲取，這種設備廣泛應用于商場、醫(yī)院、車站等場所的人流統(tǒng)計，技術上已成熟，精確率已能滿足本系統(tǒng)的要求。云計算平臺收到每一線路、每輛公交車的實時載客數(shù)量和駛離車站乘客數(shù)量后，根據(jù)改進的算法進行實時、統(tǒng)一的調(diào)度。

3.2使用實時數(shù)據(jù)改進傳統(tǒng)算法

改進的算法采用（3）式計算某線路時段i所需的最少公交數(shù)量，其中Real（i，k）為某線路第k輛公交車在i時刻的實時乘客數(shù)。

之所以用實時乘客數(shù)來代替（2）中“需要被運送的乘客數(shù)”，是因為只有實時乘客數(shù)才是可以直接實時感知的。然而這樣的替代在某些情況會和實際情況產(chǎn)生較大出入。例如當車站有大量乘客登不上車的情況下，（3）式將感知不到不能登車的乘客，仍然會按照實際登車人數(shù)來計算總需求。所以我們對（1）式中的Real（i，k）的計算方式進行改進。

公式（4）的實際含義是：當公交車未坐滿時，“需要被運送的乘客數(shù)量”就視為登車的人數(shù);當公交車已坐滿時（Real（i，k）≥C*1.2），則認為“需要被運送的乘客數(shù)量”大于公交車的總載客數(shù)，而且是總載客數(shù)的（1+w）倍。其中w是一個實時確定的權重，由公交車駛離車站的乘客數(shù)量來確定（一般為車站乘客數(shù)量除以該車站公交線路數(shù)量再除以車輛最大載客量），雖然“駛離車站候車的乘客數(shù)量”和“想要乘坐本路車的乘客數(shù)量”并不完全一致，但是這兩個變量是正相關的。

4結語

和傳統(tǒng)的公交調(diào)度算法相比，改進的實時調(diào)度算法主要做出了兩方面的改進：1）用實時數(shù)據(jù)代替預設數(shù)據(jù)。再精確的數(shù)學模型也無法模擬千變?nèi)f化的交通情況，使用實時數(shù)據(jù)來調(diào)度公交運行必然比預設的調(diào)度方案更為合理、有效;2）摒棄了許多無意義或是無法獲取的參數(shù)，將算法進行了簡化。諸如“某車站所有人中想要乘坐某路公交車的人數(shù)”“i站上車乘客中將要在j站下車的人數(shù)”這樣的參數(shù)在實際應用中無論再先進的設備都是無法獲取的。實際上這樣的參數(shù)也無須獲取，有了類似于“某一時刻乘坐某一輛公交乘客數(shù)量”這樣的真實數(shù)值，參數(shù)上的多少其實已經(jīng)無關緊要。相比而言，多參數(shù)的傳統(tǒng)算法，甚至還不如少參數(shù)的實時算法更精確，因為后者的參數(shù)是真實的。

參考文獻：

[1] 張聰.基于并行計算的公交車調(diào)度優(yōu)化研究[D]. 安徽理工大學，2014.

[2] 張春梅，王海曉，菅美英.基于多目標規(guī)劃的公交車調(diào)度方法研究[J].內(nèi)蒙古公路與運輸，2010（1）：53-55.

[3] 陳翔宇，葛瀛龍，陳魏欣.基于雙指標帶權線性規(guī)劃的公交車調(diào)度模型研究[J].計算機時代，2013（12）：1-3，6.

[4] 江國文.基于云計算的船舶大數(shù)據(jù)并行調(diào)度算法研究[J].艦船科學技術，2018，40（10X）：142-144.

[5] 羅娟，朱維鈞.一種優(yōu)化的公交車調(diào)度模型[J].平頂山學院學報，2010，25（2）：55-57.

[6] 譚澤光，姜啟源.公交車調(diào)度問題的數(shù)學模型[J].工程數(shù)學學報，2002，19（S1）：101-106.

【通聯(lián)編輯：唐一東】