城市綜合換乘樞紐的出租車合乘調(diào)度方法

鄭明明，徐洪峰，左忠義

(1.大連交通大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116028； 2.大連理工大學(xué) 交通運(yùn)輸學(xué)院，遼寧 大連 116024)*

城市綜合換乘樞紐的出租車合乘調(diào)度方法

鄭明明1，徐洪峰2，左忠義1

(1.大連交通大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116028； 2.大連理工大學(xué) 交通運(yùn)輸學(xué)院，遼寧 大連 116024)*

分析了城市綜合換乘樞紐實(shí)施出租車合乘的必要性.初步構(gòu)建了面向城市綜合換乘樞紐的出租車合乘組織模式.將出站乘客合乘的組織調(diào)度描述為靜態(tài)一點(diǎn)對多點(diǎn)出租車合乘匹配問題，以出租車數(shù)量最小、總費(fèi)用最小為優(yōu)化目標(biāo)，建立了混合整數(shù)規(guī)劃模型，利用基于遺傳算法和單純形法的啟發(fā)式算法求解該模型.算例分析表明，有效組織綜合換乘樞紐處的出租車合乘可以明顯減少進(jìn)入樞紐站的出租車輛，降低出租車輛行駛的總里程，顯著提高出租車司機(jī)單次出行收入，同時明顯降低乘客平均支出費(fèi)用，能夠體現(xiàn)出較好的社會、經(jīng)濟(jì)效益.

交通工程；出租車合乘；啟發(fā)式算法；城市綜合換乘樞紐

0 引言

出租車合乘(taxi pooling)是指多名乘客自愿同意支付一定的費(fèi)用、共同乘坐同一輛出租車的交通出行模式.從乘客的角度，合乘可以緩解打車難、減少乘車費(fèi)用；從駕駛員的角度，合乘可以降低空駛率、增加營運(yùn)收入.同時，合乘還將產(chǎn)生提高運(yùn)能、節(jié)約能源、減少污染、緩解擁堵等溢出效應(yīng).因此，鼓勵出租車合乘具有十分重要的現(xiàn)實(shí)意義.但是，駕駛員隨意拼客、隨意要價、長距離繞行、長時間等客等行為，在很大程度上影響了乘客的合乘意愿、限制了合乘的推廣實(shí)施.顯然，尋求安全、規(guī)范、高效的出租車合乘運(yùn)營組織模式顯得尤為重要.

根據(jù)乘客起終點(diǎn)的不同，可以將出租車合乘模式分為3類：①起點(diǎn)相同、終點(diǎn)相同的合乘(一點(diǎn)對一點(diǎn))；②起點(diǎn)相同、終點(diǎn)不同或起點(diǎn)不同、終點(diǎn)相同的合乘(一點(diǎn)對多點(diǎn)或多點(diǎn)對一點(diǎn))；③起點(diǎn)不同、終點(diǎn)不同的合乘(多點(diǎn)對多點(diǎn)).根據(jù)組織方式的不同，又可以將出租車合乘問題分為靜態(tài)車輛合乘問題(乘客上車前先組合好，上車后按最佳線路行走即可)和動態(tài)車輛合乘問題(車上已有部分乘客，行駛途中再與其他乘客合乘).Tao提出應(yīng)用基于時空網(wǎng)絡(luò)圖的啟發(fā)式算法求解以單輛出租車行程距離最短和乘客等待時間最小為目標(biāo)的靜態(tài)一點(diǎn)對多點(diǎn)出租車匹配問題[1]，Lee研究應(yīng)用兩步調(diào)度算法求解動態(tài)的多點(diǎn)對一點(diǎn)的多輛出租車匹配問題[2].Jung提出應(yīng)用混合模擬退火算法求解動態(tài)多點(diǎn)對多點(diǎn)的出租車合乘組織[3].Hosni應(yīng)用拉格朗日算法和啟發(fā)式算法求解動態(tài)帶時間窗的多點(diǎn)對多點(diǎn)的出租車合乘調(diào)度[4].周和平和程杰分別應(yīng)用遺傳算法研究靜態(tài)和動態(tài)多點(diǎn)對多點(diǎn)的出租車合乘問題[5- 6].國內(nèi)外的研究集中于多點(diǎn)對多點(diǎn)的出租車合乘問題以及動態(tài)出租車合乘組織，對靜態(tài)一點(diǎn)對多點(diǎn)的出租車合乘組織研究甚少.

