基于个性化需求的拼车路径匹配算法研究

基于个性化需求的拼车路径匹配算法研究

郭 会1，王丽侠2

【摘 要】目前，多数城市都存在着打车难、交通拥挤、汽车造成的空气污染严重等问题，而拼车是解决上述问题的有效方法。拼车既可以缓解交通拥挤解决打车难的问题，又可以节能减排，利于环保。面向出租车拼车的个性化需求，提出相应的数学模型，将拼车问题模型化，同时设计一种基于乘客个性化需求的出租车路径匹配算法，规划最优的行车路线，为出租车司机和乘客推荐优化的行车路径和拼车对象。实验结果表明，提出的基于乘客个性化需求的拼车路径匹配算法不仅可以提高搭乘成功率，还明显降低了车辆的运行成本，有利于节能减排，合理利用资源。 【期刊名称】计算机技术与发展 【年(卷),期】2017(027)001 【总页数】4

【关键词】出租车拼车；路径匹配；个性化需求；环保

0 引 言

近年来，随着人们生活水平的不断提高，城市化进程日益加快，出租车行业飞速发展[1]。出租车在给人们生活带来便利的同时也存在空车率高、实载率低等现象，由此造成了城市交通拥堵、空气环境污染、交通资源浪费严重等问题[2-4]。“拼车”是提高出租车乘载率，缓解打车困难，解决交通拥堵的有效手段[5]。目前，国内外学者主要研究的是拼车的基本理论,如合乘的发展现状与趋势、组织模式等。对于合乘的许多方面都是定性的分析,丰富了车辆合乘理论[6-9]。虽然部分研究者对合乘做了定量分析[10],但对于合乘路径选择方面的研究,几乎

都是针对一对多组织模式建立的数学模型,且考虑的因素与约束比较单一。对于模型的计算,主要采用启发式算法与贪婪式算法来解决车辆的行驶路径问题[11]。 文中提出了一种基于乘客个性化需求的出租车拼车算法，该算法有效解决了不同乘客的拼车请求，提高了搭乘成功率，降低了车辆运行成本。

1 出租车匹配问题的描述及数学模型的建立

1.1 问题描述

文中研究的是两两乘客间拼车路径匹配的问题，它属于多乘客、带有固定时间窗口的合乘匹配问题。具体来说，就是在某个固定区域里，有多辆出租车在行驶，同时有多名乘客有不同的搭乘需求，乘客的出发点和目的地已经确定，并且在上、下车站点对应一个明确的服务时间窗口，乘客必须在规定的时间窗口之内搭乘[12]。文中假定出租车在某个固定的区域里均匀分布，出租车能在较短的时间内到达乘客上车地点。此时忽略出租车到达乘客起始点的时间，这样有利于简化问题。 1.2 问题形式化建模

为描述问题方便，引入以下符号：

查询请求集Q={q1,q2,…,qn}为所有有搭乘需要的乘客的查询请求。其中乘客的请求包括出发地点si，目的地ei，出发时间starti，能够接受的行驶时间runti，即qi={si,ei,starti,runti}。为描述方便，引入以下符号： S={s1,s2,…,sn}为所有乘客的出发地点集合。 E={e1,e2,…,en}为所有乘客的目的地地点集合。 Z=S∪E∪Z'

其中，Z'表示除上下车点之外，出租车经过的道路节点的集合；Z为所有位置

点的集合。 1.3 约束条件 1.3.1 时间约束

乘客能够拼车必须使得每个乘客在各自发出的请求起始时间前能够上车，故乘客间的起始时间差必须大于乘客间起始位置的最短时间mint，即起点约束： 目前乘客对服务要求越来越高，要求必须在规定的时间内到达目的地，即终点约束：

其中，real表示乘客n由起点到达终点的最短时间。 1.3.2 个性化约束

由于每个乘客对于拼车有不同的要求，有的乘客希望节省费用，因此希望能够找到跟他的路线几乎完全匹配的拼车对象，而有的乘客希望节省时间的同时有人能够跟他分担部分费用。基于该考虑，提出一种满足乘客个性化需求的拼车算法，通过控制参数C来满足不同的用户请求。其中，C为起点间距离与终点间距离的总和与该出租车所经过的所有距离的比值： C=distmax(n,m)

其中，)表示两个起点间的距离；)表示两个终点间的距离；distmax(n,m)表示拼车用户中最先上车的位置与最后下车的位置间的距离。

当C=0表示乘客希望找到路径完全匹配的拼车对象，C=0.5表示乘客希望找到至少66.66%路径匹配的拼车对象，C=1表示乘客希望至少50%路径匹配。 1.4 拼车目标

基于乘客个性化匹配问题可将目标分为两个： (1)满足乘客的个性化需求，且拼车距离最远。