基于改进H-R双边匹配算法的定制公交合乘优化

孙 峣，白子建，柯水平，申 婵

（天津市市政工程设计研究院，天津 300051）

随着移动互联网的广泛普及，近年来涌现出许多基于手机APP的出行新模式，而定制公交作为一种高品质、低价格的出行方式，受到了越来越多乘客的青睐[1].深圳已开发上线的“小猪巴士”，为乘客提供实时出行需求，运营商接受乘客合乘请求成为了可能.目前，国内外关于合乘问题的研究大都基于出租车或小型共享汽车.Santos和Stiglic等学者[2-3]提出一种采用贪婪算法解决出租车共享的组合优化问题，并定量分析不同类型乘客的灵活性对共享车辆运营稳定性的影响；张薇等[4]提出用数学规划的方法求解车辆合乘的稳定匹配模型；于匡员[5]建立了合乘车辆的运营成本最小化和乘客服务数量最多的多目标函数，采用改进的遗传算法对模型求解，结果证明该模型可以有效提高社会资源利用率；宫熙桢等[6]通过计算合乘问题中司机和乘客付出的费用比例，提出了一种合理的计算方法，减少了因费用问题产生的矛盾.

双边匹配的研究最早源自解决男性和女性婚姻配对问题[7]，随后广泛地应用于许多学科领域.王中兴等[8]认为，以最大化匹配群体的整体满意度为目标得到的结果是最优的；张亦楠[9]通过分析现实中的合乘行为，认为建立以乘客满意度最大化为目标函数的同时，可以保证运营商的成本和市场份额.综上所述，目前，针对定制公交合乘的研究相对较少.本文通过对定制公交合乘问题的分析，分别建立了乘客和定制公交车辆效用函数，提出一种改进H-R双边匹配算法的定制公交合乘优化方法，并对匹配的结果进行比较分析.

1 问题描述

1.1 研究思路

对于本文研究的定制公交合乘优化问题，一方面定制公交运营商可以选择期望的乘客进行服务，另一方面乘客也可以选择合适的车辆完成出行需求.研究思路如图1所示.

图1 定制公交合乘问题研究思路

1.2 定制公交合乘双边匹配要素

（3）路况信息.路况信息包括实时路段交通流信息、路网信息等.实时路段交通流信息可以保证定制公交在保证乘客服务需求的同时，更加灵活地改变运行路径.路网信息由有向图G=（V，A）构成，其中V是点集合，表示公交站点位置；A是路段集合，每条路段的属性值aij表示定制公交在节点（i，j）间的运行时间.

1.3 目标函数与双边匹配合乘类型

1.3.1 目标函数

目标1：系统最优，最大化服务乘客数量，即考虑所有乘客的服务请求，最小化定制公交总的运营里程数；目标2：乘客最优，最大化乘客的满意度，衡量乘客满意度指标包括乘客等待时间最少、乘客出行费用最少；目标3：运营商最优，最大化运营商收益，用运营商总收益与总成本的差异衡量，即运营商的纯利润；最小化运营商等待时间.

1.3.2 双边匹配合乘类型

在定制公交运行过程中，可能会出现以下4种匹配情形，见表1.其中第4种较为常见，多个车辆接送多个乘客，乘客和定制公交车辆可以相互选择，此时需要采用双边匹配策略，使公交车辆分配与乘客的选择达到稳定状态.本文主要针对第4种“多辆车-多乘客”的情况进行优化匹配.

表1 4种匹配合乘类型

2 双边匹配的定制公交合乘优化模型

2.1 乘客的目标函数

2.2 运营商的目标函数

以最大化运营商的收益为目标函数建立模型，选用运营商接客成本和等客时间两个指标来量化运营商的效用.车辆k选择服务乘客p的效用函数为

2.3 约束条件

2.3.1 运营商乘客时间窗约束

由于定制公交服务乘客较多，必须保证车辆的准时性，故其等待乘客的时间应保持在可以接受范围

式中：P表示乘坐定制公交车的乘客集合，K表示参与运行的定制公交车的集合.

2.3.2 车容量约束

定制公交车辆k上的乘车人数，需要小于座位数

2.3.3 流量约束

保证每名乘客只被分配到一辆公交车

3 生成偏好列表

3.1 乘客的效用矩阵

