基于遺傳算法的突發公交智能調度算法

徐晨暢　錢松榮

摘 要： 公交車是城市交通的重要工具，為了優化乘客等車時間，同時使額外成本保持在可以接受的范圍內，提出一種應對突發交通狀況的公交智能調度算法，在突發狀況下派遣公交車支援合適站點。通過結合實際場景設計調度方案，給出方案的數學模型和優化問題，基于遺傳算法，求解出合適的公交車支援方案。采用某地的實際道路交通和公交數據，對算法進行了仿真，結果表明，提出的算法能夠有效的給出公交調度建議。

關鍵詞： 公交調度; 智能調度; 遺傳算法

中圖分類號： TP 311文獻標志碼： A

Intelligent Bus Dispatch Algorithm for Emergency Based on Genetic Algorithm

XU Chenchang， QIAN Songrong

（

School of Information Science and Technology， Fudan University， Shanghai 200433， China

）

Abstract： Bus is one of the most important vehicles of city transportation. In order to reduce the waiting time of the passengers and make extra cost controlable for the bus company， an intelligent bus dispatch algorithm for emergency is proposed. It designs a new mathematical model to describe the dispatch problem and provides a method based on Genetic Algorithm to calculate the best dispatch scheme. With the real transportation data of a certain city， the algorithm is proved to be effective in simulation.

Key words： bus dispatch; intelligent dispatch; genetic algorithm

0 引言

隨著城市的快速發展，城市交通需求越來越密集，越來越多的人采用公共交通出行。公交車，作為一種傳統的公共交通工具，在城市交通中扮演十分重要的角色。由于交通情況非常復雜且難以預測，人為的制定公交車的發車時間和發車間隔越來越難以滿足乘客的需求，常常出現乘客花大量時間等候公交車，或是公交車接連到站，導致資源的浪費。

近年來，隨著物聯網的發展，公交車已經不再是孤立的個體。公交公司可以通過網絡和嵌入式設備，實時獲取公交車的坐標位置和上下車乘客數量;通過大數據分析，可以實時計算道路交通情況。基于此，人們開始嘗試優化公交車的調度問題。

崔明月[1]等提出基于歷史數據，使用遺傳算法取代人為分析，為公交車一天中的各個時間段計算出不同的發車間隔。鄭思瑤[2]提出越站實時調度模型，即在滿足下車乘客正常下車的前提下，公交車選擇性的進行停站，使整個公交運行效率更高，乘客乘車時間更短。

本文提出，在道路發生堵車、交通事故等突發情況時，擁擠路段前方的乘客需要等待大量時間才能上車，在此種情況下，使用一種智能算法，自動從合適的站點調用合適的空車支援擁堵路段前方車輛，在盡可能少增加公交公司運行成本的條件下，盡可能減少乘客的等車時間，優化乘車體驗。下文將給出算法模型、模型解法和實驗分析。

1 調度模型

將某條公交線路，如圖1所示。

圖1中標有序號的圓圈為線路上的21個站點，其中，實心圓圈代表蓄車站（始發站、終點站、支援站），可以提供車輛支援，除C以外的公交車為當前在線路上運行的公交車。假設站點4和站點5之間發生交通擁堵，站點5及其后續站點的乘客將等待大量時間才能夠坐上公交車，此時，若站點8與站點5之間有較為通常的道路，可從站點8派遣車輛直達站點5加入運行線路，將能夠有效減少乘客等車時間。

針對多條線路的情況，如圖2所示。

共有3條公交線路，在此條件下，實心的蓄車站被設計為可以支援任何一條線路的任何站點。

將此問題描述為一個優化問題，有以下假設：

（1） 公交車在每兩個站點之間勻速運行;

（2） 公交車到達每個站點后，能夠滿足所有上車需求;

（3） 是否加入新的公交車不影響站點乘客到達率;

（4） 支援公交車加入后，在可預期的未來，路況保持平穩。

已知固定量有：

（1） 線路l每兩個站點之間的距離d1（l，i，j）;

（2） 線路l的站點數N（l）;

（3） 蓄車站m前往線路l的站點n距離d2（l，m，n）;

（4） 單位時間等效成本（基于城市平均工資）ρ;

（5） 公交車停站耗時τ;

（6） 公交車停站成本c1;

（7） 公交車單位距離油耗c2。

已知實時量有：

（1） 線路l上公交車的位置集合bi;

（2） 線路l上每兩個站點之間的運行時間t1（l，i，j）;

（3） 蓄車站m前往線路l的站點n所需時間t2（l，m，n）;

（4） 線路l的站點k乘客到達率（基于歷史數據計算）σ（l，k）。

自變量有：

（1） 派遣支援車輛的出發站點a;

（2） 派遣的目標線路和站點（L，b）;

應變量是：

加入新支援公交車后，節省的成本C（減少的時間成本和增加的運營成本總和）。

優化目標是：

使C最大化的若干種自變量取值。

其中，應變量C可由式（1）求得如式（1）。

其中，以圖1為例，T1表示未加入公交車C之前，公交車A和公交車B之間站點的乘客等車時間，設

bL（A）

設tAB為A、B兩輛公交車的時間間隔，tA（k），tB（k）分別為公交車A、B與站點k的時間間隔，T1由式（4）得到式（4）。

T2表示加入公交車C之后，公交車A和公交車B之間站點的乘客等車時間總和，其表達式如公式（5）所示，其中，tc（k）表示站點k與公交車C的時間間隔。

T3表示新加入公交車所需的運營人員（如司機）增加的工作時間，如式（6）。

C4表示新加入公交車所增加的停站成本、油耗成本等，如式（7）。

