鄭 漢，張星臣，王志美

(北京交通大學(xué) 交通運輸學(xué)院，北京100044)

0 引言

需求響應(yīng)公交服務(wù)(Demand-Responsive Service)，作為一類新興的城市公共交通組織方式，已成為傳統(tǒng)公交方式的有效補充，是當(dāng)前城市交通實現(xiàn)供需適應(yīng)的重要手段.

在現(xiàn)有研究中，根據(jù)不同服務(wù)特性，需求響應(yīng)公交服務(wù)可以分為定制公交、校園巴士、專車服務(wù)等不同類型.定制公交[1-2]側(cè)重提供一定頻率的、相對固定線路的出行服務(wù)；校園巴士[3]側(cè)重于解決“多對一”的定制出行問題；而專車服務(wù)[4]主要提供“一對一”的特定出行服務(wù).定制公交一般服務(wù)于穩(wěn)定、足量的客流，而校園巴士、專車服務(wù)等主要面對“門到門”服務(wù)的需求.

然而，城市出行需求具有復(fù)雜多變特性，上述“門到門”服務(wù)產(chǎn)品和定制公交產(chǎn)品很難滿足所有需求，如瞬時、大規(guī)模需求(特大城市內(nèi)生活區(qū)與商業(yè)區(qū)通勤、球賽散場后的大規(guī)模返程)便是難以滿足的需求之一.這類出行需求會在局部的時空區(qū)域內(nèi)產(chǎn)生大量的上下車行為，“門到門”服務(wù)模式此時會表現(xiàn)得效率低下[3].此外，在技術(shù)層面，“門到門”服務(wù)定制為典型NP-Hard問題，其求解規(guī)模和效率一直受限[5-6]，難以在短時間內(nèi)生成瞬時、大規(guī)模需求的疏散方案.以上說明經(jīng)典“門到門服務(wù)”不能完全滿足上述出行需求.為了準時到達預(yù)定地點，人們主觀上能夠接受以犧牲一定程度便利性，換取出行效率的提升——放棄門到門服務(wù)，接受指定時空范圍內(nèi)集體出行服務(wù)(如拼車服務(wù))已成為可被接受的方式之一.本文將一定客流的乘降地點及時間窗定義為“服務(wù)單元”.引入服務(wù)單元后，人們需要去特定地點進行乘降，而車輛僅需在服務(wù)單元間進行運送.服務(wù)可以分解為服務(wù)單元的設(shè)置和帶時間窗的車輛取送，兩者的設(shè)計需要兼顧乘客方便性，以及車隊運輸?shù)倪\營成本.由于需求分布的不均衡性，每個服務(wù)單元吸引的乘客數(shù)具有差異性.考慮多車型(容量、速度、費用等有所差異)的組織形式，既能滿足旅客需求，又能夠合理控制成本.綜上，本文研究如何基于服務(wù)單元，使用有限數(shù)量的混合類型車輛完成乘客出行服務(wù)的問題，即混合車型需求響應(yīng)公交服務(wù)問題.

本文主要由4節(jié)構(gòu)成.第1節(jié)，對服務(wù)單元進行數(shù)學(xué)化描述，并研究出行需求服務(wù)單元自動生成技術(shù)；第2節(jié)，借助Dantzig-Wolfe(D-W)分解，以運輸成本最小化為目標，建立有限數(shù)量混合類型車輛分配與路徑規(guī)劃的等價分解模型，與一般模型相比，我們增加了最大運行距離、最大運行時間約束；在第3節(jié)，以MapReduce為框架，設(shè)計基于列生成的分布式算法；第4節(jié)，選取了以北京為背景的算例，對比本文提出的分布式列生成算法、集中式列生成算法及商業(yè)軟件GAMS的結(jié)果，對方法的可行性、有效性進行了驗證.

1 基于需求分析的服務(wù)單元生成方法

網(wǎng)絡(luò)預(yù)約、大數(shù)據(jù)處理等技術(shù)在公交領(lǐng)域已有應(yīng)用[7-8]，獲取乘客預(yù)定的乘降地點和時間在技術(shù)上已較成熟.服務(wù)單元包含分配的乘客、乘降地點和乘降時間窗.如何根據(jù)乘客出行需求信息，在候選的地點、時間窗內(nèi)挑選乘降地點及時間窗，分配乘客構(gòu)成服務(wù)單元，是本節(jié)解決的主要問題.

為保障乘客的方便性，模型引入行人最大走形距離dmax，核函數(shù)寬度σ等參數(shù)；同時為提升計劃可行性，引入車輛運行冗余?.模型涉及符號如表1所示.

