利用和聲分散搜索算法解決動態共乘的乘客選擇研究

侯立文，劉 思,2

(1.上海交通大學安泰經濟管理學院，上海 200030；2. 上海理工大學管理學院，上海 200093)

1 引言

動態共乘(dynamic ridesharing，DR，在我國稱為拼車)就是某人利用信息交流平臺為出行需求相匹配的他人提供及時搭乘服務，這在客觀上對緩解城市交通壓力，改善環境狀況非常有益，大大提高了汽車服務效率，因而在諸如美國的西雅圖，加拿大的哥倫比亞，歐洲的都柏林、蘇黎世和亞洲的新加坡等地都流行起來，也催生了大量以此為業務的創業公司，如國外的uber、zimride、zipcar和國內的滴答拼車、51用車等，都取得了市場認可。而我國更是創造了春節拼車10天突破100萬參與者的記錄，目前已有北京、上海、杭州、廣州等五十多個城市陸續開展了拼車服務。但現實情況也對DR提出了挑戰，除了法律和信任等備受關注的問題之外，DR在帶給乘客快捷、低成本的同時，也需要乘客有耐心、有時間與其他乘客共同完成一次出行(如果一輛車允許同時服務3位乘客，對一位乘客而言，最糟糕的情況是第一個上車，最后一個下車)，也就是說，乘客在得到正效用的同時也伴隨著負效用。由于DR是一種新興出行模式，多數人希望能以乘客身份事先體驗一下這種服務，因而造成市場上乘客的人數遠遠多于司機，于是如何為每個司機尋找合適的乘客就是DR服務得以實現的一個關鍵問題，因為乘客分布在城市的不同地點，需要在合理的時間內到達各自的目的地，而司機不僅要滿足這些要求，而且也要符合自己的時間和目的地要求。

目前，關于DR的研究在國內外剛開始，兩篇綜述性文獻Furuhata等[1]和Agatz等[2]分別從DR發展歷程、對象分類、研究重點和模型方法等幾方面進行了介紹，為該領域的研究梳理了脈絡。根據這兩篇文獻，與本文研究相關的領域主要集中在共乘優化，優化的對象包括司機和乘客的最佳匹配Herbawi和Weber[3]，程杰等[4]；肖強等[5]、最優路線設計張瑾和何瑞春[6]、接送策略Abdel-Naby和Fante[7]，Winter和Nittel[8]和信息利用Tao Chichung和Chen Chunying[9]，Amey[10]，以及運營成本和服務水平劉書曼等[11]，邵增珍等[12]等幾方面。大部分文獻都屬于理論研究，優化問題的模型結構和求解算法都比較豐富，特別是非經典優化算法的應用已十分普遍，極大拓展了人們對該領域問題的理解。另外，許多其它領域的文獻對本文的研究也具有借鑒意義，比如在傳統合乘(carpool)和電話叫車問題(dial-a-ride-problem)領域，也常常需要建立包括最短路程在內的多目標優化問題，并且也會用到啟發式算法Cordeau和Laporte[13]，Dominik和Roberto[14]。而在車輛路徑問題(vehicle routing problem)研究中，帶有時間窗的同時取送貨方面的研究Berbeglia等[15]，Cortes等[16]在目標函數、約束條件和搜索算法等方面與本文有相似之處(不同點在于共乘不要求回歸原點)，比如顏瑞等[17]也是利用混合式啟發算法對車輛裝箱問題進行了優化，而符卓等[18]所考慮的需求可拆分和時間窗也與本文的研究有相似之處。

總體而言，由于問題背景不同，上述研究尚不能回答一般共乘(國內學者幾乎都集中在出租車共乘)的最優乘客選擇問題，面對大規模路網下既要找到效用最大的乘客，又要盡可能保持最短的行程還需要更有效的算法的幫助，而本文正是面對這一挑戰，在確保司機參與意愿情況下，力求使所搜索到的乘客的效用和共乘行程同時達到最優。以優化的角度來看，本文所描述的DR問題屬于多目標、多約束的大規模離散組合優化問題，最優解的搜索不但存在很多約束，同時也是一個多維度、多目標問題，有時甚至是一個隨機過程中的多階段、多層次的優化問題，因而求解具有較大難度。司機和乘客的分布點、路線、時間限制和獲得的效用共同構成了這樣一個復雜的DR系統，對于這樣一個多目標優化問題，由于各優化目標之間存在無法改善的相互制約關系，只能根據Pareto原則在多個目標之間進行平衡和協調，當問題規模較大，且約束較多時，傳統的經典算法不得不讓位于各類智能優化算法，而本文所采用的加入分散搜索(Scatter Search，SS)機制的和聲搜索(Harmony Search，HS)算法就屬于這樣一類算法，該算法以記憶庫取值概率和微調概率取代了梯度搜索，因此并不需要衍生信息。通過對所構建的DR模型進行求解，證明該算法完全可行。

