基于遺傳算法的景區(qū)公交調(diào)度優(yōu)化研究

林鑫?張海波?鄭鰻芝

摘 要：在公交調(diào)度管理的過程中，公交運(yùn)營(yíng)方利益和乘客利益需要合理兼顧，而公交車發(fā)車間隔是公交調(diào)度優(yōu)化的關(guān)鍵。本文以四川省成都市蒲江縣櫻桃山風(fēng)景區(qū)為例，根據(jù)景區(qū)公交線路布局情況，以降低運(yùn)營(yíng)方運(yùn)行成本、減少游客出行成本為優(yōu)化目標(biāo)建立目標(biāo)函數(shù)，對(duì)公交運(yùn)營(yíng)成本和乘客等待成本進(jìn)行合理的線性加權(quán)，求解最優(yōu)公交發(fā)車時(shí)間間隔。最后，運(yùn)用遺傳算法進(jìn)行求解，得到優(yōu)化后的公交車在不同時(shí)間段的發(fā)車間隔。

關(guān)鍵詞：公交調(diào)度;發(fā)車間隔;景區(qū)公交;遺傳算法

中圖分類號(hào)：U492.22;TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-5168（2021）32-0010-03

Research on Optimization of Bus Dispatching in Scenic Spots Based on Genetic Algorithm

LIN Xin ZHANG Haibo ZHENG Manzhi

（Southwest Jiaotong University Hope College， Chengdu Sichuan 610400）

Abstract： In the process of bus dispatch management， the interests of bus operators and passengers need to be balanced， and the bus departure interval is the key to the optimization of bus dispatch. Taking the Cherry Mountain Scenic Spot in Pujiang County， Chengdu City as an example， according to the layout of the scenic bus routes， this paper takes reducing the operating cost of the operator and reducing the travel cost of tourists as the optimization objectives， and establishes an objective function， and applies reasonable linear weighting to the bus operating cost and passenger waiting cost， so as to solve the reasonable bus departure time interval. Finally， the genetic algorithm is used to solve the problem， obtaining the optimized bus departure interval in different time periods.

Keywords： bus dispatching;departure interval;scenic bus;genetic algorithm

為最大限度地吸引游客，提高景區(qū)服務(wù)質(zhì)量，當(dāng)前急需制定合理的公交調(diào)度方案。SCHEELES以乘客出行時(shí)間成本最小為目標(biāo)，以車輛容量、客流分配為約束條件，建立以車輛發(fā)車頻率為優(yōu)化目標(biāo)的非線性規(guī)劃模型[1]。DORIGO等在研究公交線網(wǎng)問題時(shí)，以線路條件、道路條件、車輛運(yùn)營(yíng)時(shí)間為約束條件，建立了乘客出行OD矩陣的數(shù)學(xué)模型，以優(yōu)化車輛發(fā)車頻率[2]。FABIANC等在優(yōu)化公交調(diào)度的過程中考慮了乘客的換乘時(shí)間，運(yùn)用遺傳算法解決了公交車發(fā)車頻率問題[3]。國(guó)內(nèi)學(xué)者也在相應(yīng)問題上進(jìn)行了大量研究。朱金壽等在建立多目標(biāo)規(guī)劃模型時(shí)考慮了公交公司的經(jīng)濟(jì)成本和乘客的出行成本，并用遺傳算法對(duì)模型進(jìn)行求解[4]。陳濤在大數(shù)據(jù)中挖掘乘客的出行規(guī)律，并結(jié)合影響公交調(diào)度的因素，建立公交調(diào)度優(yōu)化模型進(jìn)行求解[5]。

在模型求解算法的運(yùn)用中，研究人員分別采用遺傳算法、蟻群算法、模擬退火算法等對(duì)公交調(diào)度模型進(jìn)行求解[6-8]?？傊?，以上研究都同時(shí)考慮了運(yùn)營(yíng)企業(yè)和乘客的利益，對(duì)城市公交調(diào)度方案進(jìn)行優(yōu)化。本文結(jié)合景區(qū)出行特點(diǎn)，借鑒傳統(tǒng)公交的服務(wù)-需求關(guān)系建立多目標(biāo)數(shù)學(xué)模型，運(yùn)用遺傳算法進(jìn)行求解，最后對(duì)四川省成都市蒲江縣櫻桃山風(fēng)景區(qū)公交發(fā)車頻率提出了優(yōu)化建議。

