基于多目標遺傳算法的機場巴士發車時刻表優化

巫遠昆，馬昌喜

（蘭州交通大學 交通運輸學院，蘭州 730070）

航空運輸是全球經濟快速增長的貢獻者之一，加速了經濟全球化［1］.同時，航空運輸也是我國交通運輸的重要組成部分，在中長途運輸，尤其是客運中發揮著重要作用.但是，由于航空運輸的特殊性，機場一般都建在遠離城市中心的郊區，因此機場與城市中心區域的距離一般比較長.機場巴士具有運營成本低、線路靈活、乘客乘車方便等優點［2］，是一種具有良好通達性、調度方便的公共交通工具，承擔著重要的機場接駁任務［3］，可以很好的連接城市中心和機場.合理的機場巴士時刻表可以減少乘客的等車時間，降低運營成本，更好地為乘客服務.然而，許多機場巴士發車時刻表設計不合理，從而造成乘客等待時間長、時間延誤大、運行效率低等問題，嚴重影響乘客乘坐機場巴士的積極性，甚至降低機場的運營效率.

目前，有關機場巴士時刻表設計的研究較少，學者們主要關注城市公交和軌道交通，大多數文獻集中在研究城市公交和軌道交通的時刻表設計上.孫楊等［4］將乘客的到達時間設為不確定值，建立魯棒優化模型，對公交時刻表進行優化，將結果與固定需求下的時刻表進行比較后，發現魯棒優化后的發車時刻表抗干擾能力強，更符合需求.孫芙靈［5］從乘客需求角度出發，確定發車間隔，并建立調度模型，使用時間步長法、等效法進行求解.Li等［6］將火車線路中各站點的上下車乘客數量設為模糊值，以此建立火車發車時刻表優化模型，得到了既符合乘客需求，又降低了運營成本的發車時刻表.馬天山等［7］根據乘客換乘時間分布規律建立乘客換乘總時間模型，并運用遺傳算法求解，驗證了模型的有效性.Sun等［8］考慮地鐵運行期間高峰期和非高峰期客流的差異，以提高乘客的滿意度為目標，設計不同的發車時刻表針對客流的不均勻性，減少擁堵.Salicru等［9］在等待時間比較理想的情況下，考慮了乘客的最小出行時間，設計了一種在路網中求得最優公交發車時刻表的優化算法，得到了最優公交調度方案.吳亮等［10］建立出行者與公交運營者間的雙方非對稱演化博弈模型，利用差異化的發車頻率平衡出行者與公交運營者的利益.黃志鵬等［11］結合出行時段、列車等級和舒適性是影響旅客滿意度的三個主要因素，構建旅客出行滿意度雙層規劃模型，設計了基于模型特點的啟發式算法求解，通過算例進行了仿真實驗和分析，驗證了該模型及算法的有效性.

然而，與城市公交發車時刻表研究所取得的巨大進展相比，機場巴士發車時刻表的優化卻沒有得到足夠的關注，對于機場巴士的研究主要集中在客流分配和路線優化上.美國聯邦航空管理局［12］提出了基于市場的六步策略，提高了美國機場的服務的質量.陸婧等［13］考慮市場培育期與機場市場份額，構建了動態巴士時刻表優化模型，并用第二代非支配排序遺傳算法（non-dominated sorting genetic algorithms-II，NSGA-II）算法求解模型，動態優化了機場巴士發車時刻表.Nesset等［14］研究了多機場區域轉換成本對乘客態度和忠誠度的影響.周和平等［15］構建了機場巴士線路網絡的優化模型，求解旅客出行時間的最小值.包丹文等［16］為了優化了機場巴士網絡，以提高可靠性的為目標，基于BP神經網絡，構建了機場巴士的可靠性預測模型并求解.史澈等［17］針對現階段國內旅客空鐵聯運廣泛采用的機場巴士換乘模式，建立基于不同時段客流量的換乘巴士發車間隔優化模型并求解，優化機場換乘巴士發車間隔.盧天偉等［18］提出考慮彈性需求的機場客運樞紐間多方式時刻表協同優化方法，以乘客等待總時間，時刻調整總數量，時刻調整總時間最小為優化目標，構建樞紐間多方式時刻表協同優化模型，設計非支配排序遺傳算法求解，縮短乘客等待時間.

在前人研究的基礎上，本文考慮機場巴士時刻表設計的具體特點，對單條機場巴士線路進行研究.分析客流分布特點，考慮乘客乘車時間、等待時間和上下車取放行李時間，確定乘客出行成本優化目標，同時考慮公交公司的利益，控制運營成本，建立機場巴士發車時刻表雙目標優化模型.應用NSGA-II算法，求解模型，得到多個發車調度方案，可供決策者選擇.

