高鐵車站接運公交時刻表與車輛調度綜合優(yōu)化

郭小樂， 宋 瑞， 何世偉， 黎浩東， 孫 楊， 張英群

(1. 北京交通大學 綜合交通運輸大數(shù)據(jù)應用技術交通運輸行業(yè)重點實驗室, 北京 100044；2. 交通運輸部科學研究院, 北京 100029)

近年來，我國高速鐵路發(fā)展迅速，大部分新建高鐵站位于城市郊區(qū)或新城[1]。相當數(shù)量城市的高鐵站尚未接入城市軌道交通，或城市軌道交通覆蓋地區(qū)較小。而且隨著高鐵運營時間的延長，存在部分高鐵列車在城市軌道交通結束運營后抵達高鐵站的問題。在這些情況下，高鐵站接運公交是集散高鐵客流的重要交通方式，這對高鐵站接運公交與高鐵站的銜接提出了較高要求。高鐵站接運公交主要服務于高鐵客流的集散。合理的接運公交時刻表可以實現(xiàn)客流的快速集散與輸送乘客數(shù)的最大化，吸引更多高鐵乘客選擇公共交通出行，降低社會成本。合理的車輛調度計劃可以有效減少運用車輛數(shù)，降低企業(yè)運營成本。時刻表和車輛調度問題相關性較強，對兩個問題進行綜合優(yōu)化兼顧了社會和公交企業(yè)的利益，更具現(xiàn)實意義。

部分學者對公交時刻表與車輛調度綜合優(yōu)化問題進行了研究。文獻[2-5]研究了等發(fā)車間隔時刻表與車輛調度綜合優(yōu)化問題。高鐵到達客流在時間分布上集中度高，同時還具有一定的不均勻性，高鐵站接運公交的發(fā)車時刻應與高鐵列車到站時刻適當配合，等發(fā)車間隔時刻表并不適用于高鐵站接運公交。文獻[6-11]建立數(shù)學規(guī)劃模型求解不等發(fā)車間隔時刻表與車輛調度綜合優(yōu)化問題，但均未考慮浪涌式大客流對運營調度的影響。實際運營中，在高鐵客流到達高峰期時，可能會出現(xiàn)乘客不能及時換乘的現(xiàn)象，大量客流瞬時積聚，給城市交通系統(tǒng)和高鐵站造成巨大壓力。另外，過長的候車時間也可能造成公交客流流失。針對這一現(xiàn)象，文獻[12]考慮了快速公交首站和地鐵接駁換乘大客流常態(tài)化導致客流損失的情況，對快速公交的發(fā)車間隔進行決策；文獻[13]考慮了受公交車輛的運能限制而發(fā)生乘客在換乘站點滯留的現(xiàn)象，建立數(shù)學模型以調整公交線路的發(fā)車時刻和發(fā)車間隔。但上述文獻均未考慮時刻表與車輛調度綜合優(yōu)化問題。

本文針對客流高峰期高鐵站接運公交時刻表與車輛調度綜合優(yōu)化問題，以流失乘客數(shù)最少、使用的公交車輛數(shù)最少為優(yōu)化目標，以車輛滿載率、乘客等待時間、最大可用公交車輛數(shù)、公交車輛執(zhí)行車次的順序等為約束條件，建立了時刻表與車輛調度綜合優(yōu)化模型，設計了非支配排序遺傳算法對該模型進行求解，并用算例驗證了模型和算法的正確性與有效性。

1 問題描述

某高鐵站附近往往存在多條接運公交線路的首站。公交車輛從首站出發(fā)，沿線路行駛至最遠端車站后按原路線返回首站，再執(zhí)行下一車次。公交車輛僅可在首站跨線執(zhí)行其他線路的車次，即車輛在不同線路間的空駛距離為0。對于這些線路實施區(qū)域調度可以實現(xiàn)資源的優(yōu)化配置，提高公交車輛運營效率，因此本文采用區(qū)域調度模式對所有公交車輛進行統(tǒng)一調度。

高鐵客流到發(fā)集中度高，在時間分布上具有瞬時性與不均勻性[14]。在高鐵客流到達高峰期時，接運公交首站的客流需求激增，可能出現(xiàn)大量客流積聚，給高鐵站和城市交通系統(tǒng)造成巨大壓力。高鐵乘客具有時間價值高的特點，到達后往往希望快速出站換乘市內交通，導致接運公交首站經常出現(xiàn)浪涌式大客流。另外，較高的時間價值也意味著過長的候車時間會造成乘客的流失。

