基于遺傳算法的公交車調度優化研究

譚華

（桂林航天工業學院，廣西 桂林541004）

公交調度管理是公交企業運營和業務管理的核心，對公交調度機制進行優化，建立合適的公交調度方案，可以有效地提高城市公交運營水平和服務質量，但長期以來，我國很多城市的公交企業在制定公交運營方案時，主要依靠管理人員經驗和直覺，導致公交運行水平和服務質量都很低下，從而影響民眾公交出行的使用比例和公交企業的經濟收益。所以，通過對公交車調度的研究可為現代化公共交通提供技術支持和服務保障，實現公交調度運營的高效率、高效益，為乘客提供準時、快速和舒適的服務，提高公共交通的吸引力，從而提高企業的經濟效益，方便居民出行。

鑒于此，大量國內學者從不同角度對公交車調度問題進行了研究，例如，2016 年丁勇等[1]針對泰州市公交智能化建設方面存在的技術問題，采用基于遺傳算法對泰州市的公交調度問題進行了研究；2017 年韋尚成[2]提出了一種臨界- 遺傳算法對公交調度問題進行了研究；2017 年鄧芳玥[3]采用改進遺傳算法對公交線路調度模型進行了研究；2019 年武斌[4]研究了公交調度的模糊多目標規劃模型，并通過遺傳算法驗證了模型的合理性。同年，彭蝶飛[5]等根據景區現有的公共交通資源和旅客的出行規律，構建了以旅游公交營運成本、游客等待成本和游客流失成本三方面優化目標的模型，并通過遺傳算法進行了驗證研究。2020 年徐晨暢等[6]提出了一種應對突發交通狀況的公交智能調度算法，并通過遺傳算法進行了求解驗證。

本文在總結和分析前人對公交調度問題的研究方法后，以南寧市某一公交線路為例，根據其日平均客流情況，建立了該線路的公交調度優化數學模型，最后，通過遺傳算法求解得到該線路公交車的最優化發車時間間隔及配車數量。研究表明，采用優化后的公交調度機制，能有效降低公交運行成本和提高乘客滿意度。

1 數學模型的建立

1.1 模型假設

公交調度的數學模型主要是對實際公交調度問題的抽象和概況，因此不可能完全考慮到所有的復雜外部因素，必須合理的對外部因素做相應的限制，公交車的調度模型，具有復雜和受外部影響因素多的特點，對此，本文進行了如下假設：

（1）公交車輛為同一車型，且公交車運行情況良好；

（2）乘客到達站點數量服從均勻分布；

（3）乘客上車的時間可以忽略不計；

（4）公交車只運行一條公交線路上，且只考慮單程車運行；

（5）乘客消耗的單位時間費用是固定值；

（6）公交車輛單位乘次運營成本是固定值；

（7）全程實行統一票價。

1.2 目標函數及約束條件

在實際的公交調度中，公交車輛調度優化的目標函數，需要從乘客利益和公交公司利益的角度來考慮，從公交公司的角度，需盡量大的發車間隔以減少發車次數，從而降低運營成本來提高公司的收入，從乘客的角度，需要盡量小的發車間隔，以最大限度地降低因等車和換乘帶來的交通費用損失。

本文根據公交運營時間及乘客到站密度情況，將公交車運營時段進行分時段處理，為了建立易于求解的優化模型，我們將該公交該線路的發車時段分為若干個高峰時段和若干個平峰時段。以全天公交公司運營成本和乘客等車損失費用的總和最小為優化目標，分別建立高峰時段和平峰時段的目標函數及約束條件。

其中，高峰時段的費用函數f1如（1）式所示：

考慮到公交公司利益，這里我們以公交車平均滿載率不低于60%為目標函數的約束條件，如下（4）、（5）式所示：

以上數學模型中符號說明如下表1 所示：

2 基于遺傳算法的公交調度優化模型求解

2.1 遺傳算法求解概述

遺傳算法[7]（Genetic Algorithm, GA）是由美國密歇根大學的John H. Holland 教授及其學生于20 世紀60 年代末到70 年代初提出的。是模擬達爾文生物進化論的自然選擇和遺傳機理的生物進化過程的計算模型算法。自其誕生以來就受到許多學者的關注。經過多年的不斷發展，在基礎理論和算法設計研究上都取得了長足的進步，尤其是在越來越多的領域中得到成功應用。其中在公交調度優化方面也有著十分廣泛應用，這里也借助遺傳算法對公交調度優化目標函數進行求解。

2.2 模型的遺傳算法求解步驟

遺傳算法求解的基本步驟：

（1）首先是編碼，一般采用二進制編碼或實數編碼把問題的解表示成“染色體”（個體）；然后進行種群初始化，就是依據編碼規則給出種群的初始解，也即隨機產生一群“個體”。