2 多目標共乘模型

本文假定在一個DR系統中，潛在乘客人數遠遠大于司機人數，也就是說，每個司機一定最多只能同時服務3位乘客(因為一輛轎車搭乘3位乘客其舒適性較高)，且司機事前能獲得乘客起訖點和時間約束的信息。這個系統希望每個司機所選擇的乘客可從共乘服務中獲得最大效用，這一考慮與畢笑天和何瑞春[19]等的研究比較類似，而乘客在獲得正效用的同時也伴隨著負效用。正效用主要來自于節省的成本、較好的便利性、社交機會和更多的自由時間，同時也省去了自駕車時的緊張感；負效用主要來自于接送其他乘客而耽誤的時間和潛在的不安全感。當然系統也應確保司機在途徑接送乘客的這幾個固定點后所行駛的總路程最短。

(1)

其它各參數含義如下：

ui+-共乘帶給第i個乘客的正效用

ui--共乘帶給第i個乘客的負效用

di、di+k-從停車點i或i+k到下一個停車點的距

S-車速(常量)

d0-從司機的出發點到第一個停車點的距離

vi-司機從服務第i個乘客獲得的效用

V0-司機的保留效用(常量)

T0-司機的時間要求

Ti-第i個乘客的時間要求

目標函數f1指明，最優解必須使得乘客獲得的凈效用最大，如果乘客的負效用大于其獲得的正效用，那么xi=0，所以從這個意義上講，這里的正負效用都應屬于感知效用(perceived utility)。目標函數f2的含義就是最優解應構成最短路，盡可能減少司機的成本。

3 和聲分散搜索算法

3.1 和聲搜索算法和分散搜索算法

和聲搜索最早由Geem等[20]在2001年提出，是模仿樂師在創作過程中不斷嘗試使自己演奏的樂器發出的音符盡可能與其它樂器完美匹配，在每次調整過程中，都記住匹配完美的部分，再繼續調試其余部分，如此反復，直至形成“最優曲調”。和聲搜索算法主要由三個變量共同實現：和聲庫大小、和聲記憶庫保留概率(Harmony Memory Considering Rate，HMCR)和擾動概率(Pitch Adjusting Rate, PAR)。相比傳統的最優化算法，和聲搜索算法利用的已知量較少Mahdavi等[21]，Verma等[22]，初始值的確定較容易，而且是一種根據記憶庫取值概率和微調概率進行隨機搜索的算法，從而取代了梯度搜索。

分散搜索算法是一種為了解決復雜的整數規劃問題而提出的采用智能迭代機制的全局搜索算法王曉晴等[23]，它運用種群策略和“分散-收斂集聚”機制獲取高質量和多樣性的解，并保存在參考集中，這種具有一定記憶能力的參考集使得搜索策略調整成為可能，通過結合迭代得到的合并子集共同更新參考集，以此迅速獲得全局最優解。分散搜索算法注重在多樣性和集中性兩方面進行搜索，很適合求解大規模多目標優化問題Beausoleil[24]，Russell和Chiang[25]。

基于和聲搜索算法里和聲庫的保留特點，借用精確算法中分支定界法的思想，本文將和聲搜索和分散搜索兩種算法結合了起來，把分散搜索機制加入到和聲搜索算法中，構造出和聲分散搜索(Harmony Scatter Search，HSS)算法，該算法既保留了和聲搜索算法的全局搜索能力，又充分利用了分散搜索算法的靈活性，從而非常適合解決大規模路網下多目標0-1規劃共乘模型。

3.2 算法步驟

3.2.1 初始解選擇

由于多目標問題解的特殊性，HSS算法在初始值的選擇上對HS算法進行了改進，避免了大部分初始解都是劣解而導致搜索效率低下的情況。算法首先根據解集的精度系數A(即精度的倒數)對決策變量的取值范圍M(是一個A1*n維的矩陣，A1是第一次迭代的精度系數)進行劃分，之后將每段的中位數隨機放入和聲庫內，這里稱為和聲實驗集(Trial Set)，初始大小為TS(也是一個矩陣)。同時，對實驗集中所有m個目標向量初始化，即F=F(f1，f2,…,fm)，其中，fi為目標集中某一目標函數，并將實驗集中的每個解向量的初始標志Flag置為1。

(1)

TS=M(Random(xi-median))

Fx=F(fj(TS))Flag=[1,1,…1]

