共享出行問題及求解算法研究綜述

胡忠愷，袁鵬程

（上海理工大學 管理學院，上海200082）

0 引 言

近年來，隨著移動通訊技術(shù)的迅速發(fā)展，有越來越多的出行方式供出行者選擇來完成出行目的。選擇這些不同的出行方式時，出行者會根據(jù)自身的需求考慮一系列的標準，如出行成本、出行時間、便捷性、安全性等。對于公交車、地鐵這些傳統(tǒng)的公共交通來說，它們?yōu)槌鲂姓咛峁┑氖枪潭ㄐ旭偮肪€和固定時間表的出行模式，不能提供像出租車一樣的“門對門”服務，將此定義為固定的共享出行系統(tǒng)。這種固定的共享出行系統(tǒng)向出行者收取較少的費用，但對出行者來說不夠便利。相比之下，出租車和私家車收取的費用較高，但是能提供更便利、更靈活的服務。本文研究的共享出行問題就是針對如出租車和私家車這樣非固定的共享出行系統(tǒng)。

共享出行指的是出行者無需擁有車輛所有權(quán)，以共享和合乘方式與其他人共享交通工具的一種新興交通方式，并與其他合乘者共同分擔汽油費、停車費等出行費用。共享出行給駕駛員、乘客、交通環(huán)境等多方面帶來了許多好處，例如減少出行時間、增加司機收入、緩解交通擁堵、節(jié)省能源消耗和減少空氣污染等。盡管共享出行能帶來諸多好處，但由于缺乏有效的路線和時間協(xié)調(diào)以及合理費用的制定，共享出行在發(fā)展初期屬于一種非正式且無組織的活動。隨著近些年移動互聯(lián)網(wǎng)、全球定位系統(tǒng)以及社交網(wǎng)絡的技術(shù)進步，使得司機與出行者的匹配更加高效便捷，這主要得益于共享出行系統(tǒng)平臺的開發(fā)，這些平臺成為駕駛員和乘客之間的橋梁。但共享平臺的出現(xiàn)也給司機和乘客帶來了各種各樣新的難題，如何給司機快速、合理的匹配出行乘客并規(guī)劃最優(yōu)的出行路線，如何綜合考慮司機和乘客的雙方利益，實現(xiàn)利益最大化，如何提高服務質(zhì)量等問題都受到各國學者的關(guān)注，并對各類共享合乘匹配和路徑優(yōu)化問題進行了一系列的相關(guān)研究，為共享合乘問題的進一步研究提供參考。國內(nèi)外學者都是將共享出行系統(tǒng)匹配路徑優(yōu)化的現(xiàn)實問題抽象為數(shù)學問題，并構(gòu)建不同目標和約束的優(yōu)化模型加以解決。本文將提出4種類型的共享出行問題，以了解其異同點以及共享出行系統(tǒng)的關(guān)鍵方面，給出LCPP的模型以了解模型的具體特征，并在此基礎上介紹模型的解決算法和未來的研究方向。

1 共享出行問題

本文主要對運輸人員的共享出行問題的多種變體進行介紹，此類共享出行系統(tǒng)旨在最大化車輛空位的利用率以減少私家車的數(shù)量，同時最大程度地減少繞道行駛帶來的不便，從而達到緩解交通擁堵和交通污染的目的。在近幾十年的發(fā)展中，眾多學者對共享出行問題進行了分類研究如圖1所示，例如：乘車共享問題（ridesharing）、撥號乘車問題（the dial a ride problem）、拼車問題（the carpooling problem）、共享出租車問題（the shared-taxi problem）等。

1.1 乘車共享問題（Ridesharing）

乘車共享（Ridesharing）指的是一種個人出行者與其他行程路線和時間表相似的出行者共享交通工具的出行方式，并分攤?cè)加唾M，過路費和停車費等出行費用［1］。對于乘車共享一般可以劃分為靜態(tài)共享和動態(tài)共享，靜態(tài)共享（static ridesharing）指的是共享乘車參與者在出行之前已經(jīng)將出行計劃安排好的共享模式，即參與共享出行乘客的起始點、目的地以及出發(fā)和到達的時間都是在出發(fā)之前預先告知駕駛員；動態(tài)共享（dynamic ridesharing）更加側(cè)重于司機和乘客的動態(tài)匹配，也就意味著提供共享出行服務的車輛和有共享出行需求的乘客可以隨時進入和離開系統(tǒng)，系統(tǒng)能在短時間內(nèi)將最合適的乘客和司機進行匹配。