因此，在客流高峰期高鐵站接運公交主要起到疏散高鐵到站乘客的作用。由于高鐵列車到站時刻分布不均勻，并且高鐵客流具有集中到達的特點，為實現(xiàn)高效的客流疏散，減輕高鐵站乘客積聚壓力，高鐵站接運公交的發(fā)車時刻應適當與高鐵列車到站時刻相配合，而不適用等發(fā)車間隔時刻表。增加發(fā)車次數(shù)可以疏散更多高鐵到站乘客，但往往意味著用車數(shù)的增加。決策者需要在發(fā)車次數(shù)與用車數(shù)之間權衡，以實現(xiàn)社會成本與企業(yè)成本的最小化。本文研究如何合理編制高鐵站接運公交發(fā)車時刻表與車輛調度計劃，從運營角度實現(xiàn)高鐵站接運公交與高鐵列車的有效銜接，運送高鐵到站客流由接運公交首站向目的地疏散的客流運輸過程。

2 數(shù)學模型

為方便建模，添加1條虛擬公交線路l′，2個虛擬發(fā)車時刻i′、i′′。該虛擬公交線路的全程走行時間為0，僅可能在i′、i′′發(fā)車。需要決策的變量如下：

(5) 公交車輛執(zhí)行車次順序的0-1決策變量zlmij，當存在公交車輛執(zhí)行完公交線路l在時刻i發(fā)出的車次后緊接著執(zhí)行公交線路m在時刻j發(fā)出的車次時，則zlmij=1，否則zlmij=0。

構建如下高鐵站接運公交時刻表和車輛調度綜合優(yōu)化模型。

( 1 )

( 2 )

s.t.

?i∈I,l∈L

( 3 )

( 4 )

?i∈I,l∈L,g∈G

( 5 )

?i∈I,l∈L,g∈G

( 6 )

( 7 )

?i,j∈I,gtj

( 8 )

( 9 )

(10)

(11)

?j∈I,m∈L

(12)

(13)

?i,j∈I,l,m∈L

(14)

(15)

(16)

(17)

(18)

?i,j∈I∪i′∪i″,l,m∈L∪l′,g∈G

式( 1 )為目標函數(shù)，表示最小化流失乘客數(shù)；式( 2 )為目標函數(shù)，表示最小化使用公交車輛數(shù)。模型中的約束條件：式( 3 )表示乘客只能換乘在時刻ti發(fā)車的公交車次，且換乘至某公交車次上的總乘客數(shù)須滿足公交線路的最大、最小滿載率約束；式( 4 )為乘客只能換乘時間條件允許的公交車次，且某列車上換乘至某公交車次的乘客數(shù)須滿足公交線路的最大滿載率約束；式( 5 )、式( 6 )分別為乘客只能換乘在其所在的列車到達高鐵站之后以及在其因等待時間過長而放棄換乘之前發(fā)車的公交車次；式( 7 )為所有到達的乘客或者換乘成功，或者因等待時間過長而放棄換乘；式( 8 )為某時刻到達的乘客必須等在其之前到達的乘客換乘完畢才能開始換乘；式( 9 )為某時刻到達的乘客在超過最長等待時間之前不會流失；式(10)為決策變量關系約束；式(11)為流失的乘客總數(shù)不能超過要求的最大流失乘客數(shù)；式(12)為某公交車輛在執(zhí)行某實際公交車次之前和之后分別只能執(zhí)行1個公交車次；式(13)為實際使用的公交車輛數(shù)不能超過最大可用的公交車輛數(shù)；式(14)為某公交車輛必須完成上一公交車次后才能開始執(zhí)行下一公交車次；式(15)為公交車輛只能執(zhí)行實際發(fā)出的公交車次；式(16)、式(17)分別為換乘成功和放棄換乘的乘客人數(shù)非負約束；式(18)為0-1決策變量約束。

3 模型求解算法

