侯立文，劉 思,2

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

1 引言

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

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

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

2 多目標共乘模型

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

(1)

其它各參數(shù)含義如下：

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

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

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

S-車速(常量)

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

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

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

T0-司機的時間要求

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

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

3 和聲分散搜索算法

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

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

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

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

3.2 算法步驟

3.2.1 初始解選擇

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

(1)

TS=M(Random(xi-median))

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

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

3.2.2 實驗集和參考集的更新

初始化的實驗集經(jīng)篩選進入?yún)⒖技螅瑢?yōu)將采用SS機制。與分枝定界的思想一致，即每個參考集中的解集都是一個尋優(yōu)子樹的根節(jié)點。SS算法搜索的每個子集就是根節(jié)點產(chǎn)生的子節(jié)點。每次隨機產(chǎn)生的子節(jié)點如果劣于父節(jié)點，那么就去掉這一分枝。每產(chǎn)生一次子節(jié)點，都要放入實驗集進行篩選更新。具體步驟如下：

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

(3)

(4)

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

PAR=PAR*Variance(ReferenceSet(xi))

(5)

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

步驟5當?shù)螖?shù)小于N2時，返回步驟1，否則，第二次篩選計算停止。

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

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

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

4 仿真實驗

4.1 參數(shù)設(shè)置

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

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

圖2 100個節(jié)點構(gòu)成的路網(wǎng)

4.2 算法流程與仿真結(jié)果

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

圖3 仿真計算流程圖

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

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

表1 基于效用區(qū)間的仿真結(jié)果

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

表2是第二種情形的仿真結(jié)果。與第一種情形相比，最優(yōu)解增加了4個，乘客的效用有大幅度提升(均值增加了1.7倍)，總行程的變化范圍(4142-2677=1465)和偏差(方差為500)也都顯著縮小。這些結(jié)果說明采用效用函數(shù)形式能發(fā)現(xiàn)更多合適的乘客，而且?guī)砀蟮男в煤透痰男谐獭?/p>

表2 基于效用函數(shù)的仿真結(jié)果

圖5是此次仿真對應(yīng)的可行解與Pareto最優(yōu)解的分布?？尚薪獾姆植硷@示出存在一個上界，而且大量集中于該上界附近。同時，Pareto最優(yōu)解也顯示了一定的連續(xù)性，這不同于第一種情形的跳躍式。

4.3 算法比較

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

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

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

圖6 HSS算法得到的可行解和Pareto最優(yōu)解分布曲線

圖7 TABU Search算法得到的可行解和Pareto最優(yōu)解曲面

5 結(jié)語

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