城市自助式公共出租車的調度問題探討*

高志波，吳立烜，彭巍，王倩

（1.長沙理工大學交通運輸工程學院，湖南長沙 410004；2.中國民航大學空中交通管理學院，天津 300300）

城市自助式公共出租車的調度問題探討*

高志波1，吳立烜1，彭巍1，王倩2

（1.長沙理工大學交通運輸工程學院，湖南長沙 410004；2.中國民航大學空中交通管理學院，天津 300300）

自助式公共出租車是一種緩解城市交通問題且適合城市內部短時雙向出行的交通方式，既能減少私家車的使用率，又能滿足顧客的個性化需求。城市交通流的潮汐現象導致各網點供需不均衡，極大影響整個系統的運行。針對該缺陷，文中根據不同時刻各網點的車輛數和顧客的需求量，綜合考慮運輸顧客、空車調配、原地停留等情況的效益，引入懲罰因子對模型進行改善，得到總費用最小、滿意度最佳的決策方案；根據問題特征，設計了求解該問題的簡單函數逼近算法，給出了具體求解流程；最后結合算例，計算得到了最佳城市自助式公共出租車調度方案。

城市交通；自助式出租車；空車調度；函數逼近

自助式公共出租車是基于“汽車共享”理念的一種新的出租車運營服務，比傳統汽車租賃的時長更短，比出租車出行更個性化和方便，能替代私家車出行。如何科學、有效地調配空車、控制和降低車輛調配成本已成為影響城市自助式出租車公司運作的關鍵因素之一。

Matthew Barthand等通過建立多網點汽車共享服務仿真模型，詳細評估了汽車共享服務車輛的分配及使用情況；Karbassi A.等提出了一種汽車共享中路線預測和到達時間評估方法，可在多站臺車輛系統中實現，開發的算法能測算出實際運送路徑和到達時間；黃肇義在分析汽車共享產生意義的基礎上，提出了國內推廣汽車共享服務的具體措施；周長峰等提出了兩種時間窗類型的動態車隊問題，分別以任務分配策略和任務類型的不同構造相應目標函數，分析了針對局部問題的混合整數規劃模型，給出了求解的實際操作策略；且麗莎從汽車共享服務公司和用戶等多個角度考慮，分別建立了隨機需求與考慮用戶滿意度的汽車共享空車調配模型。但在實際情況下，需求情況往往是不能全部預知的，不能簡單地處理為一個確定性的規劃問題。為此，該文以城市自助式公共出租車整體費用為目標，建立需求不完全滿足的確定性空車調配模型，并針對該模型特點及整數解等要求，通過空間和時間上的分解將空車調配問題簡化為若干前后關聯的時空階段進行求解。

1 問題描述

在自助式公共出租車的運營過程中會出現供給與需求不均衡的情況，分為應急、偶發的情況和常規、定期的情況，需采取車輛誘導與空車調度等方式來滿足用戶的用車需求。

（1）應急情況下車輛誘導。調度信息中心對用戶用車的目的地進行實時反饋，當監控中心監測到路面行駛的車輛出現“潮汐”現象時，將引導指令反饋給區域內的車輛用戶，建議就近網點停車，實現分散和引流的目的。

（2）常規空車調度。空車調配情況是緊急狀況下為保證網點高效運營而作出的被動措施，一般分為兩種情況：一是各網點庫存車輛與任務所需車輛數不平衡，即車輛供不應求；二是網點間在某時段車輛的供需情況不協調，即可能存在有些網點車輛過剩，使得網點停車位不夠還車停放的現象。

2 車輛調度決策模型

2.1條件假設

（1）交通條件。假定網點與網點之間的運輸網絡結構穩定，各網點的任務需求、車輛數量及車輛狀態隨時段的推進而變化。

（2）服務周期。設定的整體服務時間范圍能按一定時長分成若干時段，各時段內每個網點均能產生運輸任務。

（3）網點間運輸時間。由于設定運輸網絡穩定，各網點之間的車輛運行時間確定。

（4）車輛分布狀態。車型相同，任意時刻一輛車可服務所有類型任務，但僅服務一個任務需求。

（5）提前決策。每個時段初可配置好本時段所需的車輛和車位。

（6）初始狀態。服務周期初始時各網點處的車輛分布情況可從控制中心得知。

（7）車輛使用形式。車輛在網絡系統中循環使用。

（8）忽略固定成本。不考慮員工薪酬成本、車輛負荷、員工負荷等情況。

2.2目標函數

根據上述分析，建立如下目標函數：

式中：t為服務周期，以Δt等分為H個時段，從而服務周期可表示為t=｛1，2，...，H｝；H為大于等于1的正整數；n為網點個數；ytij為時段t從網點i到j分配空車服務的任務數，?i≠j；φtj+1為j網點在t+1時刻增加一輛車的邊際費用函數；wij為發送運輸任務從網點i到網點j所能創造的純利潤；rtij為從網點i到網點j的空車移動數，?i≠j；cij為網點i與j間空車移動的成本；zti，t+1為網點i由t時段原地停留到t+1時段的空車數；etij為有載客需求從網點i到網點j并且在t時段起運的任務數。

