基于集對分析的隨機需求接駁公交調度模型*

孫 博 楊春風 魏 明 陳 浩

(1.河北工業大學土木與交通學院 天津 300401;2.南通大學交通學院 江蘇 南通 226019)

0 引 言

若要發揮軌道交通在城市客運交通系統的主干道作用，必須將客運交通的主體客流吸引到軌道交通上來，接駁公交是滿足市民出行“最后一公里”需求的一種重要補充公共交通方式。目前，其運營管理模式多數與地面常規公交相似，以客流需求時空分布為基礎，按固定線路、固定時間運營將乘客疏散至軌道站點，存在問題包括沒法提供“門到門”服務、實現居民的零等待、按需求發車等。借助互聯網技術，需求響應型接駁公交(demand-responsive feeder transit services，DRFTS)是一種以滿足乘客需求為導向的非固定線路靈活公交，可以彌補傳統接駁公交的缺陷，吸引了國內外學者的廣泛關注[1-5]。

目前，需求響應型接駁公交研究剛剛起步[6-7]，與具有傳統的固定線路、固定運營時間的傳統接駁公交差別較大，屬于車輛路徑問題研究范疇，均需考慮車輛的額定載客量、乘客的出行時間窗等約束，安排多輛車遍歷所有客戶，主要差異在于車輛路徑問題無須太關注乘客對乘坐軌道站點時間的要求影響、車輛路徑及其行車計劃生成過程，可以借鑒其研究思路和方法，主要成果歸納如下：Pan等[8]提出一種設計需求響應型交通覆蓋區域形狀的混合整數規劃模型；Li等[9]提出一個解析模型揭示最佳服務區域數量、客戶的服務水平和運營成本之間關系，在此基礎上,進一步提出解析和仿真模型分析居民如何選擇固定線路和需求相應交通出行服務；Chandra等[11]提出一種解析模型識別和定位需求響應型交通網絡的關鍵節點；Cremers等[12]提出了考慮提前預約的需求響應式公交的兩階段調度模型;Braekers[13]研究了多車場需求響應式公交調度模型;Schilde等[14]研究了考慮不同時間行駛速度變化的需求響應式公交調度模型和算法;Kirchler等[15]利用禁忌搜索算法求解帶時間窗的多目標靜態DAR問題;楊海軍[16]建立了基于快速需求響應的單一、多車型全程車調度方法;Qiu等[17]研究提出了可同時處理預約需求和實時需求的兩階段車輛調度模型;Sun等[18-19]研究提出了考慮乘客滿意度、軌道同步換乘的DRT問題。由上可知，現有研究主要不足包括：①忽略乘客對乘坐軌道站點時間的要求，即乘客除了要求接駁車輛在規定時間范圍內到達出發點，還要求車輛在其要求時間內到達軌道站點(最大容忍在車時間)，這影響車輛訪問乘客的順序；②忽略部分需求點的居民出行隨機需求對其調度方案的影響，雖然可借鑒不確定的物流配送研究，其研究思路分為等價確定性模型和計算機模擬，其處理過程極其復雜，不利于大規模推廣應用。

集對分析是我國學者趙克勤[15]提出的一種處理系統確定性與不確定性相互作用的數學理論，其核心是利用聯系數描述集合的同一性、對立性、差異性等。研究表明，正態分布變量ξ=(φ,δ)的隨機點x∈ξ落入x=[x-,x+]=[φ-3δ,φ+3δ]的區間的概率達99%以上?；诩瘜Ψ治?，將該不確定變量可以轉化為二元聯系數q=A+λB=μ-3σ+6σλ，其中：A=x-=μ-3σ為其確定部分，B=x+-x-=6σ為其不確定部分，聯系數λ∈[0,1]為其不確定程度。顯然地，集對分析可以完美刻畫隨機正態分布，具有線性簡單處理等優點。綜上所述，筆者研究隨機正態分布客流需求的需求響應型接駁公交調度問題，考慮乘客的最大容忍在車時間對車輛路徑構建的影響，針對帶隨機參數的機會數學規劃模型求解復雜缺點，基于集對分析理論，利用二元聯系數刻畫隨機客流的確定和不確定部分，將其轉化為帶聯系數的確定性混合整數線性規劃模型。以南京商貿中心地鐵站為例，給出了最佳接駁公交調度方案，分析了客流的不確定程度對調度結果的影響，并進行了參數的靈敏度分析，從而驗證模型的正確性。

1 需求響應型接駁公交調度的隨機線性規劃模型

1.1 隨機需求的需求響應型接駁公交調度模型

該問題為安排車輛從調度中心出發，將乘客從需求點運輸至軌道站點，追求總里程最少。乘客需求信息通過手機APP下達出行訂單獲取，包括出行起訖點、上車時間窗、最大容忍在車時間等。利用百度或谷歌等Open GIS平臺可以精確計算需求點、軌道站點和調度中心之間實際出行距離和時間?？紤]乘客可以新增、修改和取消訂單，每個需求點的乘客需求不確定，假設服從正態分布，通過歷史數據可以獲取其平均值和偏差。根據上述描述，建立該問題的隨機線性規劃模型，見式(1)～(12)。

(1)

(2)

(3)

(4)

(5)

?i,j∈I∪Ms?k∈K

(6)

?i,j∈I∪Ms?k∈K

(7a)

?i,j∈I∪Ms?k∈K

(7b)

(8)

(9)

(10)

(11)

(12)

