基于匹配條件與調(diào)度的出租車合乘模型的研究與分析

朱易+馬慧敏+劉青+粟宇秋

1.國(guó)防科學(xué)技術(shù)大學(xué)電子科學(xué)與工程學(xué)院，湖南長(zhǎng)沙 410000

2.上海師范大學(xué)建筑工程學(xué)院，上海 201418

摘 要 為了解決當(dāng)前打車難以及行車資源相對(duì)浪費(fèi)的弊端，本文在深入考察當(dāng)前打車環(huán)境的前提下，通過模擬車輛與客戶之間的關(guān)系，建立了以最短路徑為目標(biāo)函數(shù)的合乘出租車調(diào)度模型，以出租車載客量以及乘客服務(wù)供求關(guān)系作為約束條件，利用禁忌搜索算法搜索最優(yōu)路徑，得到最優(yōu)出租車合乘匹配方案。該過程對(duì)于解決打車難，兼顧司機(jī)與乘客的利益具有重要作用。

關(guān)鍵詞 出租車；合乘；最優(yōu)方案；禁忌算法

中圖分類號(hào) TP2 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 2095-6363（2017）13-0018-01

在當(dāng)前車流量日益增加，打車?yán)щy的時(shí)代背景下，對(duì)于出發(fā)地和目的地相近或者行程路線有重合的乘客來說，合乘無疑一種能夠減輕費(fèi)用成本的選擇。對(duì)于出租車司機(jī)來說，合乘可以提高車輛的利用率，在較短的總行駛路程中獲取更大的利益。對(duì)于交通網(wǎng)絡(luò)車流量的管制來說，合乘可以有效控制在早晚高峰期時(shí)城市交通路網(wǎng)的擁堵情況。所以，在不大程度的影響乘客原有交通路線的前提下，合乘可以從多個(gè)方面改善城市交通的壓力，給乘客和司機(jī)都帶來一定程度的效益。那么，推廣合乘業(yè)務(wù)便成為了當(dāng)前出租車行業(yè)各個(gè)公司重點(diǎn)考慮的問題。

1 乘客出行路線類別

有打車意愿的乘客出行路線類別可分為相同出發(fā)點(diǎn)、到達(dá)點(diǎn)，相同出發(fā)點(diǎn)、不同到達(dá)點(diǎn)，不同出發(fā)點(diǎn)、相同到達(dá)點(diǎn)，不同出發(fā)點(diǎn)、不同到達(dá)點(diǎn)這4類，用圖1描述所示。

2 合乘出租車調(diào)度模型的建立

合乘出租車是一種在基于原路線不變或者多乘客共線的前提下，以減少顧客打車等待時(shí)間以及減少出行費(fèi)用，同時(shí)提高汽車資源的利用率，增加司機(jī)收入額新模式。本文所考慮的調(diào)度屬于靜態(tài)車輛調(diào)度范疇，即所有的乘客打車需求信息以及空馳出租車的位置信息在路徑規(guī)劃前都是已經(jīng)確定已知的，不會(huì)再隨著時(shí)間的變化而發(fā)生改變。針對(duì)本文的問題，我們建立合乘出租車調(diào)度模型規(guī)劃合乘匹配乘客的最優(yōu)行車路線，以合乘總路途最短為目標(biāo)使得乘客和出租車司機(jī)雙方都達(dá)到滿意程度。

設(shè)i表示表示第i個(gè)乘客，k表示表示第k輛出租車，oi表示該乘客上車點(diǎn)坐標(biāo)，ui表示該乘客下車點(diǎn)坐標(biāo)，m表示出租車載客人數(shù)，N表示乘客的總數(shù)，M表示乘客的總數(shù)，0

以最短路徑為目標(biāo)函數(shù)，建立的調(diào)度模型如圖所示：