表1 服務(wù)單元生成模型符號約定Table 1 Notations of service units generation model

服務(wù)單元生成過程的目標是最大化各需求到選定服務(wù)單元間時空相似度總和.表示為

相似性基于高斯核設(shè)計，表示為

該問題具有以下約束：

(1)服務(wù)單元約束.1個簇僅擁有1個服務(wù)單元，即∑w∈Sψjw=1，?j∈C.

(2)預(yù)約滿足約束.1個預(yù)約只能歸屬于1個簇，即∑i∈Rωij=1，?j∈C.

(3)候選服務(wù)單元內(nèi)部可行約束.在正常速度下，服務(wù)單元的上車點和下車點之間可達，即‖fsti‖Am≥?，?i∈Cad.其中‖?‖Am，?i∈Cad表示范數(shù)，有

(4)最大距離約束.設(shè)函數(shù)ξ(d is)表示距離和相似度間的映射，有

使用基于k-means的啟發(fā)式算法對模型進行求解，輸入為：k(服務(wù)單元數(shù))，R(需求集合)，Cad(候選服務(wù)單元集合).輸出為：k個選定服務(wù)單元.具體方法如下：

(1)從Cad中任選k個初始服務(wù)單元.

(2)計算所有需求點與候選服務(wù)單元的相似度，將需求點分配至各自相似度最大的當(dāng)前服務(wù)單元.在核函數(shù)的作用下，若某需求與所有服務(wù)單元的相似度均接近0，則該點暫時孤立，并給予目標函數(shù)一定懲罰，等待下一次分配.

(3)計算簇內(nèi)所有需求點的中心，將離中心最近的候選服務(wù)單元選為該簇的選定服務(wù)單元.

(4)若選定服務(wù)單元不再變換，則輸出結(jié)果；否則，返回步驟(2).

2 車輛分配與路徑規(guī)劃模型

本節(jié)內(nèi)容將解決服務(wù)單元和車輛的對應(yīng)關(guān)系問題.該問題被視為帶時間窗約束的車輛取送問題，一般方法(文獻[5])僅能實現(xiàn)小型案例[6].為解決上述問題，使用Dantzig-Wolfe(D-W)分解，將問題分為主問題與子問題模型.主問題解決服務(wù)單元集合的覆蓋問題，子問題解決不同類型車輛的路徑規(guī)劃問題，兩者可通過邊際成本和遞減成本關(guān)聯(lián)，使用列生成算法進行求解.混合車型在主問題和子問題中均有體現(xiàn)：主問題中發(fā)車的固定費用，子問題中車輛的最大行駛距離、最大行駛時間及載運能力，均由車輛類型決定.

2.1 載運車輛分配主問題模型LMP

主問題模型LMP的符號約定如表2所示.

表2 主問題符號約定Table 2 Notations ofLMP

基于此符號約定，構(gòu)建LMP模型為

目標函數(shù)：

約束條件：

式(2)保障服務(wù)單元被分配至1個路徑之中；式(3)保障k車的路徑r至多被選擇1次；式(4)表示決策變量θkr松弛為0-1變量.為提升求解速度，對決策變量θkr進行線性松弛，將式(4)改為θkr∈[0 , 1]，r∈Ωk,k∈M；同時將式(2)改為i∈N.新約束式(2)表示任意服務(wù)單元需要被服務(wù)但服務(wù)次數(shù)不受限制.顯然，當(dāng)約束中的“＞”號成立時，問題未達最優(yōu)解[6].

2.2 路徑規(guī)劃與評價子問題模型Sk

子問題模型的符號定義如表3所示.

表3 子問題符號定義Table 3 Notations ofSk

目標函數(shù)：

約束條件：

式(6)和式(7)限定載運車輛必須經(jīng)過服務(wù)單元的上、下車部分.式(8)和式(9)限定載運車輛起終點在車隊駐扎點.式(10)～式(12)和式(18)組成優(yōu)先級約束.式(13)～式(15)和式(19)組成能力約束.式(16)和式(17)限定載運車輛運行過程中的最大距離和最大時間.

3 分布式列生成求解算法

3.1 MapReduce框架下的列生成算法

