陶燁

摘 要：針對(duì)公交線路，研究制定出合理的公交車(chē)調(diào)度機(jī)制，對(duì)乘客和公交公司雙方的利益都有非常重要的現(xiàn)實(shí)意義和價(jià)值。本文拉薩市一公交線路為例，根據(jù)其日均客流情況，建立以公交公司運(yùn)營(yíng)成本最小和乘客利益損失最低為目標(biāo)的公交調(diào)度優(yōu)化模型，并通過(guò)改進(jìn)遺傳算法對(duì)其進(jìn)行求解，得到最優(yōu)公交運(yùn)營(yíng)時(shí)間間隔和公交車(chē)配車(chē)數(shù)量。研究結(jié)果表明，采用優(yōu)化后的公交調(diào)度機(jī)制，并用改進(jìn)后的遺傳算法求解，可以有效提升公交公司運(yùn)營(yíng)效率和乘客滿(mǎn)意度。

關(guān)鍵詞：遺傳算法 公交調(diào)度 優(yōu)化設(shè)計(jì)

長(zhǎng)期以來(lái)，我國(guó)許多城市公交企業(yè)主要依靠管理者的經(jīng)驗(yàn)和制定公交運(yùn)營(yíng)計(jì)劃者的直覺(jué)，導(dǎo)致公交運(yùn)營(yíng)水平和服務(wù)質(zhì)量低下，從而影響公共交通出行比例和公共交通企業(yè)的經(jīng)濟(jì)效益。因此，對(duì)公交調(diào)度的研究可以為現(xiàn)代公共交通提供技術(shù)支持和服務(wù)保障，實(shí)現(xiàn)公交調(diào)度運(yùn)行的高效、高效，提供準(zhǔn)時(shí)、快捷、舒適的服務(wù)，提高公共交通的吸引力，提高企業(yè)經(jīng)濟(jì)效益，促進(jìn)居民出行。

國(guó)外學(xué)者Avila-TorresP等[1]對(duì)周期同步次數(shù)與運(yùn)營(yíng)成本構(gòu)建雙目標(biāo)模糊規(guī)劃模型，采用需求水平、置信度和模糊三個(gè)指標(biāo)對(duì)模型進(jìn)行評(píng)價(jià)，結(jié)果驗(yàn)證模型有效性。Sharaf AK等[2]開(kāi)發(fā)了針對(duì)一般問(wèn)題的整數(shù)線性規(guī)劃模型，確定了最優(yōu)的發(fā)車(chē)車(chē)次。國(guó)內(nèi)學(xué)者尹詩(shī)德[3]以發(fā)車(chē)間隔為自變量建立公交調(diào)度模型運(yùn)用混合布谷鳥(niǎo)算法進(jìn)行求解，為求解公交調(diào)度問(wèn)題提供了一種新思路。李欣然等[4]以乘客平均等待時(shí)間最小為目標(biāo)建立優(yōu)化模型運(yùn)用粒子群算法進(jìn)行優(yōu)化，結(jié)果證明該算法能有效解決問(wèn)題。楊海榮[5]考慮乘客費(fèi)用和運(yùn)營(yíng)商成本建立優(yōu)化模型最后用遺傳模擬退火求解。丁勇等[6]以乘客費(fèi)用以及社會(huì)效益為目標(biāo)建立了優(yōu)化模型運(yùn)用遺傳算法求解，結(jié)果證明擁有積極意義。任傳祥等[7]以乘客時(shí)間和企業(yè)成本為目標(biāo)，建立優(yōu)化模型并用改進(jìn)的遺傳禁忌搜索算法進(jìn)行求解，結(jié)果證明效率比傳統(tǒng)求解方法高。

1 數(shù)學(xué)模型的建立

1.1 模型假設(shè)

公交調(diào)度的數(shù)學(xué)模型主要是對(duì)實(shí)際公交調(diào)度問(wèn)題的抽象和概括，因此不可能充分考慮所有復(fù)雜的外部因素，必須對(duì)外部因素進(jìn)行合理限制。公交調(diào)度模型具有復(fù)雜、受多種外部因素影響的特點(diǎn)。本文做出以下假設(shè)：

