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

徐晨暢　錢(qián)松榮

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

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

中圖分類(lèi)號(hào)： TP 311文獻(xiàn)標(biāo)志碼： 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ā)展，城市交通需求越來(lái)越密集，越來(lái)越多的人采用公共交通出行。公交車(chē)，作為一種傳統(tǒng)的公共交通工具，在城市交通中扮演十分重要的角色。由于交通情況非常復(fù)雜且難以預(yù)測(cè)，人為的制定公交車(chē)的發(fā)車(chē)時(shí)間和發(fā)車(chē)間隔越來(lái)越難以滿(mǎn)足乘客的需求，常常出現(xiàn)乘客花大量時(shí)間等候公交車(chē)，或是公交車(chē)接連到站，導(dǎo)致資源的浪費(fèi)。

近年來(lái)，隨著物聯(lián)網(wǎng)的發(fā)展，公交車(chē)已經(jīng)不再是孤立的個(gè)體。公交公司可以通過(guò)網(wǎng)絡(luò)和嵌入式設(shè)備，實(shí)時(shí)獲取公交車(chē)的坐標(biāo)位置和上下車(chē)乘客數(shù)量;通過(guò)大數(shù)據(jù)分析，可以實(shí)時(shí)計(jì)算道路交通情況?；诖耍藗冮_(kāi)始嘗試優(yōu)化公交車(chē)的調(diào)度問(wèn)題。

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

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

1 調(diào)度模型

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

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

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

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

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

（1） 公交車(chē)在每?jī)蓚€(gè)站點(diǎn)之間勻速運(yùn)行;

（2） 公交車(chē)到達(dá)每個(gè)站點(diǎn)后，能夠滿(mǎn)足所有上車(chē)需求;

（3） 是否加入新的公交車(chē)不影響站點(diǎn)乘客到達(dá)率;

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

已知固定量有：

（1） 線路l每?jī)蓚€(gè)站點(diǎn)之間的距離d1（l，i，j）;

（2） 線路l的站點(diǎn)數(shù)N（l）;

（3） 蓄車(chē)站m前往線路l的站點(diǎn)n距離d2（l，m，n）;

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

（5） 公交車(chē)停站耗時(shí)τ;

（6） 公交車(chē)停站成本c1;

（7） 公交車(chē)單位距離油耗c2。

已知實(shí)時(shí)量有：

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

（2） 線路l上每?jī)蓚€(gè)站點(diǎn)之間的運(yùn)行時(shí)間t1（l，i，j）;

（3） 蓄車(chē)站m前往線路l的站點(diǎn)n所需時(shí)間t2（l，m，n）;

（4） 線路l的站點(diǎn)k乘客到達(dá)率（基于歷史數(shù)據(jù)計(jì)算）σ（l，k）。

自變量有：

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

（2） 派遣的目標(biāo)線路和站點(diǎn)（L，b）;

應(yīng)變量是：

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

優(yōu)化目標(biāo)是：

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

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

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

bL（A）

設(shè)tAB為A、B兩輛公交車(chē)的時(shí)間間隔，tA（k），tB（k）分別為公交車(chē)A、B與站點(diǎn)k的時(shí)間間隔，T1由式（4）得到式（4）。

T2表示加入公交車(chē)C之后，公交車(chē)A和公交車(chē)B之間站點(diǎn)的乘客等車(chē)時(shí)間總和，其表達(dá)式如公式（5）所示，其中，tc（k）表示站點(diǎn)k與公交車(chē)C的時(shí)間間隔。

T3表示新加入公交車(chē)所需的運(yùn)營(yíng)人員（如司機(jī)）增加的工作時(shí)間，如式（6）。

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

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

2 模型求解

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

（1） 染色體初始化

以圖2情況為例，蓄車(chē)站共有7個(gè)，用3位二進(jìn)制數(shù)

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

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

（b） 保證每?jī)奢v正在運(yùn)行的公交車(chē)之間，最多加入1輛支援車(chē)輛。

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

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

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

（3） 自然選擇

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

（4） 交叉

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

（5） 變異

對(duì)每條染色體的每個(gè)二進(jìn)制數(shù)以Pm的概率取反，增加種群多樣性。變異后，驗(yàn)證各染色體是否滿(mǎn)足約束條件，若不滿(mǎn)足，則撤銷(xiāo)變異。

（6） 精英保留

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

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

3 實(shí)驗(yàn)仿真

本文主要目的是驗(yàn)證算法的可行性，采用Matlab對(duì)本實(shí)驗(yàn)的模型和算法進(jìn)行了仿真。如圖3所示。

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

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

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

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

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

（1） 從蓄車(chē)站2派出一輛車(chē)前往701線路的12站點(diǎn);

（2） 從蓄車(chē)站5派出一輛車(chē)前往702線路的16站點(diǎn);

（3） 從蓄車(chē)站5派出一輛車(chē)前往713線路的18站點(diǎn)。

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

（收稿日期： 2019.06.09）

作者簡(jiǎn)介：

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

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