陶燁

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

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

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

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

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

1.1 模型假設(shè)

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

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

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

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

Pkj=ukj/Tk

mk=tk/Δtk

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

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

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

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

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

Wmin=W1+W2

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

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

F=min（F1+F2）

以滿載率不低于60%為約束條件

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

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

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

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

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

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

崔珊珊[8]在設(shè)計自適應(yīng)交叉率和變異率時，主要考慮平均適應(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的值越小，見圖1。

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

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

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

3 實(shí)例分析

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

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

根據(jù)建立的公交優(yōu)化數(shù)學(xué)模型，采用改進(jìn)過后的遺傳算法進(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。高峰時段成本損失的權(quán)重系數(shù)是0.6，平峰時段0.4，高峰時段到達(dá)率0.88，平峰時段0.65，高峰時段公交公司的成本消耗的加權(quán)系數(shù)是0.7，高峰時段乘客的成本損失的加權(quán)系數(shù)是0.3。平峰時段公交公司費(fèi)用消耗的加權(quán)系數(shù)是0.6，平峰時段乘客登車的費(fèi)用損失加權(quán)系數(shù)0.4。

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

4 結(jié)語

本文對拉薩市某公交線路的公交調(diào)度進(jìn)行了研究，建立了該線路公交調(diào)度優(yōu)化的數(shù)學(xué)模型，利用改進(jìn)后的遺傳算法得到了該線公交調(diào)度的最優(yōu)發(fā)車時間間隔和最優(yōu)公交調(diào)度數(shù)量。數(shù)據(jù)表明，優(yōu)化后的公交調(diào)度機(jī)制可以提高乘客滿意度，有效降低公交成本。本文建立的公交調(diào)度優(yōu)化數(shù)學(xué)模型對于其他線路的公交調(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]尹詩德.基于模擬退火的混合布谷鳥算法求解公交調(diào)度問題.2018.華南理工大學(xué)，MA thesis.

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

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

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

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

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

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