基于多目標優化與遺傳算法的公交調度模型

張荔 　馮鑫鑫 　王會龍 　張國增 　張汝峰 　劉昕偉

摘 要：結合地區公交現狀制定合理的公交調度機制，對于公共交通發展有著重要的現實意義和指導價值。本文以公交公司運營成本和乘客出行成本最小化為目標函數，考慮車輛核載、出行時間等約束條件建立多目標優化函數，構建城市公交調度模型。然后采用遺傳算法進行求解，并以黃驊市6路公交進行模型檢驗。研究表明，優化后的公交調度機制能夠有效降低公交公司的運營成本和乘客出行的時間成本。

關鍵詞：遺傳算法 多目標優化 公交調度 調度優化

1 引言

當前我國的公交系統逐步完善，然而公交系統依然存在票價不合理、乘客滿意度較低、乘客等車時間過長等問題，因此亟需構建適合地域特點的公交調度模型，實現統籌調度。本文從乘客和公交公司雙重角度出發，建立多目標優化模型，并通過遺傳算法進行模型求解。最后根據滄州市渤海新區地區特點、公交現狀，對黃驊市6路公交車調度進行優化檢驗。

2 多目標優化模型建立

2.1 模型假設

由于在公交調度優化過程中需要考慮眾多因素，因此對模型構建做出如下假設[1]：（1）公交車的車型統一;（2）公交車的行駛速度恒定;（3）所有公交車全程使用統一票價;（4）公交車運行過程中不考慮上下車換乘的時間。

2.2 問題分析

在實際公交運營過程中，一方面，要在滿足乘客的正常出行的情況下，最大程度上減少乘客出行成本，另一方面，則需要最大可能的減少公交公司的運營成本?？紤]乘客出行成本與公交公司效益，公交線路優化的具體步驟為：

步驟1：模型假設。根據公交現狀數據，對模型進行初步假設，提出針對公交公司和乘客兩者的分治策略;

步驟2：建立模型?；诮y計數據，進行模型訓練，進而構建多目標優化模型構建;

步驟3：多目標優化設計。確定影響因素以及經驗數值，并結合構架完成的模型結果，構建多目標體系;

步驟4：目標函數求解。根據多目標模型，利用遺傳算法對目標函數進行求解;

步驟5：檢驗優化結果是否為最優解，若達到優化結果，則輸出優化結果，否則返回步驟1。

2.3 模型構建

2.3.1 最小公交運營成本模型

從公交公司的角度來看，公交運營成本所占比重如圖1所示，決定公交運營成本的主要因素分別為：燃油費用、工作人員費用、車輛損耗費用、不同載客率影響下的產生費用。

在不妨礙乘客利益的情況下，保證主要因素費用達到運營成本的最小值，公交公司的運營成本即為最小，因此，針對以上四個主要因素建立公交最小運營成本模型：

（1）

其中，表示從站點到站點的距離;表示司機及相關人員的工資費用;表示公交平均每公里的油耗;表示一位乘客對客車造成的平均損耗;表示在站點上車的人數。

2.3.2 最小乘客出行時間成本函數模型

乘客出行成本比重如圖2所示，主要分為四大階段：出發地到公交站、等待公交、乘客上下車、上車后最終到達終點站。

針對乘客出行的四大階段建立最小出行時間成本模型：

（2）

其中，，分別表示小區的長度、寬度;表示在站點車內的人數;表示在公交車站等待公交的時間;表示平均發車間隔，表示公交車在站點停留時間（和取經驗常數）;表示乘客上下車使用的時間;表示從站點到站點的距離（）。

2.3.3 約束條件

1）出行時間約束

為了盡可能減少乘客的出行時間成本，優化過后帶給乘客的出行成本一定要小于乘客常規的出行成本，即：

（3）

其中表示乘客自站上車到站下車的常規時間成本。

2）車輛核載約束

由于公交車的核載人數固定，因此車輛乘客總人數不超過車輛的核載人數，為保證公交公司的運營成本，將公交車的平均滿載率約束為不低于60%。

（4）

（5）

3 模型求解

3.1 遺傳算法流程