圖1 共享出行問題的變體Fig.1 Variants of the ride-sharing problem

1.2 拼車問題（The Carpooling Problem）

拼車問題（The Carpooling Problem，CPP），從19世紀70年代中期開始，受石油危機影響，近20%的通勤出行者使用拼車上下班，其受歡迎程度開始激增［2］。Baldacci等（2004）研究拼車作為一種由大公司組織的運輸服務，以這家公司的員工為單位，將具有相同出發(fā)點的用戶分為一組，組員輪流做司機或者選擇固定的司機，目的是鼓勵員工在上下班時能接送同事，最大限度的減少往返公司辦公的私家車車輛［3］。這種拼車是屬于持續(xù)的、長期的拼車模式，被稱為Long-term Carpooling Problem（LCPP）。而Daily Carpooling Problem（DCPP），也被稱為臨時拼車，是在沒有事先預約的情況下參與拼車。和LCPP相比，DCPP主要的不同點在于參與拼車的乘客不是固定的，并且是在集合點以先到先得的方式形成的。

1.3 撥號叫車問題（The dial-a-ride problem）

撥號叫車問題（The dial-a-ride problem，DARP）是指為n位用戶設計行駛路線和時間窗，而這些用戶可以在指定起始點和目的地之間實現(xiàn)共享出行。其目的是在約束條件下規(guī)劃一組m條最低成本的車輛路線，以容納盡可能多的用戶［4］。傳統(tǒng)的DARP主要是給老年人或殘疾人提供門到門的交通服務，通常以最小化成本為目標［5-6］。DARP與動態(tài)共享問題（dynamic ridesharing）主要的區(qū)別在于，DARP中的駕駛員可以給更廣泛的乘客提供服務，因為在這種情況下，駕駛員是屬于向乘客提供服務的一方，因此對于行駛路線和時間的限制較為寬松。

1.4 共享出租車問題（The shared-taxi problem）

Hosni等提出的共享出租車問題（The sharedtaxi problem）是共享出行問題的另一個變體［7］。該問題是乘客在提出需求時說明上下車地點，還需要表明最早可接受的上車時間和最晚可接受的下車時間以及最長的乘車時間，每位乘客的乘車費用是根據(jù)各自上下車的距離而制定的。

共享出租車問題的目的是確定乘客和出租車的最佳匹配以及每輛出租車的最佳路線，該問題和DARP有相同的特性。但是，這兩者還是有所區(qū)別的，Jung等表明在一般情況下，共享出租車問題的目標主要是通過強大的動態(tài)需求系統(tǒng)使得司機和乘客的匹配時間最小化，而傳統(tǒng)的DARP目標則是試圖在確定保證乘客數(shù)量不變的情況下提供最少的服務車輛來最大限度的降低車輛運營成本［8］。

2 模型特征

在研究共享出行問題時，通常是在車輛路徑問題的基礎上使用不同的數(shù)學公式建立模型，這些公式由不同的目標函數(shù)和約束條件構(gòu)成，表明了每個問題的不同特征。LCPP的數(shù)學模型特征，一個調(diào)度路網(wǎng)G＝(V，A)，其中A為調(diào)度路網(wǎng)中所有節(jié)點的集合，V為調(diào)度路網(wǎng)中所有弧段的集合，即a r c（i，j）∈V［3］。

（1）集合

V＝{ 0，…，n}＝{ { 0}∪V＇}表示調(diào)度路網(wǎng)中所有節(jié)點的集合，其中節(jié)點0代表目的地，也就是公司所關(guān)聯(lián)的節(jié)點；

V＇＝{ 1，…，n}表示所有參與者的集合，其中V＇＝V s∪V c；

V s＝{ 1，…，n s}表示與服務車輛相關(guān)聯(lián)的節(jié)點集合；

V c＝{n s+1，…n}表示與客戶相關(guān)聯(lián)的節(jié)點集合；

Γi＝{j：（i，j）∈A}表示節(jié)點i∈V后所有節(jié)點的集合；表示節(jié)點i∈V前所有節(jié)點的集合。

y i為二元變量，表示當客戶i∈V c有車輛服務時，y i為1，否則為0。

（3）參數(shù)