本文的研究對(duì)象是拉薩某一公交線路，發(fā)車(chē)不考慮重復(fù)路線忽視客流客觀原因造成的統(tǒng)計(jì)誤差;公交車(chē)輛為同一車(chē)型，且公交車(chē)運(yùn)行情況良好;乘客到達(dá)站點(diǎn)數(shù)量服從均勻分布;公交車(chē)只運(yùn)行一條公交線路上，且只考慮單程車(chē)運(yùn)行;單位時(shí)間內(nèi)乘客消耗的費(fèi)用是固定的;單位乘次公交車(chē)消耗的成本是固定的。

1.2 目標(biāo)函數(shù)及約束條件

在現(xiàn)實(shí)公交調(diào)度中，公交車(chē)調(diào)度優(yōu)化模型的目標(biāo)函數(shù)需要考慮兩個(gè)方面，從乘客的角度需要最大程度上減少乘客因等車(chē)所消耗的費(fèi)用損失增加發(fā)車(chē)次數(shù)。另一方面需要最大程度上減少公交公司的運(yùn)營(yíng)成本減少發(fā)車(chē)次數(shù)。以此為目標(biāo)建立模型。

Pkj=ukj/Tk

mk=tk/Δtk

1.2.1 乘客費(fèi)用損失

通過(guò)查閱國(guó)內(nèi)相關(guān)文獻(xiàn)發(fā)現(xiàn)前人在建立目標(biāo)函數(shù)時(shí)，會(huì)以所有乘客的費(fèi)用損失建立目標(biāo)函數(shù)，本文以平均費(fèi)用損失建立目標(biāo)函數(shù)，以保證每位乘客在等車(chē)時(shí)都能夠降低費(fèi)用損失，其穩(wěn)定性較之前者更高。

1.2.2 營(yíng)運(yùn)成本W(wǎng)2

公交公司的營(yíng)運(yùn)成本可表示為線路總發(fā)車(chē)次數(shù)與單位次數(shù)營(yíng)運(yùn)成本積的形式：

那么目標(biāo)函數(shù)為：

Wmin=W1+W2

為了建立易于求解的優(yōu)化模型。我們將該公交該線路的發(fā)車(chē)時(shí)段分為高峰時(shí)段和平峰時(shí)段。其中：

那么一天的費(fèi)用損失函數(shù)F

F=min（F1+F2）

以滿(mǎn)載率不低于60%為約束條件

以上數(shù)學(xué)模型中符號(hào)說(shuō)明如下表1所示：

2 遺傳算法的設(shè)計(jì)

2.1 操作算子改進(jìn)

復(fù)制：在運(yùn)營(yíng)商選擇方面，通過(guò)“優(yōu)勝劣汰”的復(fù)制操作，引導(dǎo)集團(tuán)向適應(yīng)環(huán)境的方向發(fā)展。在迭代初期，整個(gè)搜索空間分布著群體中的每個(gè)個(gè)體。這時(shí)，優(yōu)秀的個(gè)體在整個(gè)搜索空間中所占的比例很小，所以這個(gè)時(shí)候的選擇機(jī)制應(yīng)是寬松的。隨著迭代的進(jìn)行，在迭代的后期，優(yōu)秀個(gè)體在搜索空間中占有很大比例，選擇機(jī)制應(yīng)嚴(yán)格，從中選出最優(yōu)秀的個(gè)體。單一的選擇機(jī)制是不合理的，應(yīng)該隨著遺傳迭代來(lái)改變。本文首先計(jì)算個(gè)體適應(yīng)度值。采用輪盤(pán)賭法執(zhí)行選擇過(guò)程，然后利用精英保留政策保留。即從優(yōu)秀個(gè)體中除去遺傳過(guò)程而直接從父代復(fù)制到子代。輪盤(pán)賭算法公式：

自適應(yīng)交叉、變異：