為了實現(xiàn)多節(jié)點分布式計算，一方面，使用Hadoop分布式文件系統(tǒng)(簡稱HDFS)解決節(jié)點數(shù)據(jù)高效率讀、寫問題；另一方面，通過MapReduce框架解決分布式算法的協(xié)調(diào)組織與同步推進問題.圖1通過一個4節(jié)點系統(tǒng)描述了MapReduce框架下的列生成算法的基本情況.節(jié)點1～3側(cè)重子問題的求解，節(jié)點0側(cè)重主問題的求解.算法描述如下.

Step 1初始化.將服務(wù)單元信息、車隊信息，以及初始化路徑集(路徑和費用)輸入HDFS之中.其中，初始化路徑集的構(gòu)建需要引入虛擬變量及虛擬路徑.虛擬路徑定義為目標函數(shù)為一極大正值，且θkr=0的路徑[5-6]；虛擬變量表示虛擬路徑是否被使用，初始化時虛擬變量均為1.

Step 2規(guī)約.MapReduce從HDFS中獲取所有路徑集Ωk，并運行Reduce函數(shù)，通過線性規(guī)劃方法求解LMP，獲得當(dāng)前最優(yōu)解，計算LMP的邊際成本

Step 3判斷.對當(dāng)前最優(yōu)解進行終止判斷，包括：

①若虛擬變量取0，且子問題的目標函數(shù)值大于等于0時，則停止計算并輸出；

②若虛擬變量不取0，且子問題的目標函數(shù)值大于等于0時，則停止計算并告知無解；

③若子問題的目標函數(shù)值小于0，則繼續(xù)計算；

④若子問題尚未計算，則繼續(xù)計算.

Step 4存儲.將LMP獲得的解、邊際成本( )u→,v→及新的路徑集Ωk存入HDFS.

Step 5讀取.MapReduce從HDFS中獲取服務(wù)單元信息，車隊信息，以及當(dāng)前主問題的邊際成本

Step 6映射.根據(jù)車輛類型對參數(shù)進行映射，構(gòu)建不同分片發(fā)送至節(jié)點1～3，存儲于Datanode并交由Tasktracker調(diào)度.之后在Map函數(shù)中求解對應(yīng)的子問題Sk.Sk可以被視為從De+到De-的具有優(yōu)先級約束、能力約束和資源約束的最短路問題，可使用文獻[9]中算法求解.將各子問題求解由Jobtracker控制.

Step 7結(jié)合.選擇子問題解中的最優(yōu)解，按照類型添加進路徑集Ωk，并存入HDFS，之后返回Step2.

3.2 MapReduce框架下的解可行性保障方法

主問題的松弛可以提升求解效率，同時也可能造成解中出現(xiàn)路徑由非整數(shù)輛車執(zhí)行的情況.為保障解的可行性，制定如下策略.

Step 8選邊.選取滿足的邊，構(gòu)建禁忌路徑集TR1?Ωk及TR2?Ωk和禁忌邊集TA1?A和TA2?A.其中TR1是包含邊a的所有路徑集合，而TR2是TR1的補集；TA1包含邊a，而TA2包含與邊a擁有相同指向點的邊.

Step 9分支.根據(jù)下述方法進行分支：

①分支1，根據(jù)TR1，排除Ωk中的路徑.并根據(jù)TA1，刪除A中的相關(guān)信息.

②分支2，根據(jù)TR2，排除Ωk中的路徑.并根據(jù)TA2，刪除A中的相關(guān)信息.

Step 10重初始化.將分支后數(shù)據(jù)寫入HDFS，并返回Step2進行運算.

完成計算后，比對各分支的結(jié)果，選擇可行且最優(yōu)的解作最終解.

圖1 MapReduce框架Fig.1 Framework based on MapReduce

4 實例運用與結(jié)果分析

本文通過模擬預(yù)約系統(tǒng)共獲得357個預(yù)約需求，時區(qū)為6:00-12:00，分布于北京市昌平區(qū)和海淀區(qū).

以100 m為間隔，調(diào)整服務(wù)單元生成模型中的參數(shù)dmax進行數(shù)值實驗，發(fā)現(xiàn)該案例中，當(dāng)dmax在100～800 m范圍時，總是存在孤立點.為此，在接下來的試驗中，我們采取dmax=900 m進行研究(盡可能減少步行距離).此時可獲得25個服務(wù)單元.初步分析可知，在6:00-9:00，服務(wù)單元的上車點集中在西二旗、回龍觀等住宅區(qū)，以及西直門等樞紐，下車地點集中在科技、教育與商業(yè)中心，客流由城外向城內(nèi)流動(圖2(a))；在9:00-12:00的服務(wù)單元，其上車點與下車點分布在海淀區(qū)的學(xué)校、商場、辦公區(qū)等區(qū)域(圖2(b)).大體上符合北京市的基本情況.服務(wù)單元所組成的網(wǎng)絡(luò)模型如圖3所示，其中車隊駐扎地以“Depot”表示，標號0；所有上車地點以“+”表示，編號為1～25；而下車地點以“-”表示，編號26～50.