d ij為路段（i，j）上的非負成本；

t i j為路段（i，j）上的出行時間；

P i表示每個客戶i∈V c在沒有車輛接送的情況下，對總成本的貢獻；

e i表示每個參與者i∈V＇最早從起始點出發(fā)的時間；

l i表示每個參與者i∈V＇最晚到達目的地的時間；

Q k表示每輛服務車輛k∈Vs的可用座位數(shù)；

T k表示司機可接受的從家到公司的最大行駛時間；

s i表示每個參與者i∈V＇上車點的時間；

h k表示車輛k∈V s到達公司的時間。

（4）數(shù)學模型

在LCPP模型中，目標函數(shù)（1）要求最小化車輛到達目的地所消耗的路徑成本與未受服務的客戶相關(guān)懲罰所產(chǎn)生的成本之和；式（2）確保每輛車離開其出發(fā)點；式（3）則確保每輛車到達目的地；式（4）是連續(xù)性約束；式（5）和（6）分別是容量和行駛時間限制；式（7）和（8）定義了到達時間變量S i（i∈V＇）；不等式（9）和（10）設置了車輛到達公司的時間h k（k∈Vs），并確保每個員工i∈V＇在時間l i內(nèi)到達公司；式（11）確保每個客戶要么被車輛接走，要么不給該客戶提供服務；式（12）和（13）限制了變量為0-1變量；式（14）是對正數(shù)的限制。

2.1 目標函數(shù)

共享出行問題的優(yōu)化目標大致可以分為二類：運營成本目標和服務質(zhì)量目標［4］。LCPP模型就是將運營成本作為優(yōu)化目標，這一目標通常是對系統(tǒng)范圍內(nèi)的運營成本進行優(yōu)化，例如最大化服務乘客的數(shù)量、最小化行駛路程等。服務質(zhì)量目標包括最小化乘客等待時間、最小化乘車時間，以及最小化實際乘車時間與期望乘車時間之間的差異等。

許多關(guān)于共享出行問題的研究目標只包括運營成本，并將服務質(zhì)量作為模型中的約束條件，以確保達到一定的服務水平。最常見的優(yōu)化目標主要集中在最小化總行駛時間和總行駛距離。例如，考慮時間窗、車輛容量、最大用戶乘車時間等約束條件下，以最小化總路徑成本為目標函數(shù)構(gòu)建模型［9］。

單一的運營成本目標可能一定程度上確保了較為低級的服務水平，不能做到提供優(yōu)化的服務質(zhì)量，應綜合考慮兩個或多個單目標組合的多目標系統(tǒng)，處理多目標問題的3種主要方法，將目標匯總為一個加權(quán)總和目標函數(shù)［10］；考慮分層的目標函數(shù)［11］；采用帕累托原則解決多目標問題［12］。

2.2 路徑限制

在共享出行系統(tǒng)中，司機需要將每一位乘客從各自的起始點接上車，并送往相對應的目的地，而且車輛應該首先訪問起始點，式（2）和式（3）。Masoud等提出了一種實時優(yōu)化的乘車匹配算法，在最大化系統(tǒng)中服務的乘客數(shù)量的同時，通過考慮用戶對出行需求的偏好以及最小化換乘次數(shù)和乘客等待時間，使出行盡可能舒適［13］。此外，DARP和共享出租車等共享出行系統(tǒng)對于車輛有特別的要求，需要車輛從某一特定倉庫出發(fā)，并在完成行程后返回其中的任何一個倉庫，而且必須保證每輛車離開和到達相應的位置，這也確保了流量的守恒。

2.3 容量限制

容量限制是依據(jù)車輛本身的因素決定的，是為了防止共享車輛資源被過度使用，式（5）對應的是容量約束。在共享出行系統(tǒng)中，容量限制將可參與共享的用戶數(shù)量限制在該車輛空閑座位數(shù)量的范圍內(nèi)。而對于一些特殊的乘車群體例如患者，可能需要擔架或輪椅才能運輸，從而導致一位用戶占用多個座位。在Detti等的研究中，容量限制與車輛中的可用座位數(shù)以及每個乘客占用的座位數(shù)有關(guān)［14］。

2.4 成本限制