由于車輛調(diào)度問題分類的復(fù)雜性，所以，目前沒有普遍適用的求解算法。我們查閱文獻(xiàn)得知，研究者認(rèn)為，目前很多常見的關(guān)于車輛調(diào)度算法的研究并不能應(yīng)用在合乘出租車這個(gè)領(lǐng)域。針對(duì)本文研究對(duì)象的特殊性，我們通過研究發(fā)現(xiàn)，禁忌搜索算法能在初步檢索中尋找到局部最優(yōu)解，而在進(jìn)一步的搜索中可以有效的避開這些局部最優(yōu)值，從而使得求解結(jié)果更加準(zhǔn)確。因此，本文主要采用禁忌搜索算法來進(jìn)行迭代計(jì)算。

本文使用禁忌搜索算法求解合乘車輛調(diào)度問題的步驟如下：

Step1：解的表示：本文中解采用自然數(shù)編碼，一串自然數(shù)排列首位代表車的序號(hào)k，其他自然數(shù)表示乘客的上下車信息。若有3輛車，9位乘客，則1 5 3 2 3 5 2||2 4 9 6 6 9 4||3 1 7 8 8 1 7表示出租車1、2、3的線路分別為如圖所示：

Step2：解的評(píng)價(jià)方法：對(duì)于解的評(píng)價(jià)方法，首先解應(yīng)滿足問題的約束條件，其次，計(jì)算該解所生成的目標(biāo)函數(shù)值，目標(biāo)函數(shù)值越理想且越符合問題實(shí)際情況，則該解更準(zhǔn)確。本文中采用在全程14中乘客的上下車的表示方法產(chǎn)生的解所確定的車輛路徑方案，應(yīng)滿足每個(gè)乘客僅由一輛出租車提供服務(wù)的約束，同時(shí)滿足出租車的載客數(shù)小于3人的約束條件。除此之外，滿足點(diǎn)緩沖合乘匹配條件和路徑匹配度計(jì)算結(jié)果更高的乘客組的路徑所在的解更優(yōu)。

Step3：鄰域操作方法：禁忌搜索算法是一種基于鄰域搜索技術(shù)的算法，確定鄰域操作方法是構(gòu)造該算法的一個(gè)重要步驟。在本文中，我們采用兩兩交換法實(shí)施鄰域操作，該方法是指隨機(jī)選擇解中的兩個(gè)元素，并交換其值的鄰域操作方法。

Step4：禁忌對(duì)象的確定：禁忌對(duì)象是指禁忌表中被禁的那些局部最優(yōu)解，本文選取滿足第一部分合乘匹配條件的解作為最優(yōu)解。我們將每次迭代得到的最好解作為禁忌對(duì)象放入禁忌表中。

Step5：候選集合的選擇：本文將從當(dāng)前解的鄰域中隨機(jī)選擇若干個(gè)鄰居作為候選集合。

Step6：藐視準(zhǔn)則的判斷：為了防止優(yōu)良解的遺失，當(dāng)某個(gè)禁忌候選解的適配值優(yōu)于當(dāng)前全局最優(yōu)值，解禁此候選解為當(dāng)前解和當(dāng)前全局最優(yōu)解。

Step7：終止條件的確定：本文采用迭代指定次數(shù)的終止準(zhǔn)則。

3 結(jié)論

本文建立了以最短路徑為目標(biāo)函數(shù)的合乘出租車調(diào)度模型，以出租車載客量以及乘客服務(wù)供求關(guān)系作為約束條件，利用禁忌搜索算法搜索最優(yōu)路徑，得到最優(yōu)出租車合乘匹配方案。

參考文獻(xiàn)

[1]張瑾.出租車拼車問題研究及其服務(wù)系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)[D].蘭州：蘭州交通大學(xué)，2009.

[2]張亦楠.出租車合乘模式下的智能匹配問題的研究與實(shí)現(xiàn)[D].青島：中國(guó)海洋大學(xué)，2014.

[3]翟泳，楊金梁，連劍.合乘出行信息檢索的路徑匹配算法[J].交通與計(jì)算機(jī)，2007，1（25）：27-30.

[4]劉佳.出租車合乘方式及定價(jià)模型優(yōu)化研究[D].重慶：重慶交通大學(xué)，2016.