基于多目標(biāo)遺傳算法的機場巴士發(fā)車時刻表優(yōu)化

巫遠(yuǎn)昆，馬昌喜

（蘭州交通大學(xué) 交通運輸學(xué)院，蘭州 730070）

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

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

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

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

1 模型建立

1.1 問題描述

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

1.2 假設(shè)條件

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

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

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

3）所有車輛在規(guī)定時間進站出站，且在行駛過程中不會出現(xiàn)串車現(xiàn)象.

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

5）車輛只在車站?？浚型静煌＼?

1.3 參數(shù)符號說明

模型中出現(xiàn)的參數(shù)符號、參數(shù)的含義和參數(shù)的單位如表1所列.

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

1.4 模型構(gòu)建

以乘客出行的總時間最少和運營成本最低為優(yōu)化目標(biāo)構(gòu)建機場巴士發(fā)車時刻表優(yōu)化模型.

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

第二個優(yōu)化目標(biāo)公交公司運營費用最低目標(biāo)函數(shù)見式（9）.

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

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

2 算法求解

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

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

2.1 求解步驟

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

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

詳細(xì)求解步驟如下：

Step1 使用隨機數(shù)生成第一代父代種群P0，規(guī)模為N.

Step2 對進行快速非支配排序，快速非支配排序的過程如下：1）設(shè)定兩個參數(shù)n（i）和S（i），n（i）為種群中支配個體i的個體數(shù)，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(xiàn)（2）中的所有個體i（rank）=2.4）以此類推，對集合F（2）執(zhí)行操作3），直至所有個體的i（rank）都已經(jīng)確定.

2.2 編碼與解碼策略

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

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

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

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

3 實例分析

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

3.1 參數(shù)標(biāo)定

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

表2 模型參數(shù)標(biāo)定Tab.2 Model parameter calibration

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

3.2 仿真結(jié)果分析

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

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

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

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

表5 調(diào)度方案Tab.5 Dispatching scheme

以上方案中，當(dāng)決策者主要注重企業(yè)利益時，可選擇方案1；當(dāng)決策者主要注重機場巴士的社會效益時，可選擇方案5.在發(fā)車次數(shù)相同的前提下，將傳統(tǒng)的固定發(fā)車間隔的發(fā)車調(diào)度方案與5種優(yōu)化后的備選方案作對比，得到的結(jié)果如圖4所示.

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

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

表6 最優(yōu)發(fā)車時刻表Tab.6 Optimized timetable

3.3 行駛速度靈敏度分析

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

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

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

4 結(jié)論

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

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