在上述模型中，式(1)為問題的目標函數，即總運輸里程最少。式(2)～(12)為約束條件，其中：式(2)為每輛車至少有1個需求點；式(3)確保每個需求點只乘坐一輛車；式(4)為1個需求點只屬于1個線路，1個線路不能同時訪問2個需求點；式(5)為保證車輛從軌道站點出發并返回；式(6)為避免線路出現子回路；式(7)為車輛k到達相鄰需求點i和j之間時間關系；式(8)為車輛k到達需求點i的時間滿足其出行時間窗；式(9)為保證需求點i的在車時間不超過其容忍上限；式(10)為車輛k的隨機載客量不超過其額定載客量；式(11)為表示車輛k的行程里程不超過其上限；式(12)為車輛k的行程時間不低于其下限。

1.2 基于集對分析的線性等價確定性模型

minf

(13)

(14)

其他約束與上相同。

顯然地，根據約束(8)，將該問題分為帶時間窗的DRFTS(DRFTS with Time Windows, DRFTSTW)和不帶時間窗的DRFTS(DRFTS with No Time Windows, DRFTSNTW)；根據約束(9)，將該問題分為帶容忍在車時間的DRFTS(DRFTS with Tolerance in Car Time, DRFTSTCT)和不帶容忍在車時間的DRFTS(DRFTS with No Tolerance in Car Time, DRFTSNTCT)。

2 算例分析

以南京商貿中心地鐵站(M)周邊的接駁公交調度為例說明，總共15個需求點，它們的位置、出行時間和人數見表1，已知：公交車輛的額定載客量為30人、最大行程里程為9 km、最小行駛時間為3 min。

利用C#編程實現基于GIS和Cplex的求解框架調度平臺，當車輛數為3，4和5時，在分析客流的各個不確定程度基礎上，比較有無時間窗、最大容忍實際對車輛路徑的影響，計算結果見表2和表3，得到以下4個結論。

1) 隨著車輛數增加，雖然直達疏散乘客節省里程，但是車輛從需求點出發和返回增加更多無效空駛里程，總行駛里程變化趨勢與節省里程與增加無效空駛里程相關。除了表2的DRFTSNTW在λ=1時4輛車的總里程比3輛車略少，其它均是車輛數與里程成正比，增幅在0%～15%。

表1 客戶點的基本信息Tab.1 Basic information of customer points

2) 當客流的不確定程度λ由0變1時，各個需求點的上車人數增加，雖然受車輛的額定載客量限制，但是需求點的客流量不影響車輛路徑，因而總行駛里程沒有發生變化。若當前車輛路徑無法承載需求點的客流量，這些車輛可能偏好距離較遠但不超過其額定載客量的需求點，因而總行駛里程變大。例如，DRFTSNTCT和DRFTSTCT模型的5輛車對不同λ保持總行駛里程沒有變化，其他情況增幅在2%～14%。

3) 與DRFTSNTW相比，DRFTSTW的總行駛里程保持不變或逐漸變大，這是因為乘客的時間窗可能改變車輛路徑，強制車輛偏好較遠距離但是上車時間窗緊迫的需求點。雖然DRFTSNTW比DRFTSNTCT的總行駛里程多，但是滿足乘客的個性化出行時間窗，從而可以將乘客從私家車吸引至軌道交通出行。除了4輛車和λ=0.5時保持不變之外，DRFTSTW與DRFTSNTW偏差在0%～10%。

4) 同上，DRFTSTCT與DRFTSNTCT相比，其總行駛里程保持不變或變大，即：考慮乘客的最長容忍在車時間后，若車輛偏好最近的需求點可以不滿足在車時間約束。當車輛數增加一定程度時，由于每輛車僅負責少數乘客的疏散任務，客戶的時間窗約束條件較寬松，因而該約束對目標函數幾乎沒有影響。 一般情況下， DRFTSTW與DRFTSNTW偏差在0%～4%。

表2 不同車輛數的有無時間窗調度方案比較Tab.2 Comparison of scheduling schemes for different number of vehicles having and not having time window

表3 有無考慮乘客的最大在車時間對目標函數的影響Tab.3 The influence of maximum time in the car on the objective function considering passengers or not

3 結束語

針對已有需求響應型接駁公交調度未涉及個性化出行時間、隨機客流出行對其接駁線路設計的影響，建立了一類隨機混合整數線性規劃模型，揭示需求點的客流不確定程度、時間窗、容忍在車時間與調度方案之間耦合關系?；诩瘜Ψ治?，將該隨機模型轉化為一個非常簡單、易處理的線性確定性模型，容易分析客流的確定性部分和不確定部分對調度結果的影響。通過Cplex對一個算例求解表明：①隨著車輛數增加，若節省里程小于無效里程的增加量，總行駛里程保持增長趨勢，增幅在0%～15%。②隨著客流的不確定程度增加，若當前車輛路徑無法承載需求點的客流量，總行駛里程變大，增幅在2%～14%。③與DRFTSNTW相比，DRFTSTW的總行駛里程保持不變或逐漸變大，偏差在0%～10%；同理，DRFTSTCT與DRFTSNTCT相比，其總行駛里程也保持不變或變大，偏差在0%～4%。

本模型的研究不足在于：①忽略了不同需求點之間的不確定客流部分差異性；②沒有考慮接駁公交和軌道交通聯動對車輛路徑的影響；③Cplex無法求解大規模問題，亟待尋求求解該問題的啟發式算法，如：蟻群算法、遺傳算法等。