TS設定好之后，根據實驗集中每個目標的值，按Pareto最優解的選擇機制篩選出當前實驗集中的非劣解集，將其放入和聲參考集(Reference Set)中，并設初始參考集理想容量值為RS。這樣，經過基本HS算法處理的初始非劣解集就產生了。當經過N1次迭代產生RS’大小的非劣解集后，初始化迭代結束。

3.2.2 實驗集和參考集的更新

初始化的實驗集經篩選進入參考集后，尋優將采用SS機制。與分枝定界的思想一致，即每個參考集中的解集都是一個尋優子樹的根節點。SS算法搜索的每個子集就是根節點產生的子節點。每次隨機產生的子節點如果劣于父節點，那么就去掉這一分枝。每產生一次子節點，都要放入實驗集進行篩選更新。具體步驟如下：

步驟1初始化產生參考集的容量RS(即根節點個數，也就是利用SS算法搜索RS棵樹)，每棵樹的子節點數目Node設定為：

(3)

(4)

步驟3由于每個解分量有PAR的可能性進行擾動，而PAR與每個參考集中各個解分量xi的方差成正比。

PAR=PAR*Variance(ReferenceSet(xi))

(5)

步驟4將所有產生的第二層子樹的解集更新到實驗集中，并將原根節點解集(即參考集)中的解集也放入實驗集，然后按Pareto最優解原則再次篩選非劣解。

步驟5當迭代次數小于N2時，返回步驟1，否則，第二次篩選計算停止。

步驟6根據具體問題要求和解的結果決定是否進行精度為Ai=3的第三次篩選，篩選過程同第二次篩選，依次類推。

把所有得到的解向量代入目標函數，得到相應的目標向量值，然后對每個目標向量值進行Pareto最優解篩選。只有滿足Pareto優勝關系時，才能從實驗集中淘汰被支配的解向量，這樣既保證了解集的多樣性，又不會造成Pareto 最優解的遺漏。在算法中，每個解向量都會有一個Flag標記，當某個解向量被判斷為劣解后，其對應的Flag被置為0。比較結束后，所有Flag=1的解向量都是當前的支配解。以上算法的流程如圖1所示。

圖1 和聲分散搜索算法流程圖

4 仿真實驗

4.1 參數設置

首先構建一個由100*100稀疏矩陣的鄰接圖生成的路網(即該路網由1萬個節點構成)，為便于理解和展示，圖2僅給出了一個10*10的路網。對一個DR系統而言，所有司機和乘客都會分布在該路網中，而路網中節點間的距離、每個乘客的目的地和司機與乘客的時間約束都將隨機產生，當然，時間可以進一步區分為等待時間和行駛時間，然后利用模型確定估值[26]，但考慮到本文的重點，在此不做深入討論。比較相鄰節點間的距離限制為50，乘客獲得的正負效用區間分別是[10，30]和[5，15]，司機的效用區間為[1，10]，司機的保留效用設定為5，車速范圍是[30，80]，司機和乘客的行程時間要求都不超過90。迭代次數設為10萬，這也是初始和聲庫的大小，根據經驗，可設HMCR=0.8，PAR=0.1。實驗所對應的場景是：在這1萬個節點的每個節點上都有一個候選乘客(節點編號即為乘客編號)，他們都有自己唯一的下車點(也已編號標記)和時間限制，司機從起點出發(不在圖中)，去往終點Node100。

根據效用的設置方式下面將對兩種情形進行仿真實驗，第一種情形是基本模型，假設司機和乘客的效用都可以直接從它們的效用區間中任意選取，但一旦選定，就不能再變，模型中的其它參數也是如此。第二種情形則以合適的效用函數替代效用值區間，根據事先給出的效用函數求得效用值，其余參數仍然采用第一種情形里的設置。

圖2 100個節點構成的路網

4.2 算法流程與仿真結果

由于是求兩個最優目標，所以仿真過程分為在最短路上尋找滿足約束條件的可行解和在可行解中尋找效用最大的乘客這兩步。對于第一步，最短路上的時間約束和司機獲得的效用是判斷節點是否可行的依據，為此首先計算司機與路網中任意3個節點(也就是3個潛在乘客)及其對應的下車點組合而成的DR系統的最短路(有100*98*96種組合)，然后再根據最短路上的行程時間判斷是否滿足約束條件。所有滿足約束的節點組合構成可行節點集(也就是解向量)，最后根據所有可行節點的目標值確定Pareto最優解集。對于最短路徑問題，我們采用經典的Dijkstra算法來實現，而在所有候選乘客中尋找滿足約束條件的可行解則是一個0-1規劃問題。將問題稍作轉換便可利用啟發式算法(即HSS算法)求得結果，經過多次迭代最終可得到可行解的和聲庫，并同時計算出目標函數值(即可行乘客獲得的效用以及經過的總距離)，然后將可行解進行多目標優化處理，得到最終的Pareto最優集。具體仿真過程如圖3所示。

