考慮駕乘人員公平性的網(wǎng)約出租車合乘路徑優(yōu)化模型

曹 弋，周澤禹，李金洋

(大連交通大學(xué)交通運(yùn)輸工程學(xué)院，遼寧大連 116028)

1 引言

隨著我國城市社會(huì)經(jīng)濟(jì)的快速發(fā)展，居民出行需求日益增長，城市打車難問題愈加突出.出租車作為城市交通的重要組成部分，平峰與高峰時(shí)期的運(yùn)輸能力與需求不匹配.傳統(tǒng)的出租車拼客行為會(huì)造成過分繞行現(xiàn)象，導(dǎo)致乘客出行成本與時(shí)間增加.網(wǎng)約車具有智能調(diào)度與路徑選擇的優(yōu)勢(shì)，可提供合理的合乘費(fèi)用，降低總運(yùn)行成本[1].鑒于上述情況，有必要針對(duì)網(wǎng)約出租車合乘模式，綜合考慮路徑合理性、額定載客量、時(shí)間窗條件與乘客及駕駛員利益等因素，以系統(tǒng)合乘路徑最短為目標(biāo)，研究合乘路徑優(yōu)化模型及算法，以推廣網(wǎng)約出租車合乘出行模式的應(yīng)用前景.

國內(nèi)外對(duì)該領(lǐng)域的研究，早期主要集中于合乘模式.如Lee等人[2]提出了服務(wù)于公交接駁的出租車合乘調(diào)度系統(tǒng).盡管是研究接駁問題，但其模型與算法的核心是組合路徑優(yōu)化問題，仍可為本研究提供理論借鑒.Zhang等人[3]設(shè)計(jì)了一套由調(diào)度云服務(wù)器、乘客客戶端與車載定制裝置組成的網(wǎng)約車合乘系統(tǒng).

隨著方便、快捷、綠色、環(huán)保等出行理念逐漸深入人心，近年來有關(guān)合乘路徑優(yōu)化算法的研究成果不斷涌現(xiàn).其中，以遺傳算法為主導(dǎo)思想的有: Huang等人[4-5]提出了基于遺傳算法的合乘路徑匹配算法，用于求解合乘服務(wù)的多目標(biāo)優(yōu)化問題.同時(shí)還將遺傳算法與模糊控制系統(tǒng)相結(jié)合，來進(jìn)行合乘路徑優(yōu)化及車輛匹配.Jiau等人[6]提出了一種由移動(dòng)客戶端與云合乘服務(wù)模塊組成的智能合乘系統(tǒng).系統(tǒng)后臺(tái)采用遺傳算法優(yōu)化求解合乘路徑并匹配合乘車輛.Zhou等人[7]將合乘路徑與費(fèi)用分擔(dān)問題統(tǒng)一考慮、同時(shí)優(yōu)化，以出行者時(shí)間費(fèi)用成本最小為目標(biāo)函數(shù)構(gòu)建優(yōu)化模型，并采用遺傳算法求解.其他算法包括: 文獻(xiàn)[8]研究了具有時(shí)間窗約束的多車合乘分布式算法.利用合乘概率矩陣與兩階段隨機(jī)優(yōu)化算法，解出了多車合乘模型的最優(yōu)解.文獻(xiàn)[9]提出了用于解決大范圍乘客分布及合乘路徑選擇的禁忌搜索算法，并利用實(shí)際數(shù)據(jù)進(jìn)行了驗(yàn)證.Xiao等人[10]以上下車距離最小、合乘等待時(shí)間最短與到達(dá)目的地時(shí)間最短為目標(biāo)函數(shù)，構(gòu)建了網(wǎng)約車合乘多目標(biāo)優(yōu)化模型，通過引入信息熵來分配權(quán)重向量的方法得到了滿意路徑.Filcek等人[11]采用動(dòng)態(tài)規(guī)劃法和Dijkstra算法，求解得到了匹配合乘用車及合乘線路.Chou等人[12]提出了基于隨機(jī)粒子群優(yōu)化的合乘路徑與匹配算法.

