基于時(shí)間組的網(wǎng)約車合乘路徑優(yōu)化算法

馬傲雯 張淑欣 劉文婷 顧美飛 劉怡冰

（合肥工業(yè)大學(xué)管理學(xué)院，安徽合肥 230009）

近年來(lái)，城市擁堵、空氣污染和停車?yán)щy等問(wèn)題愈發(fā)凸顯[1]。車輛合乘模式對(duì)減輕道路交通擁堵壓力、緩解道路交通的擁堵程度、提高道路的運(yùn)能和資源利用率及節(jié)約能源等具有重要意義。

車輛合乘（car pooling，CP）又稱共乘或拼車，車輛路徑的選擇是關(guān)鍵問(wèn)題之一。Dantzig等[2]首次提出車輛路徑問(wèn)題（vehicle routing problem，VRP），對(duì)閉合式VRP進(jìn)行研究，并首次提出了相應(yīng)的數(shù)學(xué)規(guī)劃模型以及求解算法；Clarke等[3]提出了節(jié)省矩陣法；Christofides等[4]提出了K度中心樹和相關(guān)算法，解決固定車輛數(shù)的VRP；Sumichras等[5]研究了多中心車輛路徑問(wèn)題（MDVRP），解決從多個(gè)原料點(diǎn)向多個(gè)工廠配送原料的問(wèn)題；Su[6]提出了用動(dòng)態(tài)車輛控制和規(guī)劃系統(tǒng)，解決多中心車輛路徑問(wèn)題。

近年來(lái)，部分學(xué)者對(duì)車輛路徑問(wèn)題從多角度進(jìn)行了擴(kuò)展，出現(xiàn)了帶時(shí)間窗的車輛路徑問(wèn)題（VRPTW）。例如谷浩[7]提出了一種新的帶時(shí)間窗車輛路徑問(wèn)題的雙目標(biāo)規(guī)劃模型以及一種雙標(biāo)準(zhǔn)近似算法求解問(wèn)題，并證明了算法的近似比為[O（log1/ε），1+ε]。

段征宇等[8]考慮了路網(wǎng)交通狀態(tài)的時(shí)變性和隨機(jī)性，提出了一種帶硬時(shí)間窗的隨機(jī)時(shí)變車輛路徑問(wèn)題的多目標(biāo)魯棒優(yōu)化模型，并設(shè)計(jì)了一種非支配排序蟻群算法進(jìn)行求解，驗(yàn)證了其有效性。張凱慶等[9]考慮軟時(shí)間窗約束和車輛速度變化情況，并設(shè)計(jì)兩階段求解算法求解模型。

上述學(xué)者的研究既側(cè)重于時(shí)間窗本身的性質(zhì)（硬時(shí)間窗或軟時(shí)間窗），又考慮更接近實(shí)際的影響因素來(lái)優(yōu)化模型，但引入速度影響因素、考慮時(shí)間為目標(biāo)函數(shù)的研究較少。本文在考慮網(wǎng)約車資源利用率的基礎(chǔ)上，提出用時(shí)間代替距離進(jìn)行路徑匹配，引入“時(shí)間組”的概念表示車輛所在點(diǎn)、乘客上下車點(diǎn)的匹配依據(jù)。

1 問(wèn)題模型

