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

（1.長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長(zhǎng)沙 410004；2.中國(guó)民航大學(xué)空中交通管理學(xué)院，天津 300300）

城市自助式公共出租車(chē)的調(diào)度問(wèn)題探討*

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

（1.長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長(zhǎng)沙 410004；2.中國(guó)民航大學(xué)空中交通管理學(xué)院，天津 300300）

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

城市交通；自助式出租車(chē)；空車(chē)調(diào)度；函數(shù)逼近

自助式公共出租車(chē)是基于“汽車(chē)共享”理念的一種新的出租車(chē)運(yùn)營(yíng)服務(wù)，比傳統(tǒng)汽車(chē)租賃的時(shí)長(zhǎng)更短，比出租車(chē)出行更個(gè)性化和方便，能替代私家車(chē)出行。如何科學(xué)、有效地調(diào)配空車(chē)、控制和降低車(chē)輛調(diào)配成本已成為影響城市自助式出租車(chē)公司運(yùn)作的關(guān)鍵因素之一。

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

1 問(wèn)題描述

在自助式公共出租車(chē)的運(yùn)營(yíng)過(guò)程中會(huì)出現(xiàn)供給與需求不均衡的情況，分為應(yīng)急、偶發(fā)的情況和常規(guī)、定期的情況，需采取車(chē)輛誘導(dǎo)與空車(chē)調(diào)度等方式來(lái)滿足用戶的用車(chē)需求。

（1）應(yīng)急情況下車(chē)輛誘導(dǎo)。調(diào)度信息中心對(duì)用戶用車(chē)的目的地進(jìn)行實(shí)時(shí)反饋，當(dāng)監(jiān)控中心監(jiān)測(cè)到路面行駛的車(chē)輛出現(xiàn)“潮汐”現(xiàn)象時(shí)，將引導(dǎo)指令反饋給區(qū)域內(nèi)的車(chē)輛用戶，建議就近網(wǎng)點(diǎn)停車(chē)，實(shí)現(xiàn)分散和引流的目的。

（2）常規(guī)空車(chē)調(diào)度?？哲?chē)調(diào)配情況是緊急狀況下為保證網(wǎng)點(diǎn)高效運(yùn)營(yíng)而作出的被動(dòng)措施，一般分為兩種情況：一是各網(wǎng)點(diǎn)庫(kù)存車(chē)輛與任務(wù)所需車(chē)輛數(shù)不平衡，即車(chē)輛供不應(yīng)求；二是網(wǎng)點(diǎn)間在某時(shí)段車(chē)輛的供需情況不協(xié)調(diào)，即可能存在有些網(wǎng)點(diǎn)車(chē)輛過(guò)剩，使得網(wǎng)點(diǎn)停車(chē)位不夠還車(chē)停放的現(xiàn)象。

2 車(chē)輛調(diào)度決策模型

2.1條件假設(shè)

（1）交通條件。假定網(wǎng)點(diǎn)與網(wǎng)點(diǎn)之間的運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定，各網(wǎng)點(diǎn)的任務(wù)需求、車(chē)輛數(shù)量及車(chē)輛狀態(tài)隨時(shí)段的推進(jìn)而變化。

（2）服務(wù)周期。設(shè)定的整體服務(wù)時(shí)間范圍能按一定時(shí)長(zhǎng)分成若干時(shí)段，各時(shí)段內(nèi)每個(gè)網(wǎng)點(diǎn)均能產(chǎn)生運(yùn)輸任務(wù)。

（3）網(wǎng)點(diǎn)間運(yùn)輸時(shí)間。由于設(shè)定運(yùn)輸網(wǎng)絡(luò)穩(wěn)定，各網(wǎng)點(diǎn)之間的車(chē)輛運(yùn)行時(shí)間確定。

（4）車(chē)輛分布狀態(tài)。車(chē)型相同，任意時(shí)刻一輛車(chē)可服務(wù)所有類(lèi)型任務(wù)，但僅服務(wù)一個(gè)任務(wù)需求。

（5）提前決策。每個(gè)時(shí)段初可配置好本時(shí)段所需的車(chē)輛和車(chē)位。

（6）初始狀態(tài)。服務(wù)周期初始時(shí)各網(wǎng)點(diǎn)處的車(chē)輛分布情況可從控制中心得知。

（7）車(chē)輛使用形式。車(chē)輛在網(wǎng)絡(luò)系統(tǒng)中循環(huán)使用。

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

2.2目標(biāo)函數(shù)

根據(jù)上述分析，建立如下目標(biāo)函數(shù)：

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

式（1）中，第一項(xiàng)為車(chē)輛選擇運(yùn)輸客戶的費(fèi)用，第二項(xiàng)為車(chē)輛選擇空車(chē)調(diào)配產(chǎn)生的費(fèi)用，第三項(xiàng)為車(chē)輛原地停留的費(fèi)用，第四項(xiàng)為不能滿足顧客需求產(chǎn)生的懲罰費(fèi)用。

2.3約束條件

（1）數(shù)量約束：

（2）服務(wù)任務(wù)數(shù)約束：

（3）停車(chē)位約束：

（4）還車(chē)約束：

（5）空移車(chē)數(shù)、原地駐留車(chē)數(shù)總和的上限約束：

3 算法設(shè)計(jì)思路及流程

3.1目標(biāo)函數(shù)的簡(jiǎn)化與分析

利用函數(shù)逼近的方法簡(jiǎn)化目標(biāo)費(fèi)用函數(shù)的表達(dá)，運(yùn)用線性費(fèi)用函數(shù)近似替代目標(biāo)函數(shù)中的Gt+1（St+1，Pt+1）（見(jiàn)圖1），從而將原問(wèn)題分解為復(fù)雜的多階段、多網(wǎng)點(diǎn)問(wèn)題。