本文旨在以滿足城市綜合換乘樞紐處出站乘客的換乘需求為出發(fā)點(diǎn)，基于合乘乘客具有批量到達(dá)，合乘起點(diǎn)相同，請求合乘時間一致，出行距離較長，終點(diǎn)隨機(jī)分布的特點(diǎn)，將其定位為靜態(tài)一點(diǎn)對多點(diǎn)多輛出租車合乘匹配問題.在綜合考慮社會效益、經(jīng)濟(jì)效益的前提下，研究城市綜合換乘樞紐處出租車合乘組織模式及關(guān)鍵調(diào)度技術(shù).

1 城市綜合換乘樞紐出租車合乘組織模式設(shè)計(jì)

1.1 必要性分析

典型的城市綜合換乘樞紐包括機(jī)場、火車站、長途汽車站、客運(yùn)碼頭等，綜合換乘樞紐作為一個復(fù)雜系統(tǒng)，最核心的功能是換乘功能，目前乘客到站后到達(dá)城市內(nèi)部的常見換乘方式主要有城市軌道交通、常規(guī)公共汽車、出租車、社會車輛、步行和其他方式.綜合換乘樞紐處的合乘出租車可以看作一種介于常規(guī)公共汽車和常規(guī)出租車之間的換乘方式，這種換乘方式可以減少進(jìn)出樞紐站的出租車輛數(shù)，有利于節(jié)約停車用地和簡化樞紐站內(nèi)外部的交通組織.區(qū)別于城市軌道交通和常規(guī)公共汽車固定的發(fā)車時刻，合乘出租車可以提供較為及時和靈活的門到門的交通服務(wù).相比常規(guī)出租車，在制定合理的出租車費(fèi)率標(biāo)準(zhǔn)的基礎(chǔ)上，可以降低乘客的出行費(fèi)用.基于樞紐站批量到站的合乘乘客數(shù)量和有效的出租車合乘調(diào)度安排，可以提高出租車滿載率，增加出租車司機(jī)的單次出行收入.

1.2 合乘組織模式

在綜合換乘樞紐站組織乘客合乘出租車，需要構(gòu)建以乘客的合乘需求為驅(qū)動，以合乘信息平臺為核心，出租車輛、合乘停車場、通信設(shè)備及軟件等設(shè)施設(shè)備為支持的服務(wù)系統(tǒng).出租車合乘服務(wù)系統(tǒng)總體構(gòu)架如圖1所示，系統(tǒng)在一個周期(例如5 min)的合乘組織流程如圖2所示.

圖1 出租車合乘服務(wù)系統(tǒng)總體構(gòu)架圖

2 基于城市綜合換乘樞紐站的合乘信息平臺調(diào)度建模及求解

城市綜合換乘樞紐站出租車合乘運(yùn)營組織主要依托于合乘信息平臺的調(diào)度管理，而其中合乘調(diào)度建模及求解是一項(xiàng)關(guān)鍵技術(shù).

2.1 問題描述

城市綜合換乘樞紐站出租車合乘調(diào)度屬于一點(diǎn)對多點(diǎn)的靜態(tài)多輛出租車合乘組織問題.調(diào)度結(jié)果需要確定出租車數(shù)量、乘客乘坐的出租車編號、每輛出租車的服務(wù)路線、每輛出租車的收費(fèi)以及每位乘客的費(fèi)用.而出租車合乘服務(wù)路線與費(fèi)率的確定，不僅要考慮到出租車合乘的社會效益，還要考慮到運(yùn)營車輛和乘客的利益.因此，本文以出租車數(shù)量最少、出租車輛行駛總時間最短和乘客總費(fèi)用最小為優(yōu)化目標(biāo)建立優(yōu)化模型.