此外，也有學(xué)者就合乘網(wǎng)約車定價(jià)問題進(jìn)行了研究.如Zhong等人[13]基于供需關(guān)系與社會(huì)公平性原則，研究提出網(wǎng)約車合乘收費(fèi)模型.Wang等人[14]基于均衡模型，定量評(píng)估平臺(tái)定價(jià)策略對(duì)網(wǎng)約車市場(chǎng)表現(xiàn)的影響.Li等人[15]基于聯(lián)合博弈分析，探討了合乘服務(wù)的動(dòng)態(tài)定價(jià)方法.Liu[16]基于城市網(wǎng)約車架構(gòu)，構(gòu)建定價(jià)模型并對(duì)網(wǎng)約車價(jià)格進(jìn)行優(yōu)化.

盡管國內(nèi)外對(duì)網(wǎng)約車合乘路徑優(yōu)化問題進(jìn)行了一定的研究，但主要側(cè)重于算法本身.即通過設(shè)計(jì)不同的算法或算子，來高效求解.未能兼顧系統(tǒng)最優(yōu)與乘客公平性原則進(jìn)行建模.此外，在合乘路徑優(yōu)化模型中，也缺少對(duì)駕駛員與合乘乘客收益的約束.鑒于上述問題，本文針對(duì)近年來興起的網(wǎng)約出租車合乘出行方式，在研究合乘路徑優(yōu)化模型的同時(shí)，側(cè)重討論在系統(tǒng)最優(yōu)的前提下，依據(jù)繞行距離來確定動(dòng)態(tài)合乘價(jià)格，使得繞行距離較長的合乘路徑獲得更多的費(fèi)用補(bǔ)償.同時(shí)，在優(yōu)化模型約束條件中平衡考慮網(wǎng)約車駕駛員與合乘乘客的收支問題.研究成果對(duì)于提高出租車承載率、降低出租車運(yùn)營成本及乘客出行成本、推廣網(wǎng)約車合乘出行模式，進(jìn)而緩解城市打車難問題具有重要的理論借鑒意義與實(shí)際應(yīng)用價(jià)值.

2 問題描述與模型假設(shè)

分析表明，網(wǎng)約出租車合乘路徑優(yōu)化問題，事實(shí)上是帶時(shí)間窗的車輛路徑問題(vehicle muting problem with time window，VRPTW)的擴(kuò)展[17-18]，需要考慮如下幾個(gè)問題.

1) 組合優(yōu)化問題.在某一時(shí)間段內(nèi)，即系統(tǒng)刷新時(shí)間，路網(wǎng)中存在r對(duì)乘車需求.將其中的哪幾對(duì)需求組合起來，由某1輛網(wǎng)約車承運(yùn)，配合其他組合路徑，可使系統(tǒng)總運(yùn)營里程最短.

2) 網(wǎng)約車指派問題.在上述時(shí)間段內(nèi)，路網(wǎng)中存在k輛網(wǎng)約車.指派哪幾輛網(wǎng)約車分別對(duì)應(yīng)為上述幾組乘客服務(wù)，可獲得系統(tǒng)最優(yōu)合乘方案.

3) 最短路問題.系統(tǒng)合乘路徑方案確定后，即給出了每輛網(wǎng)約車承載合乘需求的節(jié)點(diǎn)次序.接下來需要求解各相鄰節(jié)點(diǎn)間的最短路徑.由于兩點(diǎn)間最短路問題屬于運(yùn)籌學(xué)中的經(jīng)典問題，可由Dijkstra算法等經(jīng)典算法求解，故而本文不做討論.

針對(duì)問題1)與2)開展研究并建模，可做如下數(shù)學(xué)描述: 路網(wǎng)中有r對(duì)乘車需求(1，2，···，r)，各自對(duì)應(yīng)唯一一對(duì)起終點(diǎn).同時(shí)有k輛可供合乘的網(wǎng)約車(1，2，···，k)，網(wǎng)約車額定載客人數(shù)為Q.某時(shí)刻車輛s中的乘客人數(shù)為ps，乘客給定的時(shí)間窗為[Ti1，Ti2].要求滿足ps≤Q，≤Ti2的條件下，求最優(yōu)合乘方案，使得系統(tǒng)運(yùn)營總里程最短.

