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

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

1.國防科學技術大學電子科學與工程學院，湖南長沙 410000

2.上海師范大學建筑工程學院，上海 201418

摘 要 為了解決當前打車難以及行車資源相對浪費的弊端，本文在深入考察當前打車環境的前提下，通過模擬車輛與客戶之間的關系，建立了以最短路徑為目標函數的合乘出租車調度模型，以出租車載客量以及乘客服務供求關系作為約束條件，利用禁忌搜索算法搜索最優路徑，得到最優出租車合乘匹配方案。該過程對于解決打車難，兼顧司機與乘客的利益具有重要作用。

關鍵詞 出租車；合乘；最優方案；禁忌算法

中圖分類號 TP2 文獻標識碼 A 文章編號 2095-6363（2017）13-0018-01

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

1 乘客出行路線類別

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

2 合乘出租車調度模型的建立

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

設i表示表示第i個乘客，k表示表示第k輛出租車，oi表示該乘客上車點坐標，ui表示該乘客下車點坐標，m表示出租車載客人數，N表示乘客的總數，M表示乘客的總數，0

以最短路徑為目標函數，建立的調度模型如圖所示：

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

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

Step1：解的表示：本文中解采用自然數編碼，一串自然數排列首位代表車的序號k，其他自然數表示乘客的上下車信息。若有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：解的評價方法：對于解的評價方法，首先解應滿足問題的約束條件，其次，計算該解所生成的目標函數值，目標函數值越理想且越符合問題實際情況，則該解更準確。本文中采用在全程14中乘客的上下車的表示方法產生的解所確定的車輛路徑方案，應滿足每個乘客僅由一輛出租車提供服務的約束，同時滿足出租車的載客數小于3人的約束條件。除此之外，滿足點緩沖合乘匹配條件和路徑匹配度計算結果更高的乘客組的路徑所在的解更優。

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

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

Step5：候選集合的選擇：本文將從當前解的鄰域中隨機選擇若干個鄰居作為候選集合。

Step6：藐視準則的判斷：為了防止優良解的遺失，當某個禁忌候選解的適配值優于當前全局最優值，解禁此候選解為當前解和當前全局最優解。

Step7：終止條件的確定：本文采用迭代指定次數的終止準則。

3 結論

本文建立了以最短路徑為目標函數的合乘出租車調度模型，以出租車載客量以及乘客服務供求關系作為約束條件，利用禁忌搜索算法搜索最優路徑，得到最優出租車合乘匹配方案。

參考文獻

[1]張瑾.出租車拼車問題研究及其服務系統設計實現[D].蘭州：蘭州交通大學，2009.

[2]張亦楠.出租車合乘模式下的智能匹配問題的研究與實現[D].青島：中國海洋大學，2014.

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

[4]劉佳.出租車合乘方式及定價模型優化研究[D].重慶：重慶交通大學，2016.