圖2 服務(wù)單元分布情況Fig.2 Distributions of service units

圖3 服務(wù)單元網(wǎng)絡(luò)模型圖Fig.3 Network model for service units

設(shè)定車隊1規(guī)模：22座小車(車型1)3輛和53座大車(車型2)9輛，共計12輛.車輛固定費用設(shè)置為45(車型1)和90(車型2)，而活動成本由行駛距離表示.車輛行駛細節(jié)由數(shù)字地圖提供.

本文設(shè)計了5組試驗，如表4所示，使用的計算資源為Intel(R)Core(TM)i7-6500U CPU@2.50GHz 2.59GHz，內(nèi)存 4.00GB，節(jié)點數(shù) 3，寬帶100 MB/s.其中算例1以改進的經(jīng)典模型[5]建模(添加約束式(16)和式(17))，使用商業(yè)軟件GAMS求解，作為解質(zhì)量的標準；算例2使用非分布式的列生成算法[6]對第2節(jié)模型進行求解，作為計算速度的標準；算例3采用本文第2節(jié)的模型和第3節(jié)的算法.前3組均以車隊1為研究基礎(chǔ).

對比分析，算例1～3解的目標值相同，證明第2節(jié)模型與原模型等價，方法可行.從計算時間來看，解1消耗了71 835 ms，解2消耗了36 786 ms，而解3消耗了16 184 ms，由此證明分布式列生成算法在計算時間上有足夠的優(yōu)勢.

此外，我們設(shè)計了算例4和算例5，分別表示單純使用車型1和車型2時的計劃情況.算例3總共使用了10輛車，包括2輛車型1和8輛車型2，滿載率76%.算例4由于能力不足導(dǎo)致無解.算例5目標函數(shù)為1 545.275，使用10輛車型2，滿載率67%.由此可見，同樣的需求下，混合車型的供需匹配更為合理.算例3的解如表5所示.

表4 不同數(shù)值實驗解質(zhì)量對比Table 4 Quality comparison among solutions

表5 解3的路徑詳情Table 5 Details of routes in solution 3

5 結(jié)論

本文通過設(shè)計算法分析需求，確定服務(wù)單元.將載運車輛的分配與路徑規(guī)劃問題視為帶時間窗的取送問題，通過D-W分解建立等價分解模型，提出分布式列生成算法和解的可行性保障方法.實例證明，提出的分解模型與原問題等價，設(shè)計的算法相較于集中式算法在效率上有一定的優(yōu)勢.混合車型需求響應(yīng)公交服務(wù)具有一定的實際應(yīng)用價值.

參考文獻：

[1]LIU T,CEDER A,BOLOGNA R,et al.Commuting by customized bus:A comparative analysis with private car and conventional public transport in two cities[J].Journal of Public Transportation,2016,19(2):55-74.

[2]PERUGIA A,MOCCIA L,CORDEAU J F,et al.Designing a home-to-work bus service in a metropolitan area[J].Transportation Research Part B Methodological,2011,45(10):1710-1726.

[3]PARK J,KIM B I.The school bus routing problem:A review[J].European Journal of Operational Research,2010,202(2):311-319.

[4]RITZINGER U,PUCHINGER J,HARTL R F.Dynamic programming based metaheuristics for the dial-a-ride problem[J].Annals of Operations Research,2016,236(2):341-358.

[5]SOL M.Column generation techniques for pickup and delivery problems[D]. Technische Universiteit Eindhoven,1994.

[6]FEILLET D.A tutorial on column generation and branch-and-price for vehicle routing problems[J].4OR,2010,8(4):407-424.

[7]REN Y,CHEN G,HAN Y,et al.Extracting potential bus lines of customized city bus service based on public transport big data[J].Iop Conference Series:Earth&Environmental Science,2016,46(1):012017.

[8]LEI Y W,LIN P Q,YAO K B.The network scheduling model and its solution algorithm of internet customized shuttle bus[J].JournalofTransportation Systems Engineering and Information Technology,2017,17(1):157-163.

[9]DUMAS Y,DESROSIERS J,SOUMIS F.The pickup and delivery problem with time windows[J].European Journal of Operational Research,1991,54(1):7-22.