式中：G——定義區(qū)域內(nèi)所有節(jié)點(diǎn)集，節(jié)點(diǎn)包括車輛出發(fā)點(diǎn)、乘客上下車點(diǎn)和司機(jī)接單點(diǎn)；B——網(wǎng)約車集合，有m輛網(wǎng)約車；N——乘客集合，有n個(gè)乘客；Qn——乘客上車點(diǎn)集合，Qn=[m+1，m+2，…，m+n]；Zn——乘客下車點(diǎn)集合，Zn=[m+n+1，m+n+2，…，m+2n]；R——網(wǎng)約車的車載容量；Pki——車輛k離開節(jié)點(diǎn)i時(shí)車內(nèi)的乘客數(shù)量；△pki——車輛k在節(jié)點(diǎn)i處上車乘客數(shù)；T——乘客出行需求；Tn——第n個(gè)乘客最大容忍時(shí)間，Tn≥T1n+T2n；T1n——司機(jī)接單到乘客上車的所用時(shí)間；T2n——乘客上車到乘客到達(dá)目的地所用時(shí)間；V——網(wǎng)約車的行駛速度；Dij——節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離，i，j∈G；Yki，j——司機(jī)接單到乘客上車的距離，i∈G，j∈Qn；Tij——從i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)時(shí)間，i∈Qn，j∈Zn；Xki，j——一、二元變量，i，j∈G，i≠j，k∈M。

式（1）、式（2）表示規(guī)劃模型的目標(biāo)函數(shù)；

式（3）表示一定時(shí)間t內(nèi)司機(jī)行駛載最多的乘客；

式（4）表示乘客等待時(shí)間（T1n+T2n）最小；

式（5）表示乘客數(shù)量不超過(guò)車載容量；

式（6）表示司機(jī)接單到乘客到達(dá)目的地的時(shí)間不超過(guò)乘客的最大容忍時(shí)間；

式（7）表示顧客點(diǎn)i只能由一輛車來(lái)服務(wù)。

2 問(wèn)題分析與算法設(shè)計(jì)

2.1 問(wèn)題分析

本文構(gòu)建的VRPTW模型屬于多目標(biāo)模型，變量類型有連續(xù)變量和0-1變量，約束條件為非線性約束，屬于NPhard類問(wèn)題。若將模型中的車載容量R視為變量，則模型變?yōu)榭紤]共享人數(shù)上限的VRP問(wèn)題[10]。若不考慮速度時(shí)變性，正常速度處理則模型變?yōu)閮H考慮時(shí)間窗的VRP問(wèn)題[11]。

2.2 算法設(shè)計(jì)

本文設(shè)計(jì)了一個(gè)基于路徑優(yōu)化模式建立的出租車合乘調(diào)度算法，通過(guò)綜合優(yōu)化、規(guī)模、效率三方視角，對(duì)前述問(wèn)題模型進(jìn)行對(duì)應(yīng)構(gòu)建。

（1）算法設(shè)計(jì)思路。

對(duì)于合乘問(wèn)題中的每一位乘客和每一輛車，都應(yīng)按照路徑最優(yōu)原則將新乘客插入原車輛路徑，得到新的車輛路徑，并計(jì)算所有車上乘客的拼車任務(wù)完成時(shí)間。

針對(duì)車上人數(shù)少于最大可拼車人數(shù)，需要考慮將新乘客添入車輛服務(wù)乘客，得到新的車輛路徑，重新計(jì)算車上乘客的拼車任務(wù)完成時(shí)間。

針對(duì)車上人數(shù)大于等于最大可拼車人數(shù)，需要考慮完成一個(gè)乘客的任務(wù)后，更新車輛路徑，并對(duì)車上乘客的任務(wù)完成時(shí)間進(jìn)行重新計(jì)算，計(jì)算時(shí)需要添加前一任務(wù)完成乘客的花費(fèi)時(shí)間。

拼車任務(wù)完成時(shí)間算法流程：

初始化車輛j的位置；

if（車上人數(shù)小于最大人數(shù)）；

找出車輛j送達(dá)全部乘客的最優(yōu)路徑最小（找到最短路徑）；

計(jì)算車上乘客已走過(guò)的時(shí)間與到達(dá)目的地的時(shí)間和；

計(jì)算乘客i到達(dá)目的地的完成時(shí)間；

if（車上人數(shù)大于等于最大人數(shù)）；

送達(dá)的第一位乘客的完成時(shí)間；

計(jì)算送達(dá)一位乘客的時(shí)間與地點(diǎn)；

從此地點(diǎn)重復(fù)“車上人數(shù)大于等于最大人數(shù)”，并將全部時(shí)間結(jié)果加上送達(dá)前一位乘客的時(shí)間；