根据式（1）得出乘客偏好列表.表2为乘客对车辆的效用矩阵，将表2结果进行排序，得到乘客对车辆的偏好列表（见表3），效用值越大，排序越靠前.

表2 乘客对车辆的效用矩阵

表3 乘客对车辆的偏好列表

3.2 车辆的效用矩阵

根据式（3）计算出车辆的偏好列表.表4为车辆对乘客的效用矩阵，将表4结果进行排序，得到车辆对乘客的偏好列表（见表5），效用值越大，排序越靠前.

表4 车辆对乘客的效用矩阵

表5 车辆对乘客的偏好列表

4 改进的H-R双边稳定匹配算法

采用改进的H-R双边匹配算法对问题进行求解，首先设定：①输入变量：每位乘客对每辆公交车的排序列表，每辆公交车对每位乘客的排序列表.需要强调的是，如果乘客出行时间不能与公交车进行匹配，则将效用赋予很小的值，即使最终结果匹配，也不能将两者进行匹配.因此，为了使乘客尽可能多的被服务，需要首先对乘客进行优先级排序.优先级排序的原则是对出行时间窗只能满足少量公交车的乘客给予优先匹配.②输出变量：满足稳定匹配的M对定制公交车和乘客.算法步骤如下.

步骤一：初始化.初始化所有乘客和车辆元素为未匹配状态，初始化配对集合S为空集；将乘客按照可以匹配车辆数进行优先级排序，可以匹配车辆数越少，优先级越高.

步骤二：第一轮匹配.第一轮每位乘客p都选择效用值最大的车辆k进行匹配，若车辆k没有与其他乘客进行匹配，则车辆接受乘客的请求；若车辆k已接受其他乘客p′请求服务，且车容量已达到最大限制，则车辆k会比较乘客p和p′，选择优先级高的乘客进行匹配，优先级相同的乘客将按照效用值大小进行匹配.未匹配成功的乘客将重新回到初始化列表中.

步骤三：循环N轮匹配.循环进行步骤二的匹配过程，直至所有乘客都有定制公交车匹配.

5 实例分析

为了验证定制公交匹配模型的稳定性，现以某市道路交通路网为研究对象.某市定制公交线路图和乘客实时需求信息请求点分别如图2-3所示.实例中根据公交公司提供的班车服务数据，将14条班车线路假定为定制公交线路，从400位乘客需求中随机抽取1/5数据作为乘客实时需求信息.定制公交需要偏移路线或者引导乘客到站乘车.实例中将参数标定结果为：定制公交车速为50 km/h，车辆运营成本6元/km，α1=0.6，α2=0.4，α3=0.7，α4=0.3.

图2 某市定制公交线路[10]

图3 乘客实时需求信息请求点[10]

通过考虑双边匹配的定制公交合乘优化方法计算，得到80位乘客与14辆定制公交车的匹配结果：乘客编号 7、23、28、34、39、45、55、58、79 共 9 名乘客效用函数值过小（车辆经过路线无法满足乘车的时间窗要求），将其作为无法服务的乘客剔除，车辆-乘客匹配结果如表6所示.

表6 车辆-乘客匹配结果

进一步分析模型的优越性，将本模型提出的考虑双边匹配的定制公交合乘优化方法（S1优化策略）与只考虑乘客提出需求时间顺序进行车辆匹配的方法（S2优化策略）进行对比，结果见表7.由表7可知：考虑双边匹配的定制公交合乘优化方法在保证运送乘客的前提下，可以有效缩短定制公交的运行距离，节省运营成本；同时也减少了乘客的等待时间，提高了服务水平和乘客满意度，并且也减少了未被服务乘客数量.其原因是某几条需求较高的线路由于车容量的限制，导致后续乘客需求无法被满足，所以在优化过程中，应优先考虑“瓶颈”乘客的需求首先被满足.

表7 两种策略下优化结果比较

6 结语

单纯考虑乘客选择定制公交的方案，会造成定制公交车辆运营成本增加和运行效率下降，因此在保证乘客和定制公交运营商双方的利益都得到满足的前提下，笔者提出一种基于改进H-R双边匹配的定制公交合乘优化方法.结果显示所提出的改进H-R双边匹配算法符合实时调度需求，最大化服务乘客的同时，避免了车辆的绕行或车容量达到饱和的情况发生，最终达到降低定制公交车辆运营成本的目的，为实时定制公交线路的开通和运营调度提供了理论支撑.