基于排隊論模型的車場出租車調(diào)度問題

文/史可為 張心悅 陳潤桓

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

1 問題背景介紹

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

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

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

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

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

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

（3）為使收益均衡，管理部門應如何給出租車分配“優(yōu)先權(quán)”。

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

2 模型的建立與求解

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

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

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

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

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

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

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

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

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

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

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

2.2.1 原始數(shù)據(jù)獲取與預處理

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

2.2.2 求解

（1）回歸模型結(jié)果。

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

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

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

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

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

2.3.1 排隊模型向雙目標優(yōu)化模型的轉(zhuǎn)化

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

（1）目標函數(shù)①+②。

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

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

綜上可得如下遞推關(guān)系式：

（2）約束條件。

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

因此約束條件②為：

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

其中，c為所開設(shè)乘客排隊通道的數(shù)量。

（3）最終模型。

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

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

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

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

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

2.3.3 基于粒子群算法的求解優(yōu)化

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

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

2.4 基于帶優(yōu)先權(quán)排隊論的機場出租車載客模型

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

2.4.1 帶優(yōu)先權(quán)的出租車排隊模型建立

帶優(yōu)先權(quán)排隊模型服從的假設(shè)和規(guī)則：

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

（2）在同一優(yōu)先級內(nèi)出租車司機遵照“先到先服務”原則進行載客。

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

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

優(yōu)先級分類和優(yōu)先級權(quán)值的確定：

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

其中，

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

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

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

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

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

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

3 模型進一步討論

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