網(wǎng)約出租車合乘路徑優(yōu)化模型在車輛指派過程中遵循以下基本假設(shè): 1)所有服務(wù)車輛均以已知速度行駛在路網(wǎng)上;2)預(yù)約乘客的時(shí)間窗條件固定且已知;3)乘客節(jié)點(diǎn)位置以需求對(duì)為準(zhǔn)，若節(jié)點(diǎn)重合以路權(quán)為0表示兩節(jié)點(diǎn)間距離;4)每對(duì)乘客需求人數(shù)均不大于車輛載荷.本文涉及到的集合、索引、參數(shù)、變量如表1所示.

表1 優(yōu)化模型中的參數(shù)和變量Table 1 Parameters and variables in the optimization model

3 合乘路徑優(yōu)化模型

3.1 目標(biāo)函數(shù)

本文以系統(tǒng)合乘路徑之和最短為優(yōu)化目標(biāo)，構(gòu)建的目標(biāo)函數(shù)如式(1)所示:

3.2 車輛路徑約束

車輛路徑約束代表了網(wǎng)約出租車在路網(wǎng)上行駛的基本規(guī)則[19]，如式(2)-(5)所示:

約束(2)-(3)保證了對(duì)于任意一個(gè)起終點(diǎn)都有且僅有同一輛車服務(wù).約束(4)保證了到達(dá)任意節(jié)點(diǎn)的車輛與該節(jié)點(diǎn)出發(fā)的車輛是同一輛車.為了保證其有效性，假設(shè)每個(gè)乘客需求節(jié)點(diǎn)到車輛發(fā)車起點(diǎn)的距離均為0，即反向距離定義為0;正向距離仍為實(shí)際距離.這樣，當(dāng)網(wǎng)約車行駛至最后一個(gè)需求終點(diǎn)時(shí)，可視作返回了發(fā)車起點(diǎn).約束(5)保證了任意一對(duì)需求必須由同一輛車服務(wù).若存在相同起點(diǎn)或終點(diǎn)的兩組及以上需求，則以不同序號(hào)標(biāo)記節(jié)點(diǎn).

3.3 額定載客量約束

在網(wǎng)約車提供合乘服務(wù)過程中，要保證任意時(shí)刻車內(nèi)乘員數(shù)小于等于其額定載客人數(shù)，如式(6)所示:

約束(6)對(duì)每一個(gè)弧(i，j)的車輛容量進(jìn)行限制，保證車輛運(yùn)營時(shí)車內(nèi)人數(shù)均不大于最大載客量Q.Ps表示某時(shí)刻第s輛車車內(nèi)乘客人數(shù)，其數(shù)值由算法計(jì)算確定.即在初始車內(nèi)人數(shù)的基礎(chǔ)上，每接運(yùn)一個(gè)訂單，就加上該訂單對(duì)應(yīng)的乘客數(shù)，每完成一個(gè)訂單，就減去該訂單對(duì)應(yīng)的乘客數(shù)，以遞歸方式計(jì)算車內(nèi)乘車人數(shù).

3.4 時(shí)間窗約束

乘客在接受合乘出租車服務(wù)時(shí)，總是期望網(wǎng)約車能夠在其預(yù)計(jì)的時(shí)間范圍內(nèi)到達(dá).因此，乘客需提供期望到達(dá)時(shí)間段區(qū)間[Tj1，Tj2]，即時(shí)間窗條件.本文取Tj0為乘客容忍度變差的臨界點(diǎn)，由此進(jìn)行軟時(shí)間窗約束，如圖1所示.

圖1 時(shí)間窗示意圖Fig.1 Time window diagram

由時(shí)間窗的含義可知，網(wǎng)約車在提供合乘服務(wù)的過程中，允許有繞行，但其繞行后到達(dá)j點(diǎn)的時(shí)間，不能超過乘客預(yù)期最大時(shí)間Tj2，但可以小于乘客最早到達(dá)時(shí)間Tj1.

