林鑫?張海波?鄭鰻芝

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

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

中圖分類號：U492.22;TP18 文獻標識碼：A 文章編號：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以乘客出行時間成本最小為目標，以車輛容量、客流分配為約束條件，建立以車輛發(fā)車頻率為優(yōu)化目標的非線性規(guī)劃模型[1]。DORIGO等在研究公交線網(wǎng)問題時，以線路條件、道路條件、車輛運營時間為約束條件，建立了乘客出行OD矩陣的數(shù)學(xué)模型，以優(yōu)化車輛發(fā)車頻率[2]。FABIANC等在優(yōu)化公交調(diào)度的過程中考慮了乘客的換乘時間，運用遺傳算法解決了公交車發(fā)車頻率問題[3]。國內(nèi)學(xué)者也在相應(yīng)問題上進行了大量研究。朱金壽等在建立多目標規(guī)劃模型時考慮了公交公司的經(jīng)濟成本和乘客的出行成本，并用遺傳算法對模型進行求解[4]。陳濤在大數(shù)據(jù)中挖掘乘客的出行規(guī)律，并結(jié)合影響公交調(diào)度的因素，建立公交調(diào)度優(yōu)化模型進行求解[5]。

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

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

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

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

1.2 模型的建立

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

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

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

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

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

一天的總運營成本為：

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

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

2 遺傳算法求解過程

2.1 編碼

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

2.2 初始種群

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

2.3 適應(yīng)度評價

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

2.4 算子

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

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

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

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

3 案例分析

3.1 運營線路基本信息

本文針對成都市蒲江縣櫻桃山風(fēng)景區(qū)旅游公交進行調(diào)度優(yōu)化。該旅游線路全長為10 km，共設(shè)18個站點，固定發(fā)車間隔為5 min，統(tǒng)一票價為5元/人。選取櫻桃節(jié)期間（4—5月）的一個周六作為研究時段進行靜態(tài)優(yōu)化。把一天的運營時段分為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，時間長度分別為60 min、60 min、60 min、240 min、60 min和120 min。6個時段的客流量分別為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ā)車時間間隔均為1 min。公交車額定載客人數(shù)為60人，公交車單位運營成本為6.4元/km。

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

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

3.3 計算結(jié)果

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

4 結(jié)語

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

參考文獻：

[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].交通與計算機，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].測控技術(shù)，2014（2）：124-126.

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