式（1）中，第一項為車輛選擇運輸客戶的費用，第二項為車輛選擇空車調配產生的費用，第三項為車輛原地停留的費用，第四項為不能滿足顧客需求產生的懲罰費用。

2.3約束條件

（1）數量約束：

（2）服務任務數約束：

（3）停車位約束：

（4）還車約束：

（5）空移車數、原地駐留車數總和的上限約束：

3 算法設計思路及流程

3.1目標函數的簡化與分析

利用函數逼近的方法簡化目標費用函數的表達，運用線性費用函數近似替代目標函數中的Gt+1（St+1，Pt+1）（見圖1），從而將原問題分解為復雜的多階段、多網點問題。

圖1　費用函數的線性逼近

用圖1所示的直線逼近該費用曲線時，當費用函數被線性函數替代后，斜率不變，邊際費用可近似用斜率表示，即邊際費用成為常量，與無關，從而無需確定時段t其他各網點發往j網點的車輛數。

3.2邊際費用確定及更新

每輛車可選擇載客服務、空車移動和原地停留3種運作方式。對于車輛的不同選擇方式，費用值λtNi各不相同：1）當t時段車輛選擇載客移動時，當t時段車輛選擇空車移動時當t時段車輛選擇原地停留時

由于控制變量φt（m）的更新需通過不斷調整以達到最優，設第m次調整后的狀態向量為（St（m），Pt（m））、解向量為（rt（m），yt（m），zt（m）），選擇指數平滑法確定和更新控制變量φt（m），過程如下：

式中：φm為第m次調整的平滑指數；φ為根據經驗選擇的數值；αt（m+1）i表示第m+1次調整中總費用函數關于的導數。

3.3空移車輛數上限確定及更新

3.4算法設計

基于上述分析，算法的核心步驟是如何求解各獨立的單時段單網點車輛調配問題；輔助步驟是確定邊際費用控制變量及其更新過程，該步驟的實質是進行多次調整，即和每更新一次，就對核心步驟的調配過程進行調整，逐次更新調整直至達到最優解。算法流程見圖2。

圖2　算法流程

4 實例分析

根據已知網點的布局方案，設立12個自助式公共出租車網點，記為n=｛1，2，…，12｝；系統共有317輛車、360個停車位。假設任意兩個網點間的行駛時間都為1，服務周期內共分為3個任務產生時段，記為t=｛1，2，3｝；網點間的空車調度成本（見表1）、租賃的費用（見表2）、初始的網點分布情況（見表3）、各時段各網點產生的任務（見表4～6）均為已知。下面運用上述模型求解每個時段各網點的空車調配情況。

表1　網點間空車調度及空閑的成本　元

續表1

表2　網點間載客服務所能創造的收益　元

表3　各網點初始車輛分布情況

表4　時段1各網點的任務情況　輛

表5　時段2各網點的任務情況　輛

表6　時段3各網點的任務情況　輛

運用MATLAB對上述算法與數據進行計算，得出每個時段空車調度方案（見表7～9）。

表7　時段1空車調配方案　輛

表8　時段2空車調配方案　輛

表9　時段3空車調配方案　輛

5 結語

該文以公共出租車整體費用為目標，建立了需求不完全滿足的確定性空車調配模型。針對模型特點及整數解等要求，通過空間和時間上的分解將空車調配問題簡化為若干前后關聯的時空階段，利用函數逼近思想，引入線性的邊際費用函數近似代替原目標函數來求解模型。

但在模型假設時給出的車輛在運輸網絡系統中任意網點間的運行時間相等，這在實際中很難實現，需將車輛運行時間引入該多時段動態空車調配問題中作進一步研究。

［1］ Matthew Barthand，Michael Todd.Simulation model performance analysis of a multiplestationshared vehiclesystem［J］.Transportation Research，1999（7）.

［2］ Karbassi A，Barth M.Vehicle route prediction and time of arrival estimation techniques for improved transportationsystem management［A］.Intelligent Vehicles Symposium［C］.2003.

［3］ 黃肇義.國內城市交通發展“汽車共用”的探討［J］.城市交通，2004（3）.

［4］ 周長峰，廖良才，譚躍進.多任務類型的動態車隊管理問題求解方法研究［J］.中國企業運籌學，2007（6）.

［5］ 且麗莎.基于“汽車共享”的空車調配問題研究［D］.成都：西南交通大學，2010.

［6］ 徐志良，張鳳鳴.出租汽車連續配車的一個優化逼近探索模型［J］.上海機械學院學報，1983（4）.

U492.2

A

1671-2668（2016）05-0033-05

2015年湖南省普通高等學校教學改革研究立項項目資助（JW-0823）

2016-03-15