本文構建的模型為多目標優(yōu)化模型，采用產生式方法求解問題的Pareto解集，向決策者提供多個時刻表與車輛調度方案更具現(xiàn)實意義。另外，車輛調度問題(Vehicle Scheduling Problem)屬于NP-hard問題[15]，因此公交時刻表與車輛調度綜合優(yōu)化問題也屬于NP-hard問題，問題復雜程度較大，很難使用精確算法在有限時間內求得最優(yōu)解。本文基于NSGA-Ⅱ算法設計求解算法。NSGA-Ⅱ算法是一種較為成熟的多目標智能優(yōu)化算法，在城市公共交通領域，NSGA-Ⅱ已得到廣泛應用[16-19]，取得了良好效果，其詳細介紹可以參見文獻[20]。

3.1 個體編碼方式

個體編碼方式見圖1。各線路時刻表采用0-1編碼方式，0表示該線路在某時刻不發(fā)車，1表示發(fā)車。

3.2 個體適應度評價

采用模型的目標函數(shù)即流失的最少乘客數(shù)和所需的最少公交車輛數(shù)對個體進行評價。假設每個車次只能發(fā)出1輛車，則當車輛容量、各時段最大、最小滿載率、乘客最長等待時間以及各高鐵列車上的換乘需求確定時，最少流失乘客數(shù)即可通過求解模型M1求得。

M1：minFTT(X)

s.t.

式( 3 )～式(11)

式(16)～式(17)

?i∈Ip,p∈P,l∈L,g∈G

(19)

同理，當各公交線路的全程走行時間和最大可用公交車輛數(shù)確定時，所需的最少公交車輛數(shù)可通過求解模型M2求得。

M2：minFVS(X)

s.t.

式(12)～式(15)

zlmij∈{0,1}

?i∈Ip,j∈Iq,p,q∈P,l,m∈L

(20)

模型M1、M2均為線性規(guī)劃模型，可通過調用ILOG CPLEX數(shù)學優(yōu)化引擎進行求解。

3.3 不可行解的處理方法

由于本文建立的多目標優(yōu)化模型約束較多，隨機生成的初始種群極易產生不可行個體。另外，算法交叉、變異過程的隨機性導致在尋優(yōu)過程中也極易產生不可行個體。大量不可行解的存在將極大影響算法的尋優(yōu)效率與效果，本文采取以下方法解決這一問題。

(1) 在算法的交叉、變異的過程中松弛模型中的式(11)，也允許不滿足模型其他約束的不可行解存在，對于不滿足除模型中的式(11)以外的其他約束的不可行解，將其流失乘客數(shù)或所需的公交車輛數(shù)設為一個較大值。

(2) 為提高算法效率，在保證個體滿足除式(11)以外的其他約束的前提下隨機生成初始種群。為達此目的，可采用如下規(guī)則產生初始種群個體。

Step1隨機生成一個個體。

Step2求解模型M1(不含式(11))，M2，若模型M1，M2均可求得最優(yōu)解，則M1，M2的最優(yōu)解目標值分別為該個體的流失乘客數(shù)與所需車輛數(shù)，規(guī)則終止；否則轉Step3。

Step3隨機選擇該個體編碼值為1的某個基因位，令其編碼值為0，轉Step2。

(3) 如前所述，由于在種群初始化及交叉、變異過程中暫未考慮模型中的式(11)，在上述過程中產生的個體的流失乘客數(shù)可能多于最大流失乘客數(shù)。為盡快獲得滿足最大流失乘客數(shù)約束的可行解，縮短運算時間，引入“車次插入”算子，規(guī)則如下。

Step1設置“車次插入”概率p′、種群規(guī)模Z，令k=0。

Step2若k=Z，規(guī)則終止；否則對當前種群中的個體k生成隨機數(shù)rk，若rk>p′或個體k流失乘客數(shù)不多于最大流失乘客數(shù)，轉Step5；否則轉Step3。

Step3隨機選擇該個體編碼值為0的某個基因位n，令其編碼值為1，求解模型M1，M2。

Step4若模型M1，M2均可求得最優(yōu)解，則更新該個體的流失乘客數(shù)與所需車輛數(shù)分別為M1，M2的最優(yōu)解目標值，轉Step2；否則令基因位n的編碼值為0，求解模型M1，M2，更新該個體的流失乘客數(shù)和所需車輛數(shù)，以其替換當前種群中隨機選擇的某個體。

Step5k=k+1。

3.4 算法流程

高鐵站接運公交線路發(fā)車時刻表和用車數(shù)計算步驟如下。