在共享出行系統(tǒng)中，為了與其他的交通方式相比更有競爭力，合理的成本限制對用戶來說更具有吸引力。Kann指出在共享出行系統(tǒng)中，乘客只會被分配到比他們目前通勤成本便宜的拼車系統(tǒng)中［15］；劉佳針對以生活性出行為目標的出租車動態(tài)合乘問題，提出了出租車合乘定價模型，將現(xiàn)狀模型中的固定折扣率根據(jù)合乘人數(shù)的不同變?yōu)榭勺儼俜直?，同時，還加入了乘客繞行距離補償、乘客等車時間補償、司機停車時間補償，使得司機和乘客利益雙贏且獲利均衡，收費方式更加合理［16］。

2.5 時間限制

大多數(shù)的共享出行系統(tǒng)都要涉及到時間約束，而時間限制是決定用戶體驗的服務等級的重要因素，上述模型中式（6）、式（7）和式（8）是時間約束。硬時間窗的考慮意味著車輛路線受到每個客戶上車和下車的相對嚴格的時間限制。對于硬時間窗來說，是在給定的時間表中，車輛必須在其時間窗內(nèi)到達目的地，否則解決方案是不可行的。相反，可以付出代價來違反軟窗口，因此可以將其視為硬時間窗的推廣。此外，用戶最大乘車時間限制了用戶可以花在車輛上的時間，通過為所有用戶強加一個固定的值來表示用戶最大乘車時間。

2.6 用戶偏好限制

除了時間要求以外，還有其他重要的因素導致用戶是否愿意接受共享出行系統(tǒng)給出的匹配結(jié)果。比如，Levin認為女性客戶可能會覺得與陌生男性單獨拼車不安全［17］。用戶與某些特定群體參與共享出行可能會有所顧慮，比如有些用戶只想與自己熟悉的人共享。用戶對潛在共享出行者的限制越多，該用戶的匹配成功率就越低。

3 共享出行問題求解方法

在共享出行問題求解方法的研究中，大多數(shù)集中于開發(fā)精確算法和啟發(fā)式算法來解決這些問題，并以此為分支展開，如圖2所示。如LCPP的共享出行問題是車輛路徑問題的拓展，屬于NP難題。精確算法是針對具體的模型或問題，運用相關(guān)的數(shù)學理論，最后求得問題的最優(yōu)解。啟發(fā)式算法，是在合理的花費（平衡所占的空間和所需的時間）內(nèi)，算法給出某個優(yōu)化問題中的可行解，但不能保證該解是否為最優(yōu)解。

3.1 精確式算法

精確算法是一種基于運籌學原理的優(yōu)化算法，常見的精確算法有分支定界法、動態(tài)規(guī)劃法、列生成法等。這些精確式算法通常應用于解決確定性數(shù)據(jù)的靜態(tài)問題，例如，Cordeau針對多車輛靜態(tài)DARP采用分支定界算法求解［4］。列生成算法適用于求解一類每個決策方案對應整體規(guī)劃模型中約束矩陣的一列的組合優(yōu)化問題，該算法不是直接處理所有的方案，而是將問題分解成主問題和子問題，并基于當前生成的列的子集，通過限制主問題進行優(yōu)化求解；其余的方案在改善限制主問題當前最優(yōu)解時，才會進入該子集。

使用列生成算法求解整數(shù)規(guī)劃問題時，通常會將限制主問題松弛為線性規(guī)劃問題，得到線性松弛問題的最優(yōu)解后，再用整數(shù)規(guī)劃求解。但是往往得不到整數(shù)最優(yōu)解，因此需要使用分支定價求整數(shù)最優(yōu)解。Parragh等設計了一種分支定價算法，將列生成嵌入到分支定界算法中，以解決請求和利潤分割的問題［18］。

圖2 共享出行問題求解方法分類Fig.2 Classification of shared travel problem solving methods

3.2 啟發(fā)式算法

精確算法雖然能夠求得問題的最優(yōu)解，但是在求解大規(guī)模問題時難以在有效時間內(nèi)求得最優(yōu)解，而采用啟發(fā)式算法可以求得一個接近最優(yōu)解的解。由于LCPP屬于NP難題，在求解最優(yōu)解時計算較為復雜，且容易陷入局部最優(yōu)，所以采用啟發(fā)式算法在有限的時間內(nèi)尋得最優(yōu)解。遺傳算法（GA）是一種基于種群的元啟發(fā)式算法，受到物種進化的啟發(fā)，Jorgensen等研究的DARP的目標是在滿足服務質(zhì)量的同時最小化運輸成本，提出一種基于經(jīng)典的先分群再排路線方法，該方法在使用GA為車輛分配客戶和使用啟發(fā)式算法構(gòu)造車輛的獨立路線問題之間交替進行［19］。