1 公交調(diào)度模型的建立

1.1 公交調(diào)度的概念

按照客流數(shù)據(jù)的實(shí)效性，公交調(diào)度可分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。靜態(tài)調(diào)度是指根據(jù)客流的歷史分布規(guī)律，結(jié)合運(yùn)營(yíng)企業(yè)的運(yùn)輸能力，提前制定好公交調(diào)度方案，包括車輛發(fā)車間隔、車輛運(yùn)用計(jì)劃以及工作人員排班表等。動(dòng)態(tài)調(diào)度是指利用現(xiàn)代技術(shù)手段獲得客流分布的動(dòng)態(tài)變化情況，在事先制定好的調(diào)度方案基礎(chǔ)上，實(shí)時(shí)調(diào)整調(diào)度方案，以合理安排不同情況下的車輛發(fā)車頻率、車輛運(yùn)用計(jì)劃，屬于靜態(tài)計(jì)劃的補(bǔ)充。本文從靜態(tài)調(diào)度的角度出發(fā)，對(duì)公交發(fā)車頻率進(jìn)行優(yōu)化。

1.2 模型的建立

1.2.1 模型假設(shè)。在實(shí)際的公交運(yùn)營(yíng)管理過程中，多種因素會(huì)影響公交運(yùn)營(yíng)。為簡(jiǎn)化研究過程，在建立調(diào)度優(yōu)化模型的過程中，要對(duì)諸多外部因素加以約束。因此，本研究做出如下假設(shè)：公交車輛所有車型相同，即運(yùn)載能力相同;所有車輛逢站即停，不允許超車;在運(yùn)營(yíng)各時(shí)間段內(nèi)，乘客到達(dá)站點(diǎn)服從均勻分布;車輛勻速運(yùn)行，運(yùn)行時(shí)間包括停站時(shí)間;投入運(yùn)營(yíng)車輛足夠;同運(yùn)營(yíng)時(shí)段內(nèi)發(fā)車間隔相同;乘客只用等待第一班到達(dá)車輛即可上車;車輛單位里程運(yùn)營(yíng)成本保持不變;所有乘客出行成本相同。

1.2.2 變量定義。把景區(qū)運(yùn)營(yíng)時(shí)間分為I個(gè)時(shí)間段，時(shí)間段的集合為I={1，2，…，i，…}，i表示第i個(gè)時(shí)間段。第i個(gè)時(shí)間段的時(shí)長(zhǎng)為t，第i個(gè)時(shí)間段車輛的發(fā)車間隔為Δt。S為景區(qū)公交運(yùn)營(yíng)路段的總長(zhǎng)度，r為公交車單位里程的運(yùn)營(yíng)成本。J代表站點(diǎn)的總數(shù)，站點(diǎn)數(shù)的集合為J={1，2，…，j，…}，j表示第j個(gè)站點(diǎn)。第i個(gè)時(shí)間段的客流量為vi，第i個(gè)時(shí)間段內(nèi)平均每分鐘到達(dá)j站點(diǎn)的游客數(shù)量為v。第i個(gè)時(shí)間段內(nèi)發(fā)車時(shí)間最大間隔為Δt，最小間隔為Δt。游客候車的單位時(shí)間價(jià)值為e，單位為元/min，公交車的額定載客量為C。

1.2.3 模型建立。設(shè)游客的出行成本為N，企業(yè)的運(yùn)營(yíng)成本為M。單位時(shí)間的游客出行成本計(jì)算公式為：

假設(shè)游客到達(dá)站點(diǎn)服從均勻分布，則第i時(shí)間段游客的平均候車時(shí)間為Δt/2。一個(gè)運(yùn)營(yíng)日內(nèi)所有游客的出行總成本為：

運(yùn)營(yíng)公司在一個(gè)運(yùn)營(yíng)日內(nèi)的總發(fā)車次數(shù)為：

一天的總運(yùn)營(yíng)成本為：

1.2.4 目標(biāo)函數(shù)。調(diào)整車輛發(fā)車間隔主要考慮兩個(gè)因素，一是運(yùn)營(yíng)公司的運(yùn)營(yíng)成本，二是乘客的出行成本。但是，這兩個(gè)因素對(duì)車輛發(fā)車時(shí)間間隔的影響是對(duì)立的。所以，在同時(shí)考慮兩個(gè)因素的情況下，要引入加權(quán)系數(shù)λ和λ。對(duì)多目標(biāo)問題加權(quán)合并，將其轉(zhuǎn)換成單一目標(biāo)函數(shù)：