Step1初始化。令s=0，確定種群規(guī)模Z、交叉概率pc、變異概率pm和最大迭代次數(shù)S，隨機生成父代種群P0，計算P0所有個體的最少流失乘客數(shù)與所需的最小公交車輛數(shù)。

Step2對Ps執(zhí)行快速非支配排序操作，得到所有個體的非支配排序值。

Step3對Ps執(zhí)行選擇、交叉、變異操作，生成規(guī)模為Z的子代種群Qs，計算Qs所有個體的最少流失乘客數(shù)與所需的最小公交車輛數(shù)。

Step4將Ps和Qs合并為規(guī)模為2Z的新種群Rs，對Rs執(zhí)行快速非支配排序操作，得到所有個體的非支配排序值。

Step5精英保留。令Ps+1=?，r=1。

如果Ps+1與Rs中非支配排序值為r的個體數(shù)之和不大于Z，則將Rs中非支配排序值為r的個體全部放入Ps+1；如果Ps+1與Rs中非支配排序值為r的個體數(shù)之和大于Z，則計算Rs中非支配排序值為r的個體的擁擠距離，將這些個體按照擁擠距離從大到小依次放入Ps+1，直至Ps+1中的個體數(shù)為Z為止。

Step6執(zhí)行“車次插入”算子。

Step7對Ps+1執(zhí)行快速非支配排序操作，得到所有個體的非支配排序值。

Step8更新Pareto解集。Ps+1中非支配排序值為1的個體即為最新的Pareto解集。

Step9終止檢驗。若s=S，則輸出Pareto解集，終止算法；否則令s=s+1，轉Step3。

4 算例分析

4.1 算例說明

某高鐵站共有4條接運公交線路接入，其首站均設在該高鐵站附近。各線路全程走行時間見表1。運營時間段為21:00—23:00，在該時間段內共有8列高鐵列車到達高鐵站，各次列車到站時間及各次列車上需要換乘各接運公交線路的乘客數(shù)見表2，各次列車均為虛擬車次。

表1 接運線路全程走行時間

表2 列車到站時間及換乘需求

從21:00開始，以5 min間隔設置可能的發(fā)車時刻，可能的發(fā)車時刻的最大、最小滿載率要求見下表。

表3 滿載率要求

公交車輛額定載客數(shù)C取100人/輛，乘客最長等待時間W取15 min，流失乘客數(shù)上限Nr為700人，最大可用公交車輛數(shù)Nv為30輛。

4.2 算例結果及分析

算法設計的參數(shù)設置如下：種群規(guī)模Z=20，最大迭代次數(shù)S=100，交叉概率pc=0.9，變異概率pm=0.3，“車次插入”概率p′=0.4。機器配置為2.27 GHz CPU和4 GB內存，采用C#語言編程，并調用ILOG CPLEX 12.4實現(xiàn)本文設計的算法。某次計算過程用時56.38 min，共獲得8個Pareto近似最優(yōu)解(不含式(11))，其中流失乘客數(shù)不超過流失乘客數(shù)上限的Pareto近似最優(yōu)解3個。各Pareto解的流失乘客數(shù)與使用公交車輛數(shù)見表4。各Pareto近似最優(yōu)解的最少流失乘客數(shù)為370人(占換乘需求總數(shù)的9.81%)，表5～表9分別給出了解2對應的各接運公交線路的時刻表與使用的最少公交車輛數(shù)的車輛調度方案、使得各接運公交線路流失乘客數(shù)最少的換乘各車次的乘客數(shù)(表5中每一發(fā)車時刻下的數(shù)字為執(zhí)行該車次的車輛編號)。

表4 各Pareto解的目標值

由表4可知，本文設計的算法運行一次可得到多個Pareto近似最優(yōu)解。決策者可根據(jù)偏好選擇一個Pareto近似最優(yōu)解作為最終的高鐵站接運公交時刻表，當其偏重企業(yè)成本時，可選擇解3；當其偏重社會成本時，可選擇解1；當其同時看重兩個目標時，可選擇解2。

表5 各接運公交線路時刻表及車輛調度方案(解2)

表6 接運線路1換乘方案(解2)

表7 接運線路2換乘方案(解2)

表8 接運線路3換乘方案(解2)

表9 接運線路4換乘方案(解2)

將各Pareto近似最優(yōu)解映射至坐標平面，見圖2。

