城市綜合換乘樞紐的出租車合乘調度方法

鄭明明，徐洪峰，左忠義

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

城市綜合換乘樞紐的出租車合乘調度方法

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

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

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

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

0 引言

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

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

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

1 城市綜合換乘樞紐出租車合乘組織模式設計

1.1 必要性分析

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

1.2 合乘組織模式

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

圖1 出租車合乘服務系統總體構架圖

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

城市綜合換乘樞紐站出租車合乘運營組織主要依托于合乘信息平臺的調度管理，而其中合乘調度建模及求解是一項關鍵技術.

2.1 問題描述

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

2.2 模型的建立

2.2.1 基本假設

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

2.2.2 數學符號定義

圖2 出租車合乘服務系統組織流程圖

2.2.3 決策變量

(1)車輛數變量

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

(2)路徑變量

(3)費用變量

2.2.4 優化模型

(1)

(2)

(12)

(15)

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

2.2.5 求解算法

(1)算法流程

Step1：輸入樞紐站位置、道路網結構、路網特性、出租車容量等基礎數據.輸入客戶數、客戶節點位置，以車輛數最少為第一優化目標，求出所需出租車數量(即線路數);

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

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

Step6：判斷算法是否滿足停止準則，如果不滿足，則返回到Step3；如果滿足，則輸出種群中的最大適應度值的個體作為最優解，終止計算.

(2)變量編碼

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

(3)適應度函數和選擇算子

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

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

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

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

3 算例分析

(1)算例

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

(2)仿真結果分析

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

表1 仿真結果

表2 優化后服務路線

出租車合乘調度前、后各項指標比較如表3所示.結果表明，優化調度后明顯減少了進入樞紐站的接站車輛，降低了出租車輛行駛的總里程，帶來了具有較好的社會效益；出租車司機單次出行的收入顯著提高，同時乘客平均支出費用明顯降低，體現了較好的經濟效益.

表3 優化前后指標對比

4 結論

(1)本文基于城市綜合客運樞紐站的換乘需求特性和合乘出租車的交通特性，提出應將合乘出租車視為一種新型的城市綜合客運樞紐站換乘方式，并初步設計了出租車合乘服務系統的構成和組織模式;

(2)針對核心的合乘組織調度問題，以出租車數量最少、出租車輛行駛總時間最短及乘客總費用最低建模，并應用遺傳算法與單純形法相結合的啟發式算法進行求解.通過對算例的多次實驗，表明該算法有效，優化結果滿意;

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

[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]周和平，鐘璧檣，彭霞花,等.出租車合乘路徑選擇與費率優化模型[J].長沙理工大學學報，2011,8(1):20- 24.

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

[7]吳芳，李志成，徐琛.出租車合乘制調度優化模型研究[J].蘭州交通大學學報，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

國家自然科學基金資助項目(61374193)

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

A