1 模型建立

1.1 問題描述

公交發車間隔指的是某條公交線路上，上行或下行方向上的相鄰兩輛公交車經過同一站點的時間間隔.發車間隔長意味著發車頻率低，發車次數少.減少發車次數可以降低公交公司的運營成本，但是，這會增加乘客在車站的候車時間，所以從乘客的角度考慮，應該提高發車頻率減少乘客出行時間［19］.在制定發車時刻表時，不僅要考慮為乘客提供高的服務質量，還要考慮企業的成本.如果為了追求利益而降低服務質量，則違背了公交服務于乘客的原則.如果忽視了經濟效益，則調度方案可能會因為運營成本過高而增加了公交公司的成本，導致調度方案中的發車時刻表無法實施.

1.2 假設條件

為了簡化模型，同時減小運用多目標遺傳算法對模型求解的難度，對該模型進行一些理想化的假設，具體假設如下：

1）司機服從調度安排，駕駛公交車在公交專用道上勻速行駛.

2）所有車輛都是相同的車型，且載客量足夠，不會出現車站內乘客滯留現象.

3）所有車輛在規定時間進站出站，且在行駛過程中不會出現串車現象.

4）車輛沿線道路均暢通，行駛過程中無交通事故等意外事故發生.

5）車輛只在車站停靠，中途不停車.

1.3 參數符號說明

模型中出現的參數符號、參數的含義和參數的單位如表1所列.

表1 符號定義Tab.1 Summary of the notation

1.4 模型構建

以乘客出行的總時間最少和運營成本最低為優化目標構建機場巴士發車時刻表優化模型.

機場巴士每天的運營時間段內，所有乘客在車站的等車時間之和見式（1）～（2）

第二個優化目標公交公司運營費用最低目標函數見式（9）.

模型需滿足以下約束條件：

巴士的發車間隔約束.巴士的發車間隔必須在一定的時間范圍之內，如果發車間隔過長，則會導致乘客的等車時間過長，使乘客產生焦躁情緒，違背了公共交通要具有社會效益的原則；如果發車間隔過短則會導致增加公交調度的難度，使公交調度的成本過高.巴士發車間隔需滿足式（10）.

2 算法求解

車輛調度屬于NP-hard問題，復雜度較大，難以使用精確算法求得最優解，適合使用智能算法求解［20］.模型中的兩個優化目標相互制約，一個目標的改善有可能會引起另一個目標性能的降低，故不可能同時優化兩個目標，且決策者對企業效益與乘客效益的重視程度不同，難以使用固定權重的線性加權法求解.NSGA-II是基于遺傳算法的多目標優化算法［21］，于2000年由Deb等［22］提出，被廣泛運用于復雜的，非線性的多目標優化問題，具有解分布均勻，多樣性好，有精英策略等優點，可以找到多目標優化問題的Pareto解集，求得Pareto最優解，相較于NSGA算法，NSGA-II算法使用快速非支配排序，算法的運行速度更快，復雜度更低［23］.

多目標優化問題需要尋找Pareto解集，即找到Pareto最優解，Pareto最優可以理解為，Pareto解集中的每個解相較于其他解都處于非支配地位，不存在比其中至少一個目標好且其它目標非劣的更好的解.本文采用NSGA-II求解發車時刻表優化模型.

2.1 求解步驟

算法的基本流程如圖1所示.

圖1 算法流程Fig.1 Flow framework of solution algorithm

詳細求解步驟如下：

Step1 使用隨機數生成第一代父代種群P0，規模為N.

Step2 對進行快速非支配排序，快速非支配排序的過程如下：1）設定兩個參數n（i）和S（i），n（i）為種群中支配個體i的個體數，S（i）為被個體i支配的個體集合.2）把種群中所有滿足n（i）=0條件的個體存放在集合F（1）中，令F（1）中的所有個體i（rank）=1.3）遍歷F（1）中所有被個體j支配的個體集合S（j），將S（j）中每個個體k的n（k）減1，如果n（k）-1=0，則將個體k存入集合F（2），F（2）中的所有個體i（rank）=2.4）以此類推，對集合F（2）執行操作3），直至所有個體的i（rank）都已經確定.

2.2 編碼與解碼策略

機場巴士調度問題的解為研究時段巴士在樞紐站的發車時刻表.我們可以先確定首班巴士在樞紐站的發車時刻，再求出研究時段內所有巴士的發車間隔，進而得到機場巴士的發車時刻表.