end.

（2）拼車算法框架設(shè)計(jì)。

算法Ⅰ：拼車算法框架設(shè)計(jì)。

輸入：車輛實(shí)體信息、隨機(jī)路網(wǎng)模型及各項(xiàng)環(huán)境參數(shù)。

輸出：在指定環(huán)境參數(shù)下的模擬規(guī)劃記錄。

參數(shù)化指定：總運(yùn)行時(shí)長(zhǎng)T，離散時(shí)鐘Δt，車輛集合B。

3 試驗(yàn)數(shù)據(jù)與分析

3.1 模型設(shè)計(jì)

基于上述算法設(shè)計(jì)，為了驗(yàn)證算法有效性及測(cè)試模型的泛化能力，設(shè)計(jì)并測(cè)試了一組算例，針對(duì)隨即規(guī)模的地圖模型進(jìn)行了測(cè)試和規(guī)劃。

相應(yīng)程序已通過(guò)C++以及Java實(shí)現(xiàn)，并通過(guò)拒絕拼車模型、適意愿拼車模型和過(guò)意愿拼車模型進(jìn)行對(duì)比分析。

給定地圖模型（M×N），訂單標(biāo)記Order=(Start,End)=[(i,j),(k,l)]，i,k∈[0,1,…,M-1]，j,l∈[0,1,…,N-1]，實(shí)際訂單數(shù)R，時(shí)間單位T。

（1）訂單理論距離期望。

（2）車輛單位行駛距離期望。

Neighbor矩陣以及ps參數(shù)由不同地圖模型中距離生成算法決定，基于此計(jì)算D[s]。

（3）給定時(shí)間周期內(nèi)訂單匹配量期望以及期望丟單率。

（4）期望運(yùn)載能力。

為了提高模型的準(zhǔn)確率，便于在不同環(huán)境下測(cè)試算法的性能，設(shè)計(jì)了相應(yīng)的隨機(jī)地圖生成邏輯，使得本算法以及建立在本算法上的模型，可以針對(duì)不同規(guī)模的路網(wǎng)進(jìn)行測(cè)試和分析。本項(xiàng)目試驗(yàn)假定乘客35人（記為1，2，…，35），車輛5輛（記為a，b，c，d，e，且車容量為3人）。

算例合乘路徑結(jié)果如表1所示。

表1 算例合乘路徑

3.2 拒絕拼車模型與適意愿拼車模型

通過(guò)對(duì)拒絕拼車意愿的打車模型與當(dāng)前拼車模型進(jìn)行對(duì)比，以驗(yàn)證并說(shuō)明本模型基于拼車環(huán)境對(duì)整體客戶滿足率和運(yùn)行效率（系統(tǒng)效益）的提升。

為了更好地測(cè)試模型對(duì)抗極端環(huán)境的強(qiáng)度以及拼車模型對(duì)運(yùn)行效率的提高以及資源優(yōu)化，本文采取高壓訂單生產(chǎn)策略，即訂單的隨機(jī)產(chǎn)生期望大于20%，對(duì)應(yīng)各城市運(yùn)行高峰期，即拼單高需求環(huán)境。

該測(cè)試環(huán)境（25×25路徑模塊，20折平均驗(yàn)證）下拒絕拼車模型的期望結(jié)果以及適意愿拼車模型的測(cè)試結(jié)果：

拒絕拼車模型的期望結(jié)果：丟單率為20.3237%；運(yùn)載能力為0.996。

適意愿拼車模型的測(cè)試結(jié)果：丟單率為7.6378%；運(yùn)載能力為3.1。

適意愿模型的測(cè)試結(jié)果如圖1所示。

圖1 適意愿模型的測(cè)試結(jié)果

（1）丟單率分析。

