混合車型需求響應(yīng)公交服務(wù)定制問(wèn)題研究

鄭 漢，張星臣，王志美

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

0 引言

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

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

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

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

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

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

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

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

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

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

該問(wèn)題具有以下約束：

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

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

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

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

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

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

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

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

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

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

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

2.1 載運(yùn)車輛分配主問(wèn)題模型LMP

主問(wèn)題模型LMP的符號(hào)約定如表2所示.

表2 主問(wèn)題符號(hào)約定Table 2 Notations ofLMP

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

目標(biāo)函數(shù)：

約束條件：

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

2.2 路徑規(guī)劃與評(píng)價(jià)子問(wèn)題模型Sk

子問(wèn)題模型的符號(hào)定義如表3所示.

表3 子問(wèn)題符號(hào)定義Table 3 Notations ofSk

目標(biāo)函數(shù)：

約束條件：

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

3 分布式列生成求解算法

3.1 MapReduce框架下的列生成算法

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

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

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

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

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

②若虛擬變量不取0，且子問(wèn)題的目標(biāo)函數(shù)值大于等于0時(shí)，則停止計(jì)算并告知無(wú)解；

③若子問(wèn)題的目標(biāo)函數(shù)值小于0，則繼續(xù)計(jì)算；

④若子問(wèn)題尚未計(jì)算，則繼續(xù)計(jì)算.

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)例運(yùn)用與結(jié)果分析

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

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

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

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

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

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

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

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

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

表5 解3的路徑詳情T(mén)able 5 Details of routes in solution 3

5 結(jié)論

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

參考文獻(xiàn)：

[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.