式(7)表示車輛s由i點(diǎn)到達(dá)j點(diǎn)的時(shí)刻.約束(8)為子環(huán)消除，其中B是一個(gè)時(shí)間極大值，其值遠(yuǎn)大于i，j兩點(diǎn)間實(shí)際運(yùn)行時(shí)間，保證了時(shí)間順序的合理性，使車輛到達(dá)i點(diǎn)的時(shí)刻必在j點(diǎn)之前.

式(9)表示車輛s經(jīng)過節(jié)點(diǎn)i與節(jié)點(diǎn)j所需要的時(shí)間.約束(10)表示車輛實(shí)際到達(dá)時(shí)間應(yīng)小于乘客要求的最晚到達(dá)時(shí)間Ti2.約束(11)表示車輛s到達(dá)節(jié)點(diǎn)i的時(shí)刻小于乘客給定的最早到達(dá)時(shí)間Ti1，則車輛s須在節(jié)點(diǎn)i等待至乘客最早到達(dá)時(shí)間才能離開節(jié)點(diǎn)i.約束(12)表示車輛s到達(dá)i點(diǎn)的時(shí)刻在乘客最早到達(dá)時(shí)間與車輛最晚到達(dá)時(shí)間之間時(shí)，可以忽略乘客上車時(shí)間，即車輛到達(dá)時(shí)間與車輛離開時(shí)間相同.

該懲罰函數(shù)表示在Ta0＜＜Ta2時(shí)，即車輛晚到情況下，通過對(duì)乘車價(jià)格優(yōu)惠的方式來補(bǔ)償車內(nèi)乘客與候車乘客等待時(shí)間的損失.當(dāng)＜Ta0時(shí)，即車輛早到情況下，盡管會(huì)使車內(nèi)乘客等待候車乘客，但畢竟早于車輛預(yù)計(jì)到達(dá)時(shí)間，相當(dāng)于用節(jié)省下來的繞行時(shí)間來等待候車乘客，故而不做懲罰.同時(shí)，對(duì)于實(shí)際運(yùn)行時(shí)間Ta0＜＜Ta2的情況，所增加的運(yùn)行成本，即懲罰函數(shù)將在下文乘客及駕駛員收益約束中予以考慮.

3.5 乘客及駕駛員收益約束

定義任意乘客的非合乘出行的費(fèi)用為cr，如式(14)所示.從乘客角度考慮，在提高個(gè)體網(wǎng)約車運(yùn)營效益的同時(shí)，如不兼顧合乘乘客的費(fèi)用節(jié)省，將導(dǎo)致其對(duì)網(wǎng)約車合乘服務(wù)失去積極性.因此，需要確保每一對(duì)合乘需求費(fèi)用低于其非合乘出行的費(fèi)用.

約束(15)定義了繞行比例，并保證服務(wù)車輛繞行里程不超過最短路徑的1.6倍[19].式(16)為非合乘情況下，第r組乘客應(yīng)支付的乘車費(fèi)用.式(17)為合乘情況下，第r組乘客應(yīng)支付的乘車費(fèi)用.合乘折扣率α是0～1之間的數(shù)，其值大小同時(shí)影響駕駛員收益與乘客費(fèi)用.α越大，表示乘客需支付的費(fèi)用越高，當(dāng)其接近1時(shí)，表示乘客要支付接近非合乘情況的全部費(fèi)用.對(duì)于小規(guī)模路網(wǎng)α應(yīng)取較大值.隨著路網(wǎng)規(guī)模的增大，可以取較小的值.本案例路網(wǎng)規(guī)模較小，若取小值，將難以保證駕駛員收益.該式也保證了繞行距離長的合乘路徑，具有更低的折扣率，以獲得更多的乘車費(fèi)用補(bǔ)償.因此，考慮了不同組乘客，因合乘繞行距離的不同而產(chǎn)生的不公平性.

從駕駛員角度考慮，也需要確保其在提供合乘服務(wù)時(shí)得到的收益不低于傳統(tǒng)非合乘方式的收益，才能保持其提供合乘服務(wù)的積極性.

式(18)代表駕駛員本次最低收益標(biāo)準(zhǔn)，即以傳統(tǒng)非合乘方式行駛相同里程時(shí)的收益.約束(19)保證駕駛員收益必須大于或等于最低收益標(biāo)準(zhǔn).在合乘路徑中，若網(wǎng)約車把第1位乘客送到目的地并在此后接到了第2位乘客，即第2位乘客的起點(diǎn)次序在第1位乘客終點(diǎn)以后，這種情況兩位乘客的費(fèi)用均按式(14)計(jì)算.