丟單率充分反映了不同環(huán)境下不同策略對(duì)當(dāng)前訂單生成的滿足能力。在當(dāng)前環(huán)境下拒絕拼車模型給出了超過(guò)20%的丟單率，即完全拒絕拼車會(huì)導(dǎo)致大量訂單難以在乘客容忍度范圍內(nèi)得到滿足。

在適意愿模型的拼車環(huán)境下，丟單率下降至7.63，對(duì)比結(jié)果充分反映了在乘客接受拼車策略的前提下，通過(guò)恰當(dāng)?shù)钠窜囌{(diào)度算法，成功實(shí)現(xiàn)了訂單滿足率的提高和乘客期望的滿足率，達(dá)到了本模型的期望結(jié)果。

（2）運(yùn)載能力分析。

在拒絕拼車的環(huán)境下，車輛運(yùn)載能力僅能保持在1左右，極大限制了車輛系統(tǒng)空閑利用率的提高及潛在利益的挖掘。

在適意愿模型的測(cè)試環(huán)境下，車輛的運(yùn)載能力得到3倍以上提升，結(jié)果顯著反映了在本文給出的拼車算法下，無(wú)論是考慮每輛車的運(yùn)行效率和效益，還是車輛系統(tǒng)整體的通勤能力，都得到了顯著提高。效率的提高并不意味著乘客滿足率的下降，是成功實(shí)現(xiàn)供給雙方效益的同步最大化，實(shí)現(xiàn)了本模型期望的目標(biāo)。

3.3 適意愿拼車與過(guò)意愿拼車模型

上述分析已經(jīng)顯著檢驗(yàn)并論證了本模型在提高乘客滿足率的同時(shí)，提高了車輛的利用率和運(yùn)行效率的實(shí)際效益。通過(guò)進(jìn)一步對(duì)比適意愿拼車模型與過(guò)意愿拼車模型，挖掘本模型對(duì)于推進(jìn)現(xiàn)實(shí)拼車模型實(shí)踐優(yōu)化的指導(dǎo)價(jià)值。

考慮將拼車意愿提高到2倍的環(huán)境，進(jìn)行獨(dú)立重復(fù)試驗(yàn)，結(jié)果如圖2所示。

圖2 過(guò)意愿模型的測(cè)試結(jié)果

過(guò)意愿拼車模型的測(cè)試結(jié)果：丟單率：14.8622%；運(yùn)載能力：2.89。在當(dāng)前環(huán)境下丟單率出現(xiàn)了異常提高，同時(shí)運(yùn)載能力出現(xiàn)了6.78%的下降。

問(wèn)題出現(xiàn)的關(guān)鍵是過(guò)意愿模型存在調(diào)度誤判，即使利用當(dāng)前高效的分配模型和調(diào)度算法，仍無(wú)法在資源緊缺的前提下憑空提高整體模型的表現(xiàn)能力。

從另一個(gè)角度分析，體現(xiàn)了本模型在高壓交通情況下仍能表現(xiàn)出極高的承受力和分配能力，充分說(shuō)明了模型對(duì)有限資源的規(guī)劃能力。資源緊缺的情況下，本算法依舊可以實(shí)現(xiàn)有限資源的最大利用。

4 結(jié)語(yǔ)

本文設(shè)計(jì)了基于拼車邏輯和算法設(shè)計(jì)的動(dòng)態(tài)拼車規(guī)劃模型，對(duì)相應(yīng)框架設(shè)計(jì)和具體細(xì)節(jié)均進(jìn)行了詳盡闡述，并基于這一設(shè)計(jì)完成了具體的現(xiàn)實(shí)程序?qū)崿F(xiàn)。在此基礎(chǔ)上，通過(guò)將三種不同情況下的規(guī)劃結(jié)果進(jìn)行測(cè)試和對(duì)比，本模型的性能和適用性得到了充分驗(yàn)證和討論，并在路徑規(guī)劃、交通資源分配、城市交通壓力分析預(yù)測(cè)等方面均展示出了較好的指導(dǎo)價(jià)值和意義，具有廣闊的發(fā)展和應(yīng)用空間。