2.2 模型的建立

2.2.1 基本假設(shè)

①派出的車輛類型相同，載客能力相同；②中途不允許搭乘其他乘客；③車輛無故障行駛；④任一目的地節(jié)點(diǎn)具有合乘意愿的乘客數(shù)小于出租車容量；⑤出租車輛充足.

2.2.2 數(shù)學(xué)符號定義

圖2 出租車合乘服務(wù)系統(tǒng)組織流程圖

2.2.3 決策變量

(1)車輛數(shù)變量

設(shè)q為車輛數(shù)變量(即路線數(shù)變量)，q∈{1,2，…，N}.

(2)路徑變量

(3)費(fèi)用變量

2.2.4 優(yōu)化模型

(1)

(2)

(12)

(15)

其中,式(1)表示以最少數(shù)量的出租車輛滿足本周期乘客需求，式(2)表示該周期出租車輛行駛總時間和乘客總費(fèi)用最小.考慮到城市綜合換乘樞紐組織出租車合乘的社會效應(yīng)，以最少的出租車輛數(shù)滿足服務(wù)需求可以減少對樞紐站周邊和內(nèi)部交通壓力，節(jié)約停車場用地，以及提高車輛滿載率，降低污染和節(jié)約能源的作用，因此，將出租車輛數(shù)最少最為第一目標(biāo)，總費(fèi)用最小最為第二目標(biāo).式(3)～(15)為約束條件.式(3)、(4)表示每一位乘客只被一輛車服務(wù)，式(5)表示每輛出租車運(yùn)載的乘客數(shù)不能超過其容量限制.式(6)和式(7)表示每一條線路只有一輛車從樞紐站出發(fā)，但不返回樞紐站.式(8)確保每條路徑連續(xù)性.式(9)保證節(jié)點(diǎn)i和j在路線k上是相鄰節(jié)點(diǎn).式(10)和(11)表示每條線路提供合乘服務(wù)的出租車司機(jī)單程收入要比不提供合乘服務(wù)時收入高.式(12)和(13)表示每條線路每位乘客合乘出租車費(fèi)用要較單獨(dú)乘坐出租車時費(fèi)用節(jié)省.

2.2.5 求解算法

(1)算法流程

Step1：輸入樞紐站位置、道路網(wǎng)結(jié)構(gòu)、路網(wǎng)特性、出租車容量等基礎(chǔ)數(shù)據(jù).輸入客戶數(shù)、客戶節(jié)點(diǎn)位置，以車輛數(shù)最少為第一優(yōu)化目標(biāo)，求出所需出租車數(shù)量(即線路數(shù));

Step2：設(shè)定初始化種群大小POP_N，交叉概率pc，變異概率pm，迭代次數(shù)gen等參數(shù)，隨機(jī)生成初始種群;

Step5：按照遺傳策略，對第t代種群進(jìn)行選擇操作、交叉操作和變異操作，形成下一代的種群;

Step6：判斷算法是否滿足停止準(zhǔn)則，如果不滿足，則返回到Step3；如果滿足，則輸出種群中的最大適應(yīng)度值的個體作為最優(yōu)解，終止計(jì)算.

(2)變量編碼