調度問題可以采用二進制編碼或整數編碼，本文采用二進制編碼方法對染色體進行編碼，染色體字符串長度表示整個研究時段的長度.每一位上的數字用dk表示，dk=｛0，1｝，當dk=0時，表示在該時刻不發車；當dk=1時，表示在該時刻發車.以下舉例時間精度為10 min，則染色體編碼示意圖如圖2所示.

圖2 染色體編碼示意圖Fig.2 Chromosome coding diagram

解碼后可以得到，研究時段長度為340 min，在這個時間段內共發車9次，假設首班車發車時間為10∶00，那么這9班車分別在10∶00、10∶30、11∶30、12∶20、13∶10、13∶40、14∶10、14∶50、15∶40發車.

3 實例分析

以蘭州市中川國際機場某條機場巴士線路為研究對象，優化該線路的巴士發車時刻表.該線路全長71 245 m，最大發車次數限制13次，客流在時間分布上具有一定的不均勻性.該線路共6個站點，巴士在城市路段（站點1-5）平均車速為20 km/h，在高速路路段（站點5-6）平均車速為90 km/h.選取6∶00～14∶00時間段驗證發車時刻表優化模型.

3.1 參數標定

模型的相關參數，各站點間的距離和巴士在相鄰兩站間的行駛時間如表2～4所列.

表2 模型參數標定Tab.2 Model parameter calibration

表3 各站點間距Tab.3 Distance between stations m

3.2 仿真結果分析

使用NSGA-II算法對模型進行求解，設置初始種群規模為50，迭代次數為500，選擇操作采用二進制錦標賽法，交叉操作采用單點交叉，變異操作采用二進制變異，交叉概率和變異概率分別設置為0.9和0.3.使用C++仿真后共得到11個結果，將所有結果在平面坐標中標定出來，繪制出行成本與運營成本關系圖，如圖3所示.

圖3 出行成本與運營成本的關系Fig.3 Relationship between travel cost and operation cost

從出行成本與運營成本關系圖中可以看出，形成了較為明顯的pareto前沿面，其中，符合約束條件，能較好平衡乘客和公交公司利益的解有5個，調度方案如表5所列.

表4 車輛在相鄰站點間的行駛時間Tab.4 Driving time between stations min

表5 調度方案Tab.5 Dispatching scheme

以上方案中，當決策者主要注重企業利益時，可選擇方案1；當決策者主要注重機場巴士的社會效益時，可選擇方案5.在發車次數相同的前提下，將傳統的固定發車間隔的發車調度方案與5種優化后的備選方案作對比，得到的結果如圖4所示.

圖4 優化前后出行成本比較Fig.4 Comparison of travel costs before and after optimization

從圖中可以得出，在發車次數相同的情況下，優化后發車方案的出行成本皆低于原發車方案，較原發車方案出行成本平均下降3.84%，發車9次時出行成本下降最顯著，出行成本降低了4.62%.綜合權衡乘客時間成本和企業運營成本，選擇方案3為相對最優調度策略，得到的發車時刻如表6所列.考慮了客流隨時間分布的不均勻性，在早高峰期提高了發車頻率，減小了乘客的等車時間，同時僅比傳統的整點發車調度方案增加一次發車，也兼顧了公交公司的利益.

表6 最優發車時刻表Tab.6 Optimized timetable

3.3 行駛速度靈敏度分析

對巴士的行駛速度進行靈敏度分析，把巴士的速度提高5、10、15、20 km/h，計算發車次數為9時，解的出行成本如圖5所示.

圖5 巴士速度與出行成本的關系Fig.5 Relationship between bus speed and travel cost

由圖5可以看出，隨著巴士速度的提升，出行成本從34 356減少至26 747，但是速度每提升5 km/h，出行成本減少的值逐漸變小.實際中，決策者可以提高巴士速度來降低乘客出行成本，但是速度提高值過高時，降低乘客出行成本的效率會降低，且在城市中如果巴士的速度太快，會影響乘客的乘車舒適度以及增加行車的危險性.

4 結論

本文針對機場巴士調度綜合優化問題，兼顧公交公司與出行者的利益，考慮了乘客上車以及存放行李的時間，更加符合實際情況.綜合分析模型的兩個目標函數，運用NSGA-II，求解近似Pareto最優解集，得到多個合理的發車時刻表優化方案，對發車時刻表進行優化，具有一定的應用價值.

但在構建模型過程中僅考慮上行線路，沒有將問題與機場的到達客流相結合，也沒有考慮其他線路公交車輛對本線路公交車輛運行的影響，本文也未充分考慮道路的實際交通情況，只是簡單的將線路阻抗設為定值.這些將在下一步的研究工作中進行完善.