城市综合换乘枢纽的出租车合乘调度方法

郑明明，徐洪峰，左忠义

(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