模擬退火算法（SA）最早的思想由N.Metropolis等于1953年提出，它是元啟發(fā)式算法的一種，搜索過程中引入了隨機因素，在迭代更新可行解時，以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解［20］。由于SA能夠避免陷入局部最優(yōu)狀態(tài)，因此Kirkpatrick認為該算法與簡單的局部搜索相比，不僅能接受改善目標函數(shù)的解決方案，而且還能接受其它解決方案［21］。

禁忌搜索算法（TS）由Glover提出，該算法遵循局部搜索的原理，通過標記并有意識的避開找到的一部分局部最優(yōu)解，以此來獲得更多的搜索空間［22］；Cordeau通過將單個請求從一條路線重新定位到另一條路線來生成鄰域，采用多元化策略，懲罰長期采取的方案，暫時接受不可行的方案，從而改善包含禁忌屬性的最佳解決方案［23］。在給定的迭代次數(shù)后，將執(zhí)行其他路線內(nèi)的局部搜索，TS來處理現(xiàn)實生活中更復雜的共享出行系統(tǒng)。

Hansen和Mladenovi在1997年首次提出變鄰域搜索算法（VNS），該算法的基本思想是在搜索過程中系統(tǒng)改變鄰域結(jié)構(gòu)集來拓展搜索范圍，獲得局部最優(yōu)解，再基于此局部最優(yōu)解，重新改變鄰域結(jié)構(gòu)集，拓展搜索范圍來找到另一個最優(yōu)解的過程［24］；Parragh等針對單目標DARP提出了一種具有3種鄰域類型的VNS，即交換鄰域、鏈式鄰域和零分割鄰域［25］。

大規(guī)模鄰域算法（LNS）最早由Shaw在1997年提出，其搜索機制包括拆解和重構(gòu)兩個部分，此算法在每次迭代中，先將一部分解決方案拆解，再將該解決方案重構(gòu)成一個完整的解決方案。LNS一般使用單個破壞和修復的運算符，而自適應大鄰域搜索算法（ALNS）則應用一個或多個特定的破壞和修復的運算符。Ropke和Pisinger通過添加不同的移除和重新插入算子以及自適應算子選擇方案將ALNS作為LNS的拓展，解決帶有時間窗的收發(fā)貨問題，并考慮多達982個請求［26］。在此基礎上，Timo在每次迭代中使用自適應權(quán)重的輪盤賭方法選擇移除和重新插入算子，并應用模擬退火準則［27］。

在對各種類型的共享出行問題進行求解時發(fā)現(xiàn)單獨地利用某一種算法對該問題求解時，會出現(xiàn)早熟、局部優(yōu)化等問題，而將元啟發(fā)式算法與其他類型的元啟發(fā)式算法或精確式算法等方法相結(jié)合形成混合算法，可以取長補短，解決許多組合優(yōu)化問題［28］。

4 結(jié)束語

共享出行問題是一個涉及路徑約束、時間約束、容量約束等的復雜路徑規(guī)劃問題。隨著新的出行需求的提出，相應的共享出行問題和算法需要被研究以滿足需求，因此本文對未來的發(fā)展和研究提出以下建議。

目前共享出行問題的求解算法是根據(jù)研究問題自身的特定條件和總體目標設計出來的，不同的共享出行問題有自己特定的約束集。如參與運輸?shù)能囕v都選擇污染小、耗能少的電動汽車，則需要考慮車輛在有限區(qū)域內(nèi)行駛范圍約束以及對充電時間和充電站的選擇約束，這使得現(xiàn)有的算法可能不能直接用于特定的變體，以至于算法應用過于狹窄。因此，未來一個潛在的研究方向是修改現(xiàn)有的算法或開發(fā)新的算法，來確定共享出行變體問題的可行解決方案，特別是對于那些具有特定約束的問題。這樣不僅能減少算法計算的時間，而且能夠提升算法的優(yōu)化效果，避免多余的無用優(yōu)化，增強算法尋找最優(yōu)解的能力，從而提高了算法的求解效率，加強了算法的適用性。