為了增加種群的多樣性以避免早熟的現(xiàn)象發(fā)生，較大的交叉率很好的豐富了種群的多樣性，但是隨著迭代次數(shù)的增多，種群逐漸向最優(yōu)解靠近此時(shí)若再次采用較大的交叉率、變異率。又增加了新的個(gè)體分布在最優(yōu)解的周?chē)?。降低了最?yōu)解在搜索空間中的比重延緩了收斂進(jìn)程。所以交叉率、變異率前期應(yīng)大后期應(yīng)小，是自適應(yīng)變化的。

崔珊珊[8]在設(shè)計(jì)自適應(yīng)交叉率和變異率時(shí)，主要考慮平均適應(yīng)值和迭代次數(shù)。

PC=PC0+（PC0-PCmin）*

pm=

pm=（pm0-（pm0-pmmin）*+pm0*）/2

其中：Pm1與遺傳進(jìn)化代數(shù)成反比關(guān)系，隨著遺傳進(jìn)化代數(shù)的增加，Pm1的值減小;Pm2與群體平均適應(yīng)值的好壞有關(guān)系，群體平均適應(yīng)值越好，Pm2的值越小，見(jiàn)圖1。

通過(guò)工具M(jìn)ATLAB并利用遺傳算法求解TSP商旅問(wèn)題，輸出其當(dāng)前最優(yōu)值以及當(dāng)前平均目標(biāo)值的線性圖，圖中可看出在前二十次迭代過(guò)程中，當(dāng)前最優(yōu)值與平均最優(yōu)值的下降速度幾乎相同，在迭代20次以后平均最優(yōu)值呈現(xiàn)穩(wěn)態(tài)分布而最優(yōu)值呈現(xiàn)緩慢下降趨勢(shì)。由此可得，以當(dāng)前最優(yōu)值與平均作為參考是不合理的。改進(jìn)如下：

本文引入理想狀態(tài)下目函數(shù)最大適應(yīng)度設(shè)為1，為將約束在（0 ，1）內(nèi)采用倒數(shù)形式，已知互成倒數(shù)的兩個(gè)數(shù)線性關(guān)系呈反比，同時(shí)我們要求變異率隨著迭代逐漸減小。因此最終以作為參考。這樣更好的保證了自適應(yīng)變異率與迭代過(guò)程的聯(lián)系。同時(shí)引入王倩[9]等，用四分位間距替換自適應(yīng)交叉和變異概率中的固定參數(shù)。

改進(jìn)遺傳算法流程如圖2：

3 實(shí)例分析

本研究以拉薩市某一公交線路為研究對(duì)象，對(duì)該線路發(fā)車(chē)時(shí)刻表進(jìn)行優(yōu)化。如圖3所示是該線路每日的平均客流變化情況。

這里我們將公交車(chē)一天的運(yùn)行時(shí)間分為 9 個(gè)時(shí)段，又考慮到，公交發(fā)車(chē)一天內(nèi)的發(fā)車(chē)間隔在個(gè)時(shí)段內(nèi)不會(huì)頻繁更換，將該線路一天的發(fā)車(chē)時(shí)段用高峰時(shí)段、平峰時(shí)段進(jìn)行標(biāo)記，如表2所示。高峰時(shí)段的劃分為：7：30-8：30，12：00-12：30，14：00-14：30，17：30-18：30，總3個(gè)小時(shí)。平峰時(shí)段的劃分為：6：30-7：30、8：30-12：00、12：30-14：00、14：30-17：30、18：30-21：30，總12個(gè)小時(shí)，見(jiàn)表2。

根據(jù)建立的公交優(yōu)化數(shù)學(xué)模型，采用改進(jìn)過(guò)后的遺傳算法進(jìn)行實(shí)例仿真。主要參數(shù)出發(fā)間隔的變化間隔[5，30]，該值為0.5的整數(shù)倍。初始種群大小n=30，交叉概率PC=0.89，變異概率PM=0.01，最大迭代次數(shù)g=220。迭代次數(shù)權(quán)重系數(shù)0.6，平均適應(yīng)度權(quán)重系數(shù)0.4。高峰時(shí)段成本損失的權(quán)重系數(shù)是0.6，平峰時(shí)段0.4，高峰時(shí)段到達(dá)率0.88，平峰時(shí)段0.65，高峰時(shí)段公交公司的成本消耗的加權(quán)系數(shù)是0.7，高峰時(shí)段乘客的成本損失的加權(quán)系數(shù)是0.3。平峰時(shí)段公交公司費(fèi)用消耗的加權(quán)系數(shù)是0.6，平峰時(shí)段乘客登車(chē)的費(fèi)用損失加權(quán)系數(shù)0.4。