1.2.5 約束條件。考慮景區(qū)服務(wù)質(zhì)量，車輛空間利用可以適當(dāng)寬松，但不能過于擁擠，即滿足式（6）約束條件;車輛發(fā)車時(shí)間間隔應(yīng)有約束范圍，以保障運(yùn)營(yíng)公司和乘客的利益，即滿足式（7）約束條件;為保障運(yùn)營(yíng)公司的經(jīng)濟(jì)利益，要限制運(yùn)營(yíng)公司的運(yùn)營(yíng)成本，即滿足式（8）約束條件。

2 遺傳算法求解過程

2.1 編碼

本文對(duì)變量采用二進(jìn)制編碼（0，1）。在定義染色體長(zhǎng)度時(shí)，要考慮時(shí)間段劃分、最小發(fā)車時(shí)間間隔和最大發(fā)車時(shí)間間隔。一天的運(yùn)營(yíng)時(shí)間段數(shù)為I，染色體的長(zhǎng)度為4I。設(shè)定發(fā)車時(shí)間間隔最小為1 min，最大為8 min，即區(qū)間長(zhǎng)度為8。不同時(shí)間段內(nèi)發(fā)車時(shí)間間隔為一個(gè)3位數(shù)的二進(jìn)制數(shù)。

2.2 初始種群

在產(chǎn)生初始種群的過程中，采用隨機(jī)挑選的辦法，在隨機(jī)產(chǎn)生的數(shù)個(gè)個(gè)體中選擇出最好的個(gè)體加入初始種群，并且不斷重復(fù)這個(gè)過程，直到達(dá)到目標(biāo)種群規(guī)模，選擇出含有X個(gè)個(gè)體、染色體長(zhǎng)度為4I的二進(jìn)制數(shù)。

2.3 適應(yīng)度評(píng)價(jià)

根據(jù)適應(yīng)度計(jì)算函數(shù)計(jì)算出不同個(gè)體的適應(yīng)度，選擇適應(yīng)度大的個(gè)體投入下一次的遺傳過程。在計(jì)算過程中，為進(jìn)行適應(yīng)度值的比較，一般其適應(yīng)度值取正值。引入一個(gè)適當(dāng)?shù)倪m應(yīng)度最大值Z，將目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù)：

2.4 算子

2.4.1 選擇算子。算子交叉過程中，原始個(gè)體不斷交叉復(fù)制。在此過程中，對(duì)個(gè)體中的部分基因加以改變，從而產(chǎn)生新的個(gè)體。通過比較不同個(gè)體適應(yīng)度值的大小，選擇適應(yīng)度高的個(gè)體，舍棄適應(yīng)度低的個(gè)體。

2.4.2 交叉算子。在選擇算子得到的種群中，隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行交叉運(yùn)算。設(shè)定交叉率為0.8，根據(jù)交叉率判斷是否執(zhí)行交叉。若不需要，則直接將個(gè)體納入新的種群;若需要，則執(zhí)行單點(diǎn)交叉，直到交叉次數(shù)達(dá)到設(shè)定的最大值，從而得出新的個(gè)體納入種群。

2.4.3 變異算子。在交叉算子得到的種群中，隨機(jī)選擇個(gè)體，設(shè)定變異率為0.01，根據(jù)變異率判斷是否執(zhí)行變異。若不需要，則直接將個(gè)體納入新的種群;若需要，則隨機(jī)選擇點(diǎn)位進(jìn)行變異，直到滿足約束條件或達(dá)到設(shè)定的最大變異次數(shù)，從而得到新的個(gè)體納入種群。

2.4.4 終止計(jì)算。在變異運(yùn)算得到的種群中，按適應(yīng)度值進(jìn)行比較，淘汰掉適應(yīng)度值較低的個(gè)體，從上一代群體中選取適應(yīng)度值較高的個(gè)體進(jìn)行替代，從而產(chǎn)生新的種群，直到達(dá)到設(shè)定的運(yùn)算次數(shù)。

3 案例分析

3.1 運(yùn)營(yíng)線路基本信息