圖1　費(fèi)用函數(shù)的線性逼近

用圖1所示的直線逼近該費(fèi)用曲線時(shí)，當(dāng)費(fèi)用函數(shù)被線性函數(shù)替代后，斜率不變，邊際費(fèi)用可近似用斜率表示，即邊際費(fèi)用成為常量，與無(wú)關(guān)，從而無(wú)需確定時(shí)段t其他各網(wǎng)點(diǎn)發(fā)往j網(wǎng)點(diǎn)的車(chē)輛數(shù)。

3.2邊際費(fèi)用確定及更新

每輛車(chē)可選擇載客服務(wù)、空車(chē)移動(dòng)和原地停留3種運(yùn)作方式。對(duì)于車(chē)輛的不同選擇方式，費(fèi)用值λtNi各不相同：1）當(dāng)t時(shí)段車(chē)輛選擇載客移動(dòng)時(shí)，當(dāng)t時(shí)段車(chē)輛選擇空車(chē)移動(dòng)時(shí)當(dāng)t時(shí)段車(chē)輛選擇原地停留時(shí)

由于控制變量φt（m）的更新需通過(guò)不斷調(diào)整以達(dá)到最優(yōu)，設(shè)第m次調(diào)整后的狀態(tài)向量為（St（m），Pt（m））、解向量為（rt（m），yt（m），zt（m）），選擇指數(shù)平滑法確定和更新控制變量φt（m），過(guò)程如下：

式中：φm為第m次調(diào)整的平滑指數(shù)；φ為根據(jù)經(jīng)驗(yàn)選擇的數(shù)值；αt（m+1）i表示第m+1次調(diào)整中總費(fèi)用函數(shù)關(guān)于的導(dǎo)數(shù)。

3.3空移車(chē)輛數(shù)上限確定及更新

3.4算法設(shè)計(jì)

基于上述分析，算法的核心步驟是如何求解各獨(dú)立的單時(shí)段單網(wǎng)點(diǎn)車(chē)輛調(diào)配問(wèn)題；輔助步驟是確定邊際費(fèi)用控制變量及其更新過(guò)程，該步驟的實(shí)質(zhì)是進(jìn)行多次調(diào)整，即和每更新一次，就對(duì)核心步驟的調(diào)配過(guò)程進(jìn)行調(diào)整，逐次更新調(diào)整直至達(dá)到最優(yōu)解。算法流程見(jiàn)圖2。

圖2　算法流程

4 實(shí)例分析

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

表1　網(wǎng)點(diǎn)間空車(chē)調(diào)度及空閑的成本　元

續(xù)表1

表2　網(wǎng)點(diǎn)間載客服務(wù)所能創(chuàng)造的收益　元

表3　各網(wǎng)點(diǎn)初始車(chē)輛分布情況

表4　時(shí)段1各網(wǎng)點(diǎn)的任務(wù)情況　輛

表5　時(shí)段2各網(wǎng)點(diǎn)的任務(wù)情況　輛

表6　時(shí)段3各網(wǎng)點(diǎn)的任務(wù)情況　輛

運(yùn)用MATLAB對(duì)上述算法與數(shù)據(jù)進(jìn)行計(jì)算，得出每個(gè)時(shí)段空車(chē)調(diào)度方案（見(jiàn)表7～9）。

表7　時(shí)段1空車(chē)調(diào)配方案　輛

表8　時(shí)段2空車(chē)調(diào)配方案　輛

表9　時(shí)段3空車(chē)調(diào)配方案　輛

5 結(jié)語(yǔ)

該文以公共出租車(chē)整體費(fèi)用為目標(biāo)，建立了需求不完全滿足的確定性空車(chē)調(diào)配模型。針對(duì)模型特點(diǎn)及整數(shù)解等要求，通過(guò)空間和時(shí)間上的分解將空車(chē)調(diào)配問(wèn)題簡(jiǎn)化為若干前后關(guān)聯(lián)的時(shí)空階段，利用函數(shù)逼近思想，引入線性的邊際費(fèi)用函數(shù)近似代替原目標(biāo)函數(shù)來(lái)求解模型。

但在模型假設(shè)時(shí)給出的車(chē)輛在運(yùn)輸網(wǎng)絡(luò)系統(tǒng)中任意網(wǎng)點(diǎn)間的運(yùn)行時(shí)間相等，這在實(shí)際中很難實(shí)現(xiàn)，需將車(chē)輛運(yùn)行時(shí)間引入該多時(shí)段動(dòng)態(tài)空車(chē)調(diào)配問(wèn)題中作進(jìn)一步研究。

［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］ 黃肇義.國(guó)內(nèi)城市交通發(fā)展“汽車(chē)共用”的探討［J］.城市交通，2004（3）.

［4］ 周長(zhǎng)峰，廖良才，譚躍進(jìn).多任務(wù)類(lèi)型的動(dòng)態(tài)車(chē)隊(duì)管理問(wèn)題求解方法研究［J］.中國(guó)企業(yè)運(yùn)籌學(xué)，2007（6）.

［5］ 且麗莎.基于“汽車(chē)共享”的空車(chē)調(diào)配問(wèn)題研究［D］.成都：西南交通大學(xué)，2010.

［6］ 徐志良，張鳳鳴.出租汽車(chē)連續(xù)配車(chē)的一個(gè)優(yōu)化逼近探索模型［J］.上海機(jī)械學(xué)院學(xué)報(bào)，1983（4）.

U492.2

A

1671-2668（2016）05-0033-05

2015年湖南省普通高等學(xué)校教學(xué)改革研究立項(xiàng)項(xiàng)目資助（JW-0823）

2016-03-15