統(tǒng)一的用戶管理模塊能夠使圖書館對(duì)各個(gè)資源平臺(tái)的用戶信息進(jìn)行統(tǒng)一管理；能夠統(tǒng)一處理來自內(nèi)部及外部應(yīng)用系統(tǒng)和用戶管理系統(tǒng)之間的數(shù)據(jù)互操作，以此增強(qiáng)用戶數(shù)據(jù)的開放存取及用戶信息的共享服務(wù)；能夠建立更安全、更高效、更友好、支持使用范圍更廣、更具通用靈活性的圖書館多類型用戶的統(tǒng)一認(rèn)證、集中授權(quán)的體系架構(gòu)。

本模型在合乘計(jì)價(jià)時(shí)，通過定義并引入繞行比例與繞行補(bǔ)償系數(shù)，使得繞行時(shí)間長的乘客獲得更多費(fèi)用補(bǔ)償，以此來兼顧系統(tǒng)最優(yōu)與用戶公平性.

4 基于遺傳算法的模型優(yōu)化求解

4.1 算法比較與選擇

合乘模式的網(wǎng)約出租車問題屬于NP難問題，不能用常規(guī)代數(shù)式解決.經(jīng)過多年發(fā)展，解決帶時(shí)間窗的車輛路徑問題的常用優(yōu)化算法比較如表2所示.

通過表2對(duì)幾種優(yōu)化算法的優(yōu)缺點(diǎn)比較，結(jié)合合乘路徑優(yōu)化模型的特點(diǎn)，即每一對(duì)合乘需求均對(duì)應(yīng)一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，且每一輛出租車分別由其當(dāng)前所處位置出發(fā)，分別完成各自的合乘運(yùn)輸任務(wù)，選擇遺傳算法來求解合乘路徑優(yōu)化模型.同時(shí)，該路徑優(yōu)化問題必須滿足需求對(duì)的順序和對(duì)應(yīng)條件，如采用簡單交叉變異算子，將可能產(chǎn)生大量不可行解.因此，在傳統(tǒng)遺傳算法上改進(jìn)交叉變異機(jī)制，提高算法計(jì)算效率.

表2 現(xiàn)代優(yōu)化算法比較Table 2 Comparison of modern optimization al-gorithms

4.2 染色體編碼方案

本研究對(duì)染色體使用十進(jìn)制數(shù)編碼[20].路徑優(yōu)化模型的解向量可編成一條長度為2r+3k+1的染色體，即: (0，s1，i1，i2，···，ia，0，s2，ia+1，ia+2，···，ib，0，sj，ij···，0，sk，ic，···ir，0).系統(tǒng)共有k輛網(wǎng)約車提供合乘服務(wù)，每一條子路徑均有一輛網(wǎng)約車完成合乘服務(wù).在每一段編碼中，第2個(gè)自然數(shù)sk表示當(dāng)前提供合乘服務(wù)的網(wǎng)約車編號(hào).第3個(gè)自然數(shù)ir表示提供合乘服務(wù)的網(wǎng)約車當(dāng)前所處位置的節(jié)點(diǎn)編號(hào).其后的編碼i則表示各個(gè)合乘需求起終點(diǎn)編號(hào).

4.3 適應(yīng)度評(píng)價(jià)與選擇

利用目標(biāo)函數(shù)構(gòu)造適應(yīng)度評(píng)價(jià)函數(shù)，采用輪盤賭方式進(jìn)行優(yōu)秀個(gè)體選擇，確保適應(yīng)度大的個(gè)體被選中的幾率高.

4.4 改進(jìn)的交叉算子

將每代種群的染色體中適應(yīng)度最大的染色體直接復(fù)制進(jìn)入下一代.其余染色體按0.6的交叉概率進(jìn)行交叉.由于網(wǎng)約車合乘路徑優(yōu)化問題的約束條件及上下車次序要求，如采用簡單交叉算子，將產(chǎn)生大量不可行解.因此，本文設(shè)計(jì)如下改進(jìn)交叉算子.