圖3 仿真計算流程圖

仿真運算進行了3次(采用主頻為2.2MHz，內存為8G的四核服務器進行計算，每次耗時大約4小時，因此沒有進行太多次實驗)，每次都顯示出有9個Pareto最優解，表1展示了其中一次的結果。比如在第一組中，司機所選的乘客是編號為第205、758和第960號，此次共乘帶給他們的總效用是50，總行程2919。本次總行程的變化范圍是4542-2727=1815，方差為800。當總行程大于4381后，就不存在最優解了，說明超過該行程的乘客效用比目前的最優解都低。

圖4展示了此次仿真所獲得的所有可行解和Pareto最優解的分布，就最優解而言，總行程越大，帶給乘客的效用也越大，這符合成本與收益的一般關系，但最優解集似乎可分為兩部分，它們之間有顯著的跳躍性。

表1 基于效用區間的仿真結果

圖4 模型的可行解和 Pareto 最優解的分布(效用區間)

表2是第二種情形的仿真結果。與第一種情形相比，最優解增加了4個，乘客的效用有大幅度提升(均值增加了1.7倍)，總行程的變化范圍(4142-2677=1465)和偏差(方差為500)也都顯著縮小。這些結果說明采用效用函數形式能發現更多合適的乘客，而且帶來更大的效用和更短的行程。

表2 基于效用函數的仿真結果

圖5是此次仿真對應的可行解與Pareto最優解的分布。可行解的分布顯示出存在一個上界，而且大量集中于該上界附近。同時，Pareto最優解也顯示了一定的連續性，這不同于第一種情形的跳躍式。

4.3 算法比較

為了進一步展示HSS算法的優勢，我們也使用了Xia Jizhe等[27]提出的禁忌搜索算法(TABU Search algorithm)同時對問題進行了仿真，禁忌搜索算法也是一種廣泛使用的智能優化算法，禁忌圖帶有記憶功能，而禁忌搜索機制常常能避免算法陷入局部最優，并使其搜索方向跳出有限的解域。但是同時計算速度較慢，尤其在多目標優化問題中往往不容易找到最優的帕累托曲面解。我們在第一個基本拼車問題中，設置了相同的參數和初識范圍，使用禁忌搜索方法和HSS方法對計算同時進行了仿真，得到的結果比較如下：

從圖中結果可以得到，HSS算法不但可行解數量多于TABU搜索算法的結果，而且HSS算法仿真結果Pareto最優解集為13個，TABU搜索算法的僅為8個。同時從Pareto解最優曲線的形狀看出，TABU搜索算法的曲線并不光滑，存在未找到的最優解可能性很大，而HSS算法結果的最優曲線上解相對密集，解的質量也同時也優于TABU搜索算法。再者，TABU搜索算法的運行時間是HSS算法運行時間的7.76倍左右，算法的復雜度也遠高于和聲搜索算法。

圖5 模型的可行解和 Pareto 最優解的分布(效用函數)

圖6 HSS算法得到的可行解和Pareto最優解分布曲線

圖7 TABU Search算法得到的可行解和Pareto最優解曲面

5 結語

DR服務的出現為緩解當前城市交通壓力提供了一種補充途徑，然而由于市場上司機和乘客數量的不對稱導致DR匹配的實現往往不能達到最佳水平，乘客從共乘中獲得的效用可能伴隨著更長的行駛距離，為此本文在考慮了乘客效用最大化和行駛距離最短兩個目標的前提下，建立了針對最佳乘客選擇的多目標優化模型，模型的求解采用HS算法和SS算法的結合，從而有利于在大規模路網條件下找到Pareto最優解。在進行仿真實驗時，針對乘客效用的兩種形式分別進行了實驗，結果顯示，采用效用函數能發現更多合適的乘客，而且還能得到更好的Pareto最優解。總體而言，本文的研究既包括建立雙節點路網系統，并找出所有節點組合的最短路徑，也完成了一個離散的多目標0-1規劃問題的求解，從而進一步拓展了DR領域的研究內容，但盡管如此，本文尚存在一些不足，最明顯的就是各個參數的標定或隨機化處理，比如車輛速度和時間窗，而這正是本文后續的主要研究內容；另外，針對HSS算法的進一步優化和改進也值得研究，以便提高模型的運算速度。