基于遺傳算法的突發(fā)公交智能調(diào)度算法

徐晨暢　錢松榮

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

關(guān)鍵詞： 公交調(diào)度; 智能調(diào)度; 遺傳算法

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

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

近年來，隨著物聯(lián)網(wǎng)的發(fā)展，公交車已經(jīng)不再是孤立的個體。公交公司可以通過網(wǎng)絡(luò)和嵌入式設(shè)備，實時獲取公交車的坐標位置和上下車乘客數(shù)量;通過大數(shù)據(jù)分析，可以實時計算道路交通情況。基于此，人們開始嘗試優(yōu)化公交車的調(diào)度問題。

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

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

1 調(diào)度模型

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

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

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

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

將此問題描述為一個優(yōu)化問題，有以下假設(shè)：

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

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

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

（4） 支援公交車加入后，在可預(yù)期的未來，路況保持平穩(wěn)。

已知固定量有：

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

（2） 線路l的站點數(shù)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乘客到達率（基于歷史數(shù)據(jù)計算）σ（l，k）。

自變量有：

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

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

應(yīng)變量是：

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

優(yōu)化目標是：

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

其中，應(yīng)變量C可由式（1）求得如式（1）。

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

bL（A）

設(shè)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）。

從而，我們建立了智能調(diào)度算法的調(diào)度模型。

2 模型求解

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

（1） 染色體初始化

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

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

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

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

（2） 計算適應(yīng)度

對當(dāng)前的P組染色體，分別計算節(jié)省的成本C，代入sigmoid函數(shù)中求出適應(yīng)度F，如式（8）。

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

（3） 自然選擇

根據(jù)每個染色體的適應(yīng)度，采用輪盤賭的方式選擇出P個子代染色體。

（4） 交叉

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

（5） 變異

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

（6） 精英保留

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

設(shè)最大代數(shù)為MaxGen，在達到最大代數(shù)之前，循環(huán)執(zhí)行步驟2）至步驟6），最終bestchain會趨于最優(yōu)解，排除bestchain的M個方案中使C<0的方案，剩余的方案即為最優(yōu)（近似）調(diào)度方案的組合。

3 實驗仿真

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

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

在該仿真問題中，設(shè)定M為10，染色體長度為110，P為200，MaxGen為300。站點間、各蓄車站到各站點的路程為在某地圖軟件量取的真實路程;站點間、各蓄車站前往各站點的運行時間采用某時刻地圖軟件基于大數(shù)據(jù)給出的機動車運行時間估計;運行車輛分布根據(jù)公交公司網(wǎng)站查詢的發(fā)車間隔，結(jié)合站點間機動車運行時間數(shù)據(jù)人為設(shè)定;乘客到達率根據(jù)站點所處地段估測得到。另外，根據(jù)當(dāng)?shù)厝司杖耄悦咳展ぷ?小時為標準，計算出ρ=0.15 yuan/min。τ、c1、c2根據(jù)實際情況給出。

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

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

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

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

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

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

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

4 總結(jié)

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

參考文獻

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

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

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

（收稿日期： 2019.06.09）

作者簡介：

徐晨暢（1994-），男，碩士，研究方向：數(shù)據(jù)通信與網(wǎng)絡(luò)。

錢松榮（1963-），男，碩士，教授，研究方向：數(shù)據(jù)通信與網(wǎng)絡(luò)。