最后通過(guò)仿真得到了拉薩市公交的最佳發(fā)車(chē)時(shí)間間隔。高峰時(shí)段的最佳發(fā)車(chē)時(shí)間間隔為9.4分鐘，平峰時(shí)段的最佳發(fā)車(chē)時(shí)間間隔為16.4分鐘?？紤]到實(shí)際時(shí)間間隔通常是5的倍數(shù)，和每日計(jì)劃不會(huì)改變，最終獲得最優(yōu)出發(fā)時(shí)間間隔，發(fā)車(chē)間隔10分鐘在高峰時(shí)間20分鐘在高峰時(shí)間，所以發(fā)車(chē)車(chē)次56次、平均滿(mǎn)座率80%，公司運(yùn)營(yíng)成本節(jié)約20%，乘客滿(mǎn)意度提高30%。

4 結(jié)語(yǔ)

本文對(duì)拉薩市某公交線路的公交調(diào)度進(jìn)行了研究，建立了該線路公交調(diào)度優(yōu)化的數(shù)學(xué)模型，利用改進(jìn)后的遺傳算法得到了該線公交調(diào)度的最優(yōu)發(fā)車(chē)時(shí)間間隔和最優(yōu)公交調(diào)度數(shù)量。數(shù)據(jù)表明，優(yōu)化后的公交調(diào)度機(jī)制可以提高乘客滿(mǎn)意度，有效降低公交成本。本文建立的公交調(diào)度優(yōu)化數(shù)學(xué)模型對(duì)于其他線路的公交調(diào)度也有一定的積極意義。

參考文獻(xiàn)：

[1]Paulinavila-Torres，F(xiàn)ernando López-Irarragorri，Caballero R， et al. The multimodal and multiperiod urban transportation integrated timetable construction problem with demand uncertainty[J]. Journal of Industrial and Management Optimization（JIMO），2018，14（2）：447-472.

[2]Sharaf A K，F(xiàn)ahad A R，Areej Z.Optimal bus frequency for Kuwait public transportation company：A cost view[J].Sustainable Cities and Society，2018，41：312-319.

[3]尹詩(shī)德.基于模擬退火的混合布谷鳥(niǎo)算法求解公交調(diào)度問(wèn)題.2018.華南理工大學(xué)，MA thesis.

[4]李欣然，and 靳雁霞."量子行為粒子群優(yōu)化算法在公交調(diào)度優(yōu)化中的應(yīng)用." 計(jì)算機(jī)系統(tǒng)應(yīng)用 21.07（2012）：191-195. doi：CNKI：SUN：XTYY.0.2012-07-045.

[5]楊海榮.“基于改進(jìn)遺傳算法的公交車(chē)輛調(diào)度優(yōu)化.”長(zhǎng)沙理工大學(xué)學(xué)報(bào)（自然科學(xué)版）6.02（2009）：13-17. doi：CNKI：SUN：HNQG.0.2009-02-004.

[6]丁勇，姜楓，and武玉艷.“遺傳算法在公交調(diào)度中的應(yīng)用.”計(jì)算機(jī)科學(xué)43.S2（2016）：601-603.doi：CNKI：SUN：JSJA.0.2016-S2-136.

[7]任傳祥，郇宜軍，and 尹唱唱.“基于遺傳禁忌搜索算法的公交調(diào)度研究.”山東科技大學(xué)學(xué)報(bào)（自然科學(xué)版）.04（2008）：53-56.doi：10.16452/j.cnki.sdkjzk.2008.04.015.

[8]崔珊珊.遺傳算法的一些改進(jìn)及其應(yīng)用[D].中國(guó)科學(xué)技術(shù)大學(xué)，2010.

[9]王倩，李風(fēng)軍.改進(jìn)的自適應(yīng)遺傳算法及應(yīng)用[J/OL].重慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版）：1-8[2021-05-13].