1) 分別針對(duì)兩個(gè)父代染色體，選擇其中任意一個(gè)非末位的0元素后第3位至其后第一個(gè)0元素之間的編碼為交叉字段，實(shí)施簡單交叉，產(chǎn)生兩個(gè)子代染色體.

2) 對(duì)于子代染色體，選擇那些因交叉后而產(chǎn)生重復(fù)的自然數(shù).若該數(shù)在非交叉位內(nèi)，則將其刪除;若在交叉位內(nèi)，則予以保留.子代中若存在未訪問的某一乘車需求點(diǎn)，則在染色體的交叉位以外補(bǔ)齊該點(diǎn)對(duì)應(yīng)的自然數(shù).

根據(jù)合乘路徑優(yōu)化模型，從一條路徑中刪除點(diǎn)對(duì)并不會(huì)影響路徑的可行性.同時(shí)，統(tǒng)計(jì)子代染色體中由于交換片段而產(chǎn)生的遺失點(diǎn)對(duì)，重新按照之前的插入步驟插入到染色體中.對(duì)新個(gè)體采用了保留優(yōu)秀個(gè)體策略，只有當(dāng)新個(gè)體適應(yīng)度值好于舊個(gè)體時(shí)才更新染色體.

4.5 改進(jìn)的變異算子

變異方法采用個(gè)體內(nèi)部兩位互換方法，按0.1的概率進(jìn)行變異操作.首先從需求起點(diǎn)中隨機(jī)選擇變異位置pos1和pos2，之后將兩個(gè)發(fā)生變異的位置互換，刪除對(duì)應(yīng)終點(diǎn)，最后使終點(diǎn)在其相對(duì)應(yīng)起點(diǎn)所在的子路徑中隨機(jī)選取其后位置插入，且同樣對(duì)得到的新個(gè)體采用了保留優(yōu)秀個(gè)體策略.

5 案例分析

本研究選取大連市局部地區(qū)為案例研究對(duì)象.通過調(diào)查，獲得高峰期5 min內(nèi)網(wǎng)約車乘車需求，其起訖點(diǎn)位置如圖2所示.根據(jù)調(diào)查信息可知各個(gè)需求點(diǎn)的時(shí)間窗信息tj1，tj0tj1+4，tj2tj0+2，如表3所示.

圖2 合乘需求及可用出租車分布Fig.2 Distribution of ride-sharing demand and available taxis

表3 出行需求點(diǎn)的信息Table 3 Information of travel demand points

網(wǎng)約車運(yùn)營費(fèi)用參數(shù)采用大連市現(xiàn)行標(biāo)準(zhǔn)，即起步里程3 km，起步價(jià)10 元，單位計(jì)價(jià)為2 元/km.出租車額定載客量均為4人，初始乘客數(shù)均為0人，平均時(shí)速40 km/h.合乘折扣率α取0.9，繞行補(bǔ)償系數(shù)β取0.4.數(shù)值的選取要兼顧乘車人費(fèi)用節(jié)省和駕駛員通過多次收取費(fèi)用而使盈利增加這兩方面.案例中選取了不同數(shù)值進(jìn)行計(jì)算比較.最終發(fā)現(xiàn)，由于案例路網(wǎng)規(guī)模和合乘規(guī)模偏小，因此若選取的折扣率和繞行補(bǔ)償系數(shù)偏小，乘車人的費(fèi)用雖然較低，但駕駛員收益增加較小，影響駕駛員提供合乘服務(wù)的積極性.

首先借助MATLAB對(duì)遺傳算法編程.生成初始解向量時(shí)隨機(jī)選取的OD點(diǎn).選擇初始種群規(guī)模為80，經(jīng)過300代進(jìn)化，適應(yīng)度函數(shù)趨于穩(wěn)定得到最終結(jié)果，經(jīng)過3次遺傳算法求解，得出了3套組合路徑優(yōu)化方案，如圖3所示.

根據(jù)圖3可以發(fā)現(xiàn)，3次求解結(jié)果中，目標(biāo)函數(shù)在迭代50次以后趨于穩(wěn)定，其中，最優(yōu)組合為方案1，路徑總里程為36.877 km，其路徑如圖4所示.

