利用和聲分散搜索算法解決動(dòng)態(tài)共乘的乘客選擇研究

侯立文，劉 思,2

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

1 引言

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

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

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

2 多目標(biāo)共乘模型

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

(1)

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

ui+-共乘帶給第i個(gè)乘客的正效用

ui--共乘帶給第i個(gè)乘客的負(fù)效用

di、di+k-從停車點(diǎn)i或i+k到下一個(gè)停車點(diǎn)的距

S-車速(常量)

d0-從司機(jī)的出發(fā)點(diǎn)到第一個(gè)停車點(diǎn)的距離

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

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

T0-司機(jī)的時(shí)間要求

Ti-第i個(gè)乘客的時(shí)間要求

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

3 和聲分散搜索算法

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

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

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

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

3.2 算法步驟

3.2.1 初始解選擇

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

(1)

TS=M(Random(xi-median))

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

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

3.2.2 實(shí)驗(yàn)集和參考集的更新

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

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

(3)

(4)

步驟3由于每個(gè)解分量有PAR的可能性進(jìn)行擾動(dòng)，而PAR與每個(gè)參考集中各個(gè)解分量xi的方差成正比。

PAR=PAR*Variance(ReferenceSet(xi))

(5)

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

圖3 仿真計(jì)算流程圖

仿真運(yùn)算進(jìn)行了3次(采用主頻為2.2MHz，內(nèi)存為8G的四核服務(wù)器進(jìn)行計(jì)算，每次耗時(shí)大約4小時(shí)，因此沒有進(jìn)行太多次實(shí)驗(yàn))，每次都顯示出有9個(gè)Pareto最優(yōu)解，表1展示了其中一次的結(jié)果。比如在第一組中，司機(jī)所選的乘客是編號(hào)為第205、758和第960號(hào)，此次共乘帶給他們的總效用是50，總行程2919。本次總行程的變化范圍是4542-2727=1815，方差為800。當(dāng)總行程大于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個(gè)，乘客的效用有大幅度提升(均值增加了1.7倍)，總行程的變化范圍(4142-2677=1465)和偏差(方差為500)也都顯著縮小。這些結(jié)果說明采用效用函數(shù)形式能發(fā)現(xiàn)更多合適的乘客，而且?guī)砀蟮男в煤透痰男谐獭?/p>

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

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

4.3 算法比較

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

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

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

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

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

5 結(jié)語

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