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

胡忠愷，袁鵬程

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

0 引 言

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

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

1 共享出行問題

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

1.1 乘車共享問題（Ridesharing）

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

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

1.2 拼車問題（The Carpooling Problem）

拼車問題（The Carpooling Problem，CPP），從19世紀70年代中期開始，受石油危機影響，近20%的通勤出行者使用拼車上下班，其受歡迎程度開始激增［2］。Baldacci等（2004）研究拼車作為一種由大公司組織的運輸服務，以這家公司的員工為單位，將具有相同出發點的用戶分為一組，組員輪流做司機或者選擇固定的司機，目的是鼓勵員工在上下班時能接送同事，最大限度的減少往返公司辦公的私家車車輛［3］。這種拼車是屬于持續的、長期的拼車模式，被稱為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位用戶設計行駛路線和時間窗，而這些用戶可以在指定起始點和目的地之間實現共享出行。其目的是在約束條件下規劃一組m條最低成本的車輛路線，以容納盡可能多的用戶［4］。傳統的DARP主要是給老年人或殘疾人提供門到門的交通服務，通常以最小化成本為目標［5-6］。DARP與動態共享問題（dynamic ridesharing）主要的區別在于，DARP中的駕駛員可以給更廣泛的乘客提供服務，因為在這種情況下，駕駛員是屬于向乘客提供服務的一方，因此對于行駛路線和時間的限制較為寬松。

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

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

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

2 模型特征

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

（1）集合

V＝{ 0，…，n}＝{ { 0}∪V＇}表示調度路網中所有節點的集合，其中節點0代表目的地，也就是公司所關聯的節點；

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

V s＝{ 1，…，n s}表示與服務車輛相關聯的節點集合；

V c＝{n s+1，…n}表示與客戶相關聯的節點集合；

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

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

（3）參數

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

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

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

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

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

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

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

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

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

（4）數學模型

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

2.1 目標函數

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

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

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

2.2 路徑限制

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

2.3 容量限制

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

2.4 成本限制

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

2.5 時間限制

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

2.6 用戶偏好限制

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

3 共享出行問題求解方法

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

3.1 精確式算法

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

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

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

3.2 啟發式算法

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

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

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

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

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

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

4 結束語

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

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