從而，我們建立了智能調度算法的調度模型。

2 模型求解

使用遺傳算法[3]可對第1部分的優化問題進行求解，求解流程如下：

（1） 染色體初始化

以圖2情況為例，蓄車站共有7個，用3位二進制數

a表示，目標線路總共有3條，用2位二進制數L表示，最長的線路共有23個站點，所以需要用5位二進制數b表示。可見，一個支援方案的變量共需用10位二進制數表示。在一個大的公交系統中，我們希望一次求解能夠同時獲得對不同路段的多個支援方案，定義方案上限為M個，如M為10時，則總共需要100位二進制數表示這10個方案。這100位二進制數，就是遺傳算法中的一個染色體。在遺傳算法中，還需定義種群大小P，如當P為200時，在初始化的過程中，需要隨機初始化200組長度為100的染色體（chain）。隨機初始化的結果需要根據約束條件判斷是否有意義，本模型的約束條件包括：

（a） 各變量在約束范圍內，1≤a≤7，1≤L≤3，1≤b≤N，其中N為線路L的站點數;

（b） 保證每兩輛正在運行的公交車之間，最多加入1輛支援車輛。

（2） 計算適應度

對當前的P組染色體，分別計算節省的成本C，代入sigmoid函數中求出適應度F，如式（8）。

其中，θ為根據實際情況定義的一個常數，盡可能使使C/θ的取值在sigmoid函數的非飽和區。此時，還需保留一個使F最大的最佳染色體bestchain。

（3） 自然選擇

根據每個染色體的適應度，采用輪盤賭的方式選擇出P個子代染色體。

（4） 交叉

設每條染色體的每一個支援方案為染色體的一個片段，將P個染色體兩兩配對，交換兩個染色體的隨機一個片段，若交換后，兩條染色體仍滿足約束條件，則完成交換，若不滿足約束條件，則撤銷交換。

（5） 變異

對每條染色體的每個二進制數以Pm的概率取反，增加種群多樣性。變異后，驗證各染色體是否滿足約束條件，若不滿足，則撤銷變異。

（6） 精英保留

為了保證最佳染色體不在上述過程中消失，完成上述過程后，隨機將P個染色體中的一個替換成bestchain。

設最大代數為MaxGen，在達到最大代數之前，循環執行步驟2）至步驟6），最終bestchain會趨于最優解，排除bestchain的M個方案中使C<0的方案，剩余的方案即為最優（近似）調度方案的組合。

3 實驗仿真

本文主要目的是驗證算法的可行性，采用Matlab對本實驗的模型和算法進行了仿真。如圖3所示。

某地區的三條線路（701、702、713），三角形標識的為蓄車站。

在該仿真問題中，設定M為10，染色體長度為110，P為200，MaxGen為300。站點間、各蓄車站到各站點的路程為在某地圖軟件量取的真實路程;站點間、各蓄車站前往各站點的運行時間采用某時刻地圖軟件基于大數據給出的機動車運行時間估計;運行車輛分布根據公交公司網站查詢的發車間隔，結合站點間機動車運行時間數據人為設定;乘客到達率根據站點所處地段估測得到。另外，根據當地人均收入，以每日工作8小時為標準，計算出ρ=0.15 yuan/min。τ、c1、c2根據實際情況給出。

如上文描述，仿真中的大部分數據來源如線路、路程、運行時間、ρ等是真實數據;少部分無法獲得真實數據的，如乘客到達率人為設定，設定過程中盡可能反應真實情況。因此，使用這些數據，能夠有效模擬真實場景，仿真結果具有實際意義。

仿真案例中，所有站點序號從北往南，從小到大，從1開始標記。人為增加701線路11～12站點間運行時間，702線路14～15站點間運行時間，713線路17～18站點運行時間后，用于模擬這3個路段發生交通擁堵，在此種情況下，驗證算法的正確性。仿真過程如圖4所示。

可以看出，隨著迭代不斷進行，bestchain的節省的成本C不斷增加，最終結果為359.5元。在這個結果下給出的方案是：

（1） 從蓄車站2派出一輛車前往701線路的12站點;

（2） 從蓄車站5派出一輛車前往702線路的16站點;

（3） 從蓄車站5派出一輛車前往713線路的18站點。

其中，蓄車站2為圖3中左上方的三角形標注的站點，蓄車站5為圖3中心的三角形標注的站點。可以看出，通過模型的求解，派遣蓄車站的車輛支援擁堵路段的后續站點，降低了時間成本，從而降低了整體的成本，符合直觀的認知。由此可見本文提出的模型和求解方法能夠給出合理的調度支援方案。

4 總結

本文基于公交實時位置信息和乘客到達率信息，對突發公交智能調度的場景進行建模，利用遺傳算法進行求解，實現了在道路部分擁堵時的一種有效的調度算法。通過實驗可以看出，算法能夠準確的計算出合適的支援車輛所在蓄車站和合適的目標站點。本文所述方法，能夠一定程度解放城市公交調度中所需的人力，為解決城市公交調度問題提供了一種有效的智能解決方案，也是公交調度平臺軟件開發的可行參考。

參考文獻

[1] 崔明月，黃榮杰，劉紅釗，等.量子遺傳算法在公交車輛調度中的應用[J].實驗室研究與探索，2014，33（12）：72-76.

[2] 鄭思瑤. 車車通信條件下的公交實時調度方法研究[D].北京：北京交通大學，2016.

[3] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008（10）：2911-2916.

（收稿日期： 2019.06.09）

作者簡介：

徐晨暢（1994-），男，碩士，研究方向：數據通信與網絡。

錢松榮（1963-），男，碩士，教授，研究方向：數據通信與網絡。