圖3 迭代次數(shù)與目標(biāo)函數(shù)關(guān)系曲線Fig.3 Relation curve between iteration times and objective function

圖4 最優(yōu)路徑優(yōu)化結(jié)果Fig.4 Optimal path optimization results

同時(shí)使用枚舉算法利用MATLAB編程得最優(yōu)總行駛距離為36.118 km.遺傳算法與枚舉算法計(jì)算得到的組合路徑優(yōu)化結(jié)果如表4所示.2種算法運(yùn)算性能的比較如表5所示.

表4 組合路徑優(yōu)化結(jié)果Table 4 The optimization results of combined path

通過表5數(shù)據(jù)對(duì)比可知，盡管枚舉算法能夠得到全局最優(yōu)解，但在相同的計(jì)算規(guī)模下，遺傳算法的運(yùn)算時(shí)間遠(yuǎn)遠(yuǎn)小于枚舉算法.可以預(yù)見，隨著路網(wǎng)規(guī)模及合乘需求擴(kuò)大至城市級(jí)，枚舉算法的運(yùn)算時(shí)效性將顯著變差，無法滿足網(wǎng)約車實(shí)時(shí)調(diào)度的需要.在計(jì)算精度方面，遺傳算法多次運(yùn)行的結(jié)果波動(dòng)不大，與全局最優(yōu)解的總里程之差僅為0.759 km，在合理范圍之內(nèi).3次運(yùn)算結(jié)果最大誤差為3.6 km，相對(duì)誤差小于總里程的10%，結(jié)果較穩(wěn)定.

表5 算法性能比較Table 5 Algorithm comparison

針對(duì)合乘路徑優(yōu)化方案及同等需求條件下的非合乘方案，進(jìn)行駕駛員收益與乘客費(fèi)用的對(duì)比分析與討論，如表6所示.

表6 出租車及乘客合乘與非合乘方式收益與支出Table 6 Income and expenditure of taxi and passenger with ride-sharing and non-ride-sharing

由表6 數(shù)據(jù)分析可知，在車輛使用方面，本案例共有12 組需求對(duì)，若按照傳統(tǒng)出租車運(yùn)營方式則需要12輛出租車共同完成承接任務(wù);若按本合乘方案，僅用5輛車，其中空駛率僅為10%.而大連市出租車空駛率平均約為52%.證明該方案有效的減少出租車需求量及平均空駛率.在駕駛員收益方面，每輛合乘網(wǎng)約車的駕駛員收益，均大于或等于非合乘方案單個(gè)駕駛員收益的最大值.說明合乘方案能夠充分保障網(wǎng)約車駕駛員的利益及其提供合乘服務(wù)的積極性.在乘客成本方面，合乘方案下每組乘客所支付的費(fèi)用，均小于等于其非合乘方案所應(yīng)支付的費(fèi)用.說明合乘方案在節(jié)省乘客成本的同時(shí)，能夠保障其選擇合乘服務(wù)的積極性.

6 結(jié)論

1) 網(wǎng)約出租車合乘路徑優(yōu)化模型兼顧了系統(tǒng)最優(yōu)與用戶公平性原則，能夠?qū)崿F(xiàn)合乘路徑優(yōu)化.

2) 基于遺傳算法的模型求解結(jié)果與真解的一致性較高.較非合乘方案，在出租車資源節(jié)省、合乘乘客成本降低與網(wǎng)約車駕駛員收益提高等方面具有明顯優(yōu)勢(shì).

由于調(diào)查資源與研究條件所限，案例分析中所研究的路網(wǎng)規(guī)模與合乘出行需求規(guī)模均較小，且乘客時(shí)間窗條件為假定參數(shù).同時(shí)，關(guān)于不同路網(wǎng)及合乘需求規(guī)模對(duì)合乘折扣率的影響問題，可在后續(xù)應(yīng)用研究中進(jìn)行進(jìn)一步探討.盡管如此，本研究在理論建模與算法設(shè)計(jì)方面所得的一般性規(guī)律仍可為同類研究所借鑒.