一種基于云計算的公交車實時調度算法改進

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

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

關鍵詞：云計算;實時數據;公交車調度

中圖分類號：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.

【通聯編輯：唐一東】