（2）計算適應度，即根據適應度函數計算每一個個體的適應度值，然后按適者生存的原則，從中選擇出適應度較大的“個體”進行復制，再通過交叉、變異過程產生更適應環境的新一代“個體”種群，即子代。

（3）重復第2 步。

（4）經過這樣的一代一代地進化，達到終止條件，最后就會收斂到最適應環境（適應度最大）的一個“染色體”（即個體）上，那它就是問題的最優解。圖1 所示，給出了基本遺傳算法求解流程圖。

圖1 基本遺傳算法求解流程圖

①編碼。編碼是設計遺傳算法首要解決的問題。選擇合適的編碼方式，對問題的求解精度有非常關鍵的影響，由于二進制編碼的隨機性使得其局部搜索能力較差，尤其在高精度的問題上不夠理想，鑒于此，本文采用實數編碼的方法，在這種編碼方法中，染色體的各個基因就是決策變量的真實值。每個染色體代表一個時間段的發車間隔。

②初始種群。在本文中，根據經驗法，初步選擇初始群體中的個體值。對于高峰時段的初始值可以選擇[5,15]區間的任意值作為初始值，對于平峰時段可以選擇[15,30]區間的任意值作為初始值。

③適應值函數。遺傳算法的適應度是用來判斷群體中的個體的優劣程度的指標，它是根據所求問題的目標函數來進行評估的。這里直接以待求解的目標函數轉換為適應度函數，該公交調度模型的目標函數為最小化問題，所以適應度函數為fD=min（mf1+nf2）

④算子選擇。遺傳算法的操作算子有選擇、交叉和變異這三種，它們分別模擬了生物繁衍、交配和基因突變。在選擇算子方面，我們這里采用輪盤賭選擇算子；在交叉算子方面，我們采用算術交叉算子，在變異方面，我們采用均勻變異算子。

⑤終止條件。設定最大的進化代數，當遺傳算法運行到該參數指定的世代，計算終止。

3 實例分析

本研究以南寧市某一條公交線路為研究對象, 對該線路上行方向的發車時刻表進行優化。如圖2 所示是該線路每日的平均客流變化情況。該公交線路全長16.2 公里，30 個站點，固定發車時間間隔為15 分鐘，實行統一票價（2 元/人），該線路運營時間為6:30-21:30（共15 小時）。

圖2 公交線路平均日客流情況

這里我們將公交車一天的運行時間分為9 個時段，又考慮到，公交發車一天內的發車間隔在個時段內不會頻繁更換，將該線路一天的發車時段用高峰時段、平峰時段進行標記，如表2所示。最終客流平峰時段為：6:30-7:30、8:30-12:00、12:30-14:00、14:30-17:30、18:30-21:30，共12 個小時。高峰時段為：7:30-8:30，12:00-12:30，14:00-14:30，17:30-18:30，共3 個小時。

表2 運行時間區間及各時段劃分

根據建立的公交優化數學模型，采用遺傳算法進行仿真求解。算法中需要的主要參數：發車間隔變化區間[5，30]，且取值為0.5 的整數倍。初始種群規模N=20，交叉概率Pc =0.9，變異概率Pm =0.01，最大迭代次數G=200。高峰時段費用損失權重系數為0.6，平峰時段費用損失權重系數為0.4，高峰時段第j 車站乘客到達率為0.85，平峰時段第j 車站乘客到達率0.55，高峰時段公交公司費用消耗的加權系數0.7，高峰時段乘客等車的費用損失加權系數0.3，平峰時段公交公司費用消耗的加權系數0.6，平峰時段乘客等車的費用損失加權系數0.4。

最后，通過仿真求解，得到南寧市該路公交車的優化發車時間間隔，高峰時段的優化間隔時間為8.3 分鐘，平峰時段的優化間隔時間為17.8 分鐘，為了考慮到實際發車間隔一般為5 的倍數，同時一天的發車時刻表不會頻繁更換，最終得到了次優化的發車間隔，高峰時段發車間隔為10 分鐘、平峰時段發車間隔為20 分鐘，這樣使得總發車趟數為54 趟、滿客率平均為80%，公司運營成本節約10%，乘客滿意度提高20%。

4 結論

本文針對南寧市某一公交線路的公交調度問題進行了研究，建立了該線路的公交調度優化數學模型，通過遺傳算法求解得到該線路公交車的最優化發車時間間隔及配車數量。研究表明，采用優化后的公交調度機制，能有效降低公交運行成本和提高乘客滿意度。利用本文建立的公交調度模型，對其他公交線路的調度優化有一定的借鑒意義和參考價值。