本文針對(duì)成都市蒲江縣櫻桃山風(fēng)景區(qū)旅游公交進(jìn)行調(diào)度優(yōu)化。該旅游線路全長(zhǎng)為10 km，共設(shè)18個(gè)站點(diǎn)，固定發(fā)車間隔為5 min，統(tǒng)一票價(jià)為5元/人。選取櫻桃節(jié)期間（4—5月）的一個(gè)周六作為研究時(shí)段進(jìn)行靜態(tài)優(yōu)化。把一天的運(yùn)營(yíng)時(shí)段分為6段，分別為08：00—09：00、09：00—10：00、10：00—11：00、11：00—15：00、15：00—16：00、16：00—18：00，時(shí)間長(zhǎng)度分別為60 min、60 min、60 min、240 min、60 min和120 min。6個(gè)時(shí)段的客流量分別為1 127人、1 221人、1 437人、6 325人、1 021人和904人，發(fā)車間隔最大分別為4 min、4 min、4 min、8 min、4 min和6 min，最小發(fā)車時(shí)間間隔均為1 min。公交車額定載客人數(shù)為60人，公交車單位運(yùn)營(yíng)成本為6.4元/km。

3.2 參數(shù)設(shè)置

遺傳算法中設(shè)置的參數(shù)值為：交叉概率P=0.8，變異概率P=0.05，種群規(guī)模K=80，迭代次數(shù)G=500次。在運(yùn)營(yíng)公司利益和游客利益的權(quán)重選擇上，以λ+λ=1為前提，傾向于考慮企業(yè)利益時(shí)，取λ=0.6，λ=0.4;在傾向于乘客方利益時(shí)，取λ=0.4，λ=0.6。

3.3 計(jì)算結(jié)果

當(dāng)λ=0.6，λ=0.4時(shí)，各時(shí)間段內(nèi)的發(fā)車間隔分別為3.5 min、3.1 min、2.9 min、5.9 min、3.2 min和4.3 min;當(dāng)λ=0.4，λ=0.6時(shí)，各時(shí)段的發(fā)車間隔為3.2 min、2.3 min、2.0 min、4.2 min、2.6 min和3.3 min。在實(shí)際調(diào)度方案的制定中，可根據(jù)調(diào)度目標(biāo)選擇固定的權(quán)重系數(shù)，也可在不同時(shí)段內(nèi)選擇不同的權(quán)重系數(shù)。例如，在客流低谷期，可側(cè)重于運(yùn)營(yíng)企業(yè)利益，選擇λ=0.6、λ=0.4制定方案;在客流高峰期，可側(cè)重于乘客利益，選擇λ=0.4、λ=0.6制定方案。

4 結(jié)語

考量乘客的出行成本與運(yùn)營(yíng)公司的經(jīng)營(yíng)成本，建立綜合的非線性規(guī)劃模型。該規(guī)劃模型的優(yōu)化目標(biāo)為車輛的發(fā)車時(shí)間間隔，同時(shí)考慮了運(yùn)營(yíng)公司和游客雙方的經(jīng)濟(jì)成本。最后，利用遺傳算法求解最優(yōu)解，得出最合適的發(fā)車時(shí)間間隔。

參考文獻(xiàn)：

[1]SCHEELE S.A supply model for public transit service[J].Transportation Research Part B：Methodological，1980（12）：133-146.

[2]DORIGO M，MANIEZZO V，COLORNI A.The ant system：Optimization by a colony of a cooperating agent[J].IEEE Transactions on SMC，1996（1）：28-41.

[3]FABIAN C，ZHAO F.A genetic algorithm for bus schedule synchronization [J].American Association of Textile Technology，2006（13）：737-742.

[4]朱金壽，朱琪，楊勇剛.遺傳算法在公交車調(diào)度優(yōu)化中的應(yīng)用[J].交通與計(jì)算機(jī)，2002（3）：62-64.

[5]陳濤.基于大數(shù)據(jù)和混合啟發(fā)式算法的公交調(diào)度方法[D].杭州：杭州電子科技大學(xué)，2016：17-18.

[6]韋尚成.臨界-遺傳算法在公交調(diào)度中的應(yīng)用[J].物流科技，2017（5）：101-106.

[7]任曉莉.基于禁忌搜索的智能公交調(diào)度研究[J].測(cè)控技術(shù)，2014（2）：124-126.

[8]蔡光躍.遺傳算法和蟻群算法在求解TSP問題上的對(duì)比分析[J].計(jì)算機(jī)工程與應(yīng)用，2007（10）：96-98.