遺傳算法是通過二進制或者實數編碼將問題的解表示為“染色體”個體，然后進行種群初始化，對種群進行進行一系列的選擇，交叉，變異操作，直至輸出適應度最優的個體，得到最終結果[2]。

1）編碼與種群初始化

首先，采用二進制對問題的解進行編碼操作，其中每個染色體就代表在一個時間段內的發車間隔，其次，發車的時間區間共14個，針對發車間隔的特點，將客流量的時間段分為客流高峰期和客流平穩期，對于高峰期的發車間隔初始種群設置為區間[5，15]任意值，對于平穩期的發車間隔初始種群設置為區間[15，30]中的任意值。種群初始化產生隨機數作為發車間隔的取值，并產生一個128bit的隨機數作為初始化路線。

2）選擇操作

利用公交的約束特征，對個體進行選擇，隨機選擇個體比較，選擇兩者中最優的個體進入種群，重復進行操作，直至達到規定的種群數量。

3）交叉操作

針對上文使用的編碼方式，通過改進交叉算子的大小來進行交叉操作。發車間隔段和路線選擇段分開交叉考慮，發車間隔段以6bit為單位隨機選擇交叉點進行交叉，路線選擇段則直接對該段所有bit選取隨機交叉點交叉操作。

4）變異操作

變異是通過賦予基因較小的變異概率實現，在選取變異基因時，需要保證變化的染色體所表示的解仍然屬于問題的可行解域。隨機產生變異點以該bit反轉作為變異點，再對該區間檢查區域范圍，若不符合區域范圍則重新變異直至滿足。

4 模型檢驗

4.1 基礎數據

本文以黃驊市6路公交為研究對象，對此線路上各個時間段的平均每日客流量進行統計， 6路公交線總長14公里，34個站點，固定的發車間隔為15分鐘，車輛的發車周期為：7：10—17：30，實行統一票價（1元/人）。由每日客流量數據分析如圖3所示，將公交的發車時段分為三個階段：客流高峰期的時間段為：7：30—8：30，17：30—19：30，客流過渡期的時間段為：13：30—15：30，客流平穩期的時間段為：6：30—7：30，8：30—13：30，15：30—17：30，19：30—20：30。

4.2 參數設計

本文使用遺傳算法進行求解過程中，具體的參數設置為：初始種群數：10000高峰期為[5.15]，平穩期為[15，30];交叉率為0.5;變異率為0.01。

4.3 結果及分析

通過遺傳算法求解過程，可以得到黃驊市6路公交車的優化的發車間隔，高峰期的發車間隔為9.2分鐘，過渡期的優化時間間隔不發生改變依然為15分鐘，平穩期的優化時間間隔為18.6分鐘，考慮到公交發車時間段的實際情況一般為整數，進一步取整后得到高峰期的發車時間間隔為10分鐘，平穩期的優化時間間隔為20分鐘，全天發車總次數為53次，優化后的公交站點線路與公交車原線路相同。

本文針對黃驊市6路公交調度問題進行了深入的研究和優化，統計數據顯示，黃驊市2路公交的日平均客流量情況與6路相仿，因此針對6路公交的優化方式同樣適用于黃驊市2路公交。

5 結論

本文通過遺傳算法求解多目標函數優化模型，實現公交優化調度模型構建，并對黃驊市6路公交車調度進行優化檢驗，研究表明，優化后的公交調度機制能夠有效降低公交公司運營成本和乘客出行成本。該多目標優化調度模型及相關算法，可以推廣到其他線路公交的調度問題，進而實現整個地區公交服務體系升級。

基金項目：2020年滄州市社會科學發展研究課題（動態需求下的城市公交柔性調度數學模型研究-以滄州市渤海新區為例2020025）;2020年滄州市科學計劃自籌經費項目（204102004）。

參考文獻：

[1]陶浪，馬昌喜，朱昌鋒，等.基于遺傳算法的定制公交路線多目標優化[J].蘭州交通大學學報，2018，037（002）：31-37.

[2]陳曉旭，項煜，楊超，等.基于遺傳算法的公交線路發車間隔優化[J].交通與運輸，2020（5）.