采用遺傳算法計(jì)算時，染色體采用基于客戶點(diǎn)的實(shí)數(shù)編碼方式.編碼給出了各輛出租車搭乘的客戶數(shù)及行駛路徑，用0將不同車輛的路徑隔開.例如染色體078930256041，表示第一輛出租車到達(dá)4個客戶節(jié)點(diǎn)，路徑為0(樞紐站)(- 7- 8- 9- 3，第二輛出租車到達(dá)3個客戶節(jié)點(diǎn)，路徑為0(樞紐站)- 2- 5- 6，第三輛出租車到達(dá)2個客戶節(jié)點(diǎn)，路徑為0(樞紐站)- 4- 1.

(3)適應(yīng)度函數(shù)和選擇算子

由于模型的目標(biāo)函數(shù)是求最小值，所以取目標(biāo)函數(shù)(式(2))的倒數(shù)作為適應(yīng)度函數(shù)，同時采用懲罰函數(shù)法對模型的容量約束條件進(jìn)行處理.通過輪盤賭選擇和精英選擇的策略進(jìn)行選擇操作，即采用輪盤賭選擇得到新種群，然后再采用精英選擇，將前代種群中的最優(yōu)個體賦值給新種群中的最后一個個體.

(4)交叉算子和變異算子

為了保證每個客戶節(jié)點(diǎn)只被服務(wù)一次的約束，本文使用由Oguz在2002年提出的交叉算子A.例如對于兩個父代個體：父代1：(078930256041)和父代2：(012304567089).隨機(jī)從其中一個父代(如父代1)中產(chǎn)生兩個交叉點(diǎn)(豎線位置)，將該父代兩個交叉點(diǎn)之間的有效部分(不含0)作為待交叉基因段，例如父代1(078|9302|56041)的待交叉基因段為{932}.從父代2中找出和父代1待交叉基因段相同的基因{239}，再用父代2中的所找到基因序列{239}替代父代1中的待交叉片段{932}，得到子代1：(078230956041).將父代1中被替換的基因段替換到父代2中，得到子代2：(019304567082).

變異算子采用交換變異，即隨機(jī)選擇兩個有效的基因座(不含0)，然后將兩者互換位置.

3 算例分析

(1)算例

已知一個城市客運(yùn)樞紐站(0點(diǎn))，一個周期內(nèi)30個客戶提出合乘需求，W=[dij]31×30表示在城市道路網(wǎng)中客運(yùn)樞紐0到達(dá)各客戶節(jié)點(diǎn)j=1,2…30以及各客戶節(jié)點(diǎn)間最短路徑距離，平均行駛速度取40km/h.每個客戶節(jié)點(diǎn)的乘客數(shù)均為1.出租車的最大載客能力為4人.R1=0.2，R2=0.2，L0=3km，r0=1.2元/km,c0=8元，取α=0.42元/min，交叉概率取0.9，變異概率取0.09，種群數(shù)為100，迭代次數(shù)為50次.

(2)仿真結(jié)果分析

本算法用Matlab語言編程.測試了20次，得到的實(shí)驗(yàn)數(shù)據(jù)見表1.目標(biāo)函數(shù)最小值為1 097，各出租車的服務(wù)路線如表2所示.本算法為啟發(fā)式算法，無法確定本算法得到的最好解是最優(yōu)解，但是實(shí)驗(yàn)20次，有3次得到本算法所能得到的最優(yōu)解，并且實(shí)驗(yàn)結(jié)果比較穩(wěn)定(波動小于1.03%)，說明本算法是有效的.

表1 仿真結(jié)果

表2 優(yōu)化后服務(wù)路線

出租車合乘調(diào)度前、后各項(xiàng)指標(biāo)比較如表3所示.結(jié)果表明，優(yōu)化調(diào)度后明顯減少了進(jìn)入樞紐站的接站車輛，降低了出租車輛行駛的總里程，帶來了具有較好的社會效益；出租車司機(jī)單次出行的收入顯著提高，同時乘客平均支出費(fèi)用明顯降低，體現(xiàn)了較好的經(jīng)濟(jì)效益.

表3 優(yōu)化前后指標(biāo)對比

4 結(jié)論

(1)本文基于城市綜合客運(yùn)樞紐站的換乘需求特性和合乘出租車的交通特性，提出應(yīng)將合乘出租車視為一種新型的城市綜合客運(yùn)樞紐站換乘方式，并初步設(shè)計(jì)了出租車合乘服務(wù)系統(tǒng)的構(gòu)成和組織模式;

(2)針對核心的合乘組織調(diào)度問題，以出租車數(shù)量最少、出租車輛行駛總時間最短及乘客總費(fèi)用最低建模，并應(yīng)用遺傳算法與單純形法相結(jié)合的啟發(fā)式算法進(jìn)行求解.通過對算例的多次實(shí)驗(yàn)，表明該算法有效，優(yōu)化結(jié)果滿意;

(3)城市綜合換乘樞紐的出租車合乘運(yùn)營模式中的出租車輛路線分配問題、合乘出租車輛停車場選址及布局等問題，均是今后進(jìn)一步研究的內(nèi)容.另外，本文僅考慮了出站旅客的疏散問題，而如何組織城市旅客合乘出租車到樞紐站也是今后需要進(jìn)一步研究的問題.

[1]TAOCHCH,CHENCHY.Heuristicalgorithmsforthedynamictaxipoolingproblembasedonintelligenttransportationsystemtechnologies[J].Proceedings-FourthInternationalConferenceonFuzzySystemsandKnowledgeDiscovery,2007(3):590- 595.

[2]LEEKT,LINDJ,WUPJ.Planninganddesignofthetaxipoolingdispatchingsystem[J].TransportationResearchRecord,2005,1903:86- 95.

[3]JUNGJ,JAYAKRISHNANR.Dynamicshared-taxidispatchalgorithmwithhybrid-simulatedannealing[J].Computer-AidedCivilandInfrastructureEngineering,2016,31(4):275- 291.

[4]HOSNIH,NAOUM-SAWAYAJ,ARTAILH.Theshared-taxiproblem:Formulationandsolutionmethods[J].TransportationResearchPartB:Methodological,2014,70(1):303- 318.

[5]周和平，鐘璧檣，彭霞花,等.出租車合乘路徑選擇與費(fèi)率優(yōu)化模型[J].長沙理工大學(xué)學(xué)報(bào)，2011,8(1):20- 24.

[6]程杰，唐智慧，劉杰,等.基于遺傳算法的動態(tài)出租車合乘模型研究[J].武漢理工大學(xué)學(xué)報(bào)，2013,37(1):187- 191.

[7]吳芳，李志成，徐琛.出租車合乘制調(diào)度優(yōu)化模型研究[J].蘭州交通大學(xué)學(xué)報(bào)，2009,28(1)：104- 107.

A Scheduling Method for Taxi-Pooling Problem in Integrated Transfer Hub

ZHENG Mingming1，XU Hongfeng2，ZUO Zhongyi1

(1.School of Traffic and Transportation Engineering,Dalian Jiaotong University,Dalian 116028,China; 2.School of Transportation and Logistics,Dalian University of Technology,Dalian 116024,China)

For the main functions of integrated transfer hub,the necessity of taxi pooling is analyzed,and its organization mode is provided for integrated transfer hub.According to the characteristics of arriving passengers,this scheduling is classified into the case of one origin to many destinations.By taking into account the benefits of the integrated transfer hub,taxi drivers and passengers,a mixed integer programming model is established and a heuristic algorithm based on genetic algorithm and simplex method is proposed.Finally,the model is tested by an example,and results shows that the taxi pooling decreases the volume and travel distance of taxi as well as the passenger expenses apparently, and increases the driver income evidently.

traffic engineering;taxi pooling;heuristic algorithm;integrated transfer hub

1673- 9590(2017)03- 0001- 06

2016- 09- 19

國家自然科學(xué)基金資助項(xiàng)目(61374193)

鄭明明(1979-)，女，講師，碩士，主要從事城市公共交通規(guī)劃與管理方法研究E-mail:zhengmm1979@126.com.

A