基于排隊論模型的車場出租車調度問題

文/史可為 張心悅 陳潤桓

（南京郵電大學 江蘇省南京市 210003）

1 問題背景介紹

送客到機場的出租車司機會根據實際情況對下一步工作做出兩種選擇：

（1）前往緩沖區等待，載客人返回市區。此時出租車需要付出等待時間成本。

（2）直接空車返回市區載客。此時出租車司機會付出空載損失費用和損失潛在的載客收益。

兩種選擇方式引發了值得探討的問題：

（1）司機應該如何進行決策使自己獲益最大；

（2）管理者應如何管理機場候車區使得總乘車效率最高；

（3）為使收益均衡，管理部門應如何給出租車分配“優先權”。

針對這三個問題建立模型求解。

2 模型的建立與求解

2.1 基于多級評價指標的司機載客方案選擇決策模型

結合文獻和實際情況[1]分析發現司機對某方案收益大小的預估主要取決于機場抵達航班的乘客數量、蓄車池內已在等待的出租車的數量、天氣狀況、道路擁堵情況[2]。因此我們進行指標分級：某段時間內的乘客數量受某時間段內抵達機場的航班數量、蓄車池內已在等待的出租車的數量和當前時間因素（節假日、普通工作日等）影響[3]。

2.1.1 基于線性最小二乘擬合的乘客數量回歸模型

來利用最小二乘法[4]對乘客數量X2關于m個子項指標的變化曲線進行擬合，步驟如下：

首先確定回歸方程的維數。由于不同類別的自然環境和特殊時期對乘客數量的影響程度一般由專家打分得出[5]，均為常數ξ0，因此乘客數量的變化規律是關于某段時間內抵達航班數的二維線性函數。

其次選用曲線擬合中最常見的最小二乘法去擬合含有未知數的函數和已知的n組互不相同的的數據點其中，X2i表示乘客數量X2的n組不同的值，表示指標乘客數量X2的m個子項指標的n組不同值。定義方程：

最后根據最小二乘準則確定回歸方程的函數rk(x)和系數。

2.1.2 基于模糊綜合評判法和熵值法的綜合評價模型

對于站在出租車司機心理角度考慮的模糊問題，在此選擇模糊數學模型來對所篩選的三個一級指標進行綜合評價。步驟如下：

2.2 司機選擇決策模型的具體應用與模型分析

為驗證上述得出的決策模型，在此選取成都雙流國際機場作為研究對象[6]。

2.2.1 原始數據獲取與預處理

我們利用Python爬蟲、成都市出租車GPS數據、四川省氣象局官網、成都市交通運輸局官網，通過合理合法手段采集到了評價體系中所有指標的原始數據。經過數據合理的清洗整理、歸一化、可視化、缺失值和異常值的處理，得到機場蓄車池內出租車的數量、當天出租車乘客數量、完整道路擁堵系數數據等數據。

2.2.2 求解

（1）回歸模型結果。

根據最小二乘法利用SPSS對二維數據進行擬合，得到乘客數量關于其二級指標變化規律的函數表達式為：（2）基于模糊綜合評判法和熵值法的綜合評價模型的求解。

由于我們選取的是雙流國際機場在9月13日具體一天的相關數據，因此將當天24小時分成四等份，求出每個時間段內道路擁堵指數變化率，再根據熵值法求解模糊綜合評價體系因素集中各因素的權重，最終求出9月13日司機在四個時間段內的決策方案為：全時段均選擇方案A。

2.3 基于排隊論的機場出租車上客區服務效率模型

我們參考首都國際機場和虹橋機場的出租車乘車區與“上車點”來分析此類排隊系統的運作情景并建立我們的構想的理想上客區模型。對于該模型按照以下方式設計：

站在出租車司機和機場管理者的角度考慮：司機的主要目標為收益最大、損耗的時間成本最小，與時間成本抵消后剩余的利潤部分就越大；而對于機場管理者，其管理損失主要來源于增設上車點而必須增加的管理費用；站在搭乘出租車的乘客角度考慮：乘客的乘車體驗心理是希望等待時間越少越好。

2.3.1 排隊模型向雙目標優化模型的轉化

考慮在有n個服務點的服務系統中，上客區的服務水平可以保證以95%的置信度，即服務者的服務時間滿足在以乘客為主體的服務系統中，服務效率指的是司機單位時間內的接客數；在以出租車司機為主體的服務系統中，服務效率指的是乘客單位時間內給司機提供的收益值，近似呈指數分布。隊列都遵循“多通道、單階段”的結構。