合理選取優(yōu)化目標對于多目標優(yōu)化問題至關重要。對于2個優(yōu)化方向均為最小化的目標，如果它們之間存在正相關關系，則這2個優(yōu)化目標是不沖突的，即只有其中1個優(yōu)化目標有效。由圖2可知，各Pareto近似最優(yōu)解中，解的流失乘客數(shù)越少，則使用公交車輛數(shù)越多，即流失乘客數(shù)與使用公交車輛數(shù)是2個相互沖突的目標。因此本文選取流失乘客數(shù)與使用公交車輛數(shù)作為優(yōu)化目標較為合理。

4.3 最大可用公交車輛數(shù)靈敏度分析

將最大可用公交車輛數(shù)在20～30輛范圍內調整，最少流失乘客數(shù)見圖3。

由圖3可知，當最大可用公交車輛數(shù)為20輛時，最少流失乘客數(shù)多于流失乘客數(shù)上限；在20～26輛之間時，隨著最大可用公交車輛數(shù)的增加，最少流失乘客數(shù)逐漸減少。當最大可用公交車輛數(shù)大于26輛時，隨著最大可用公交車輛數(shù)的增加，最少流失乘客數(shù)不再發(fā)生變化。

運送乘客總數(shù)與發(fā)車次數(shù)之比即為每車次運送的平均乘客數(shù)，根據(jù)每車次運送的平均乘客數(shù)和公交車輛額定載客數(shù)可以計算每車次的平均滿載率，該指標可以反映乘客的乘車舒適度。隨著最大可用公交車輛數(shù)的增加，車次平均滿載率逐漸降低，當最大可用公交車輛數(shù)超過26輛時，由于最優(yōu)解均相同，運送乘客總數(shù)與發(fā)車次數(shù)均不再變化，因此車次平均滿載率不再變化。因此當最大可用公交車輛數(shù)為26輛時，繼續(xù)增加最大可用公交車輛數(shù)在增加運營成本的同時已無法降低最少流失乘客數(shù)和車次平均滿載率，即無法提高服務水平和乘客舒適度。決策者可在權衡企業(yè)與乘客成本的前提下對最大可用公交車輛數(shù)進行決策。

4.4 接運公交時刻表與高鐵到達客流一致性分析

以10 min為單位時段統(tǒng)計21:00—23:00內各時段的換乘需求和發(fā)車次數(shù)，見圖4。

由圖4可知，各接運公交線路各時段的發(fā)車次數(shù)與換乘需求一致性較高。各接運公交線路各時段的發(fā)車次數(shù)的變化趨勢較換乘需求的變化趨勢具有一定的滯后性，這是因為乘客可以等待一定時間(最長15 min)，本時段到達的乘客可能需等待至下一時段被運送。對于高鐵站接運公交線路，各時段發(fā)車次數(shù)無周期規(guī)律，不同時段的發(fā)車次數(shù)差異較大，這符合高鐵站客流到達規(guī)律，以及降低車輛運用數(shù)量的目的，但需要鐵路運輸部門與城市公交運營管理部門在客流數(shù)據(jù)方面有更好的交流共享機制。

5 結論

本文針對客流到達高峰期高鐵站接運公交時刻表與車輛調度綜合優(yōu)化問題，考慮因等待時間過長導致的乘客流失，以流失乘客數(shù)最少和使用公交車輛數(shù)最少為優(yōu)化目標，以車輛滿載率、乘客等待時間、最大可用公交車輛數(shù)、公交車輛執(zhí)行車次的順序等為約束條件，構建了高鐵站接運公交時刻表與車輛調度綜合優(yōu)化模型，并用帶精英策略的非支配排序遺傳算法NSGA-Ⅱ求解獲得了近似Pareto最優(yōu)解集。算例的計算結果表明，通過該模型及算法可以在有限的時間內獲得多個較優(yōu)的接運公交時刻表與車輛調度方案，供決策者選擇，驗證了模型及算法的有效性。實際工作中，接運公交除承擔了高鐵客流的集散任務外，還需滿足線路沿線其他車站的出行需求，因此考慮以高鐵站為起、終點的雙方向客流以及線路其他車站出行需求優(yōu)化時刻表和車輛調度方案將是今后研究的一個重點。另外，車輛在行駛途中可能發(fā)生延誤，如何在考慮車輛延誤的情況下保證車輛接續(xù)也將是未來研究的一個方向。