基于匹配条件与调度的出租车合乘模型的研究与分析

朱易+马慧敏+刘青+粟宇秋

1.国防科学技术大学电子科学与工程学院，湖南长沙 410000

2.上海师范大学建筑工程学院，上海 201418

摘 要 为了解决当前打车难以及行车资源相对浪费的弊端，本文在深入考察当前打车环境的前提下，通过模拟车辆与客户之间的关系，建立了以最短路径为目标函数的合乘出租车调度模型，以出租车载客量以及乘客服务供求关系作为约束条件，利用禁忌搜索算法搜索最优路径，得到最优出租车合乘匹配方案。该过程对于解决打车难，兼顾司机与乘客的利益具有重要作用。

关键词 出租车；合乘；最优方案；禁忌算法

中图分类号 TP2 文献标识码 A 文章编号 2095-6363（2017）13-0018-01

在当前车流量日益增加，打车困难的时代背景下，对于出发地和目的地相近或者行程路线有重合的乘客来说，合乘无疑一种能够减轻费用成本的选择。对于出租车司机来说，合乘可以提高车辆的利用率，在较短的总行驶路程中获取更大的利益。对于交通网络车流量的管制来说，合乘可以有效控制在早晚高峰期时城市交通路网的拥堵情况。所以，在不大程度的影响乘客原有交通路线的前提下，合乘可以从多个方面改善城市交通的压力，给乘客和司机都带来一定程度的效益。那么，推广合乘业务便成为了当前出租车行业各个公司重点考虑的问题。

1 乘客出行路线类别

有打车意愿的乘客出行路线类别可分为相同出发点、到达点，相同出发点、不同到达点，不同出发点、相同到达点，不同出发点、不同到达点这4类，用图1描述所示。

2 合乘出租车调度模型的建立

合乘出租车是一种在基于原路线不变或者多乘客共线的前提下，以减少顾客打车等待时间以及减少出行费用，同时提高汽车资源的利用率，增加司机收入额新模式。本文所考虑的调度属于静态车辆调度范畴，即所有的乘客打车需求信息以及空驰出租车的位置信息在路径规划前都是已经确定已知的，不会再随着时间的变化而发生改变。针对本文的问题，我们建立合乘出租车调度模型规划合乘匹配乘客的最优行车路线，以合乘总路途最短为目标使得乘客和出租车司机双方都达到满意程度。

设i表示表示第i个乘客，k表示表示第k辆出租车，oi表示该乘客上车点坐标，ui表示该乘客下车点坐标，m表示出租车载客人数，N表示乘客的总数，M表示乘客的总数，0

以最短路径为目标函数，建立的调度模型如图所示：

由于车辆调度问题分类的复杂性，所以，目前没有普遍适用的求解算法。我们查阅文献得知，研究者认为，目前很多常见的关于车辆调度算法的研究并不能应用在合乘出租车这个领域。针对本文研究对象的特殊性，我们通过研究发现，禁忌搜索算法能在初步检索中寻找到局部最优解，而在进一步的搜索中可以有效的避开这些局部最优值，从而使得求解结果更加准确。因此，本文主要采用禁忌搜索算法来进行迭代计算。

本文使用禁忌搜索算法求解合乘车辆调度问题的步骤如下：

Step1：解的表示：本文中解采用自然数编码，一串自然数排列首位代表车的序号k，其他自然数表示乘客的上下车信息。若有3辆车，9位乘客，则1 5 3 2 3 5 2||2 4 9 6 6 9 4||3 1 7 8 8 1 7表示出租车1、2、3的线路分别为如图所示：

Step2：解的评价方法：对于解的评价方法，首先解应满足问题的约束条件，其次，计算该解所生成的目标函数值，目标函数值越理想且越符合问题实际情况，则该解更准确。本文中采用在全程14中乘客的上下车的表示方法产生的解所确定的车辆路径方案，应满足每个乘客仅由一辆出租车提供服务的约束，同时满足出租车的载客数小于3人的约束条件。除此之外，满足点缓冲合乘匹配条件和路径匹配度计算结果更高的乘客组的路径所在的解更优。

Step3：邻域操作方法：禁忌搜索算法是一种基于邻域搜索技术的算法，确定邻域操作方法是构造该算法的一个重要步骤。在本文中，我们采用两两交换法实施邻域操作，该方法是指随机选择解中的两个元素，并交换其值的邻域操作方法。

Step4：禁忌对象的确定：禁忌对象是指禁忌表中被禁的那些局部最优解，本文选取满足第一部分合乘匹配条件的解作为最优解。我们将每次迭代得到的最好解作为禁忌对象放入禁忌表中。

Step5：候选集合的选择：本文将从当前解的邻域中随机选择若干个邻居作为候选集合。

Step6：藐视准则的判断：为了防止优良解的遗失，当某个禁忌候选解的适配值优于当前全局最优值，解禁此候选解为当前解和当前全局最优解。

Step7：终止条件的确定：本文采用迭代指定次数的终止准则。

3 结论

本文建立了以最短路径为目标函数的合乘出租车调度模型，以出租车载客量以及乘客服务供求关系作为约束条件，利用禁忌搜索算法搜索最优路径，得到最优出租车合乘匹配方案。

参考文献

[1]张瑾.出租车拼车问题研究及其服务系统设计实现[D].兰州：兰州交通大学，2009.

[2]张亦楠.出租车合乘模式下的智能匹配问题的研究与实现[D].青岛：中国海洋大学，2014.

[3]翟泳，杨金梁，连剑.合乘出行信息检索的路径匹配算法[J].交通与计算机，2007，1（25）：27-30.

[4]刘佳.出租车合乘方式及定价模型优化研究[D].重庆：重庆交通大学，2016.