（1）目標函數①+②。

從乘客想獲得更好的乘車體驗的心理角度建立目標函數為：

從司機想獲得收益的心理角度分析即有：

綜上可得如下遞推關系式：

（2）約束條件。

在“多通道、單階段”的隊列結構中，顧客到達人數分布服從泊松分布[7]，服務者的每次的服務時間分布服從指數分布。

因此約束條件②為：

接著根據Little公式[8]，可以得到在兩個子模型中每個顧客等待被服務的概率和隊列中平均等待的顧客數為：

其中，c為所開設乘客排隊通道的數量。

（3）最終模型。

基于顧客被服務子模型的約束條件：

基于出租車司機和機場管理者損失值子模型的約束條件：

2.3.2 基于窮舉遍歷法的模型求解

根據我們所設計的理想機車出租車上客模型，將上客點開設數量的最大值n設置為10個。

慮避免求解結果陷于局部最優和整體已知數據集的中等規模特性，我們首選窮舉遍歷法尋找目標函數的最優解。得到結果為：為了使上客區總乘車效率最高，應設置5個上車點。

2.3.3 基于粒子群算法的求解優化

為了提高求解效率，接著引入時間復雜度為O(n)的粒子群算法求解原優化問題的最優解，作為解法對比。

使用粒子群算法求解出的最優解看出：通過粒子群算法使ρ的精度精確得到提高，進而目標函數的精確性也得到了提高。

2.4 基于帶優先權排隊論的機場出租車載客模型

首先需要找到合適的指標去衡量出租車收益的大小。由于當前很多城市針對出租車在堵車時低速駕駛的損耗提出了相應的福利政策，因此可以忽略出租車的起步價與另加的公里價之間的差異，用出租車的載客行駛時長來衡量出租車司機的收益。

2.4.1 帶優先權的出租車排隊模型建立

帶優先權排隊模型服從的假設和規則：

（1）模型將優先級分為n類（1級代表最高），n是待求出的未知量。

（2）在同一優先級內出租車司機遵照“先到先服務”原則進行載客。

（3）對任意優先級，乘客到達概率服從泊松分布，司機從機場載客的外出服務時間服從負指數分布[9]。

（4）在分析了成都市出租車的GPS數據后，發現從機場出發的出租車在載客的情況下抵達市區用時最長時間為4小時左右。因此我們認定從機場和市區往返的時間單程超過4小時以上的出租車不參與機場給予的“優先權”優惠政策。

優先級分類和優先級權值的確定：

我們將4小時作為參與優先級評選的出租車外出服務時間的右區間。因此我們在這4小時之內按照對應的優先級權值分配給出租車司機送客完畢重新回到蓄車池內的繼續等待時間。利用如下公式[10]計算非搶占性排隊模型的服務者等待時間：s是上車點的數量，μ是出租車司機的平均服務效率，λ是乘客的平均到達率，并且

其中，

出租車收益價值的衡量指標：

因為出租車在當天的首次排隊時間不確定性極高且對于整天載客情況的影響不大，我們將機場出租車每天的載客過程定義為一個運營周期Ti,j，可得到如下公式：

由于給與短途載客再次返回機場的出租車“優先權”的目的是為了使所有司機在機場的收益更加均衡。即平衡收入差距，我們以優先級個數n為自變量，基于最小二乘法建立如下模型：

求解該最小二乘模型，得出當n=3時目標函數最小。

2.4.2 基于蒙特卡洛仿真的模型求解

通過生成200個出租車并通過蒙特卡洛[11]的思想，隨機的在區間[0.15h,2h]上賦予這些出租車服務時間并在10小時內進行大量模擬，通過計算200個出租車各自的總服務時間，可以看出基于該“優先權處理”方案最終可以較為合理的滿足短途出租車的收益，各出租車收益大體均衡。

3 模型進一步討論

在針對機場出租車問題所建立的模型中，航班數、出租車數據來源真實可靠，數據有一定權威性和可靠全面性，同時綜合考慮了蓄車池車量、航班數、節假日、空氣天氣狀況、道路阻礙系數等各項指標，并且利用了排隊論及仿真模擬了人等車，車等人的情況，較貼合生活實際。但為了適當簡化條件，在查閱文獻時沒有考慮到節假日時期引起的道路擁堵系數的提高，導致計算結果仍不能充分模擬實際生活場景。