基于模糊减法聚类的出租车合乘业务方案设计

朱瑞林 刘志鹏

摘要：运用模糊减法聚类算法对出租车合乘业务方案进行设计。乘客初末位置以核心区域为准则进行内集和外集的划分，对内集中的乘客选择离核心区域最近的空驰出租车选择3人合乘匹配的方案，外集中的乘客对其初末位置进行合乘适用度匹配之后选择2人合乘或1人合乘的方案，对不同的合乘方案分别设计相应的计费标准。结果表明，该方案不但能减少乘客的出行费用，也能增加出租车司机的收入。

关键词：合乘业务;模糊聚类;内集;外集;计费标准

中图分类号：TP391 文献标识码：A 文章编号：1007-9416（2018）11-0122-02

0 引言

出租車合乘业务是指乘客出行时按路线相同或相近原则，多人共同乘坐同一辆车。出租车业务系统则根据合乘乘客数量、乘车时长及实际乘车路线等情况，分别计算出每位乘客所需要费用。设计合乘业务系统目的在于通过控制运营车辆总数提高合乘的效率以缓解交通压力和乘客打车难的困境。肖强等[1]通过对出租车的行驶路线进行模糊聚类分析，对合乘乘客与出租车进行合乘模糊识别的方式来提高合乘几率。胡继华[2]等将出租车司机的路径选择经验融入到路径规划算法中，可以提高乘客的出行效率。本文根据乘客分布和车辆位置信息对合乘方式进行了深入研究，综合考虑了乘客分布密度的区域划分、乘客与出租车的匹配过程、车费计算等多方面因素对合乘业务的影响。

1 问题描述

针对乘客与出租车司机之间的合乘匹配问题，需要综合考虑乘客出发位置、乘客的目的地位置以及空乘出租车的位置之间的距离信息，根据三者位置信息形成的聚类中心区域，求解出租车与乘客目的地之间的最优路径。对分布在不同类中心区域的乘客应当设计合理的行车路线，应考虑到乘客从出发点到目的地所需的时间以及所需的出租车数量最少，还要同时兼顾乘客出行费用与出租车司机的收益，也就是出租车出乘的时候尽量选择三人满座的情况。

2 合乘方案的数学模型建立

本文针对出租车与乘客合乘匹配问题，以多个起点至多个目的地的运营方式为出发点，提出聚类核心区域模块划分的解决思路。根据乘客的出发点、目的地以及空驰出租车三者位置信息的分布情况，对其进行基于位置信息密度的模糊聚类分析。

2.1 基于位置信息密度的模糊减法聚类

基于位置信息密度的模糊减法聚类方法对出租车与乘客的匹配进行分析。对乘客的出发位置、目的地位置以及空驰出租车位置信息进行聚类，得出数据集中每一个数据点的密度。在其中选择密度值最大的数据点作为第一个中心点位置，通过迭代计算法求出剩下数据点的位置密度，根据需要选择最佳的密度阈值，由大于阈值的所对应位置信息，形成若干聚类中心，不断地优化选取模糊隶属度，得到模糊影响半径，通过选取影响半径可得到若干个区域。若区域之间出现了重叠，取区域的合集并称之为核心区域。分析乘客的出发位置和目的地信息，若两者都处于核心区域内则将该乘客划入内集中，其他乘客则划入外集中。

2.2 乘客与出租车的分配过程分析

根据乘客出发位置和目的地位置信息是否处于核心区域进行合乘人员的分配，在选取模糊影响半径的时候，尽量使内集中的乘客密度最大，增加合乘的几率，直接采取3人合乘的方案，而外集中的乘客采用2人合乘或者1人独乘的方案。

2.2.1 内集乘客的合乘分配方案

使用模糊聚类法对内外集确定后，按照乘客的出发点与终点都在内集区域的准则，对处于内集中的乘客按照3人合乘的模式，确保内集中的乘客人数为3的整数倍。若人数不是3的整数倍时，按照距离核心区域最近的准则，从外集中选择1-2人归入到内集中构成3的整数倍。在空驰出租车集中依次选取离核心区域最近的出租车，确定需要合乘的出租车之后，从内集中选择距离该出租车最近的3个乘客进行合乘。

2.2.2 外集乘客的合乘分配方案

在经过内集乘客人员的合乘匹配之后，剩下乘客的初止位置不都是分布于内集中，且出发点位置和目的地位置的分布都很稀疏，乘客之间的合乘几率比较低。采用出发点位置和目的地位置相近的原则进行最多2人的合乘匹配方案。当合乘适应度大于某一阈值时选择合乘。而合乘适应度由两乘客起点与目的地邻近度决定，其中 ，，其中表示乘客所处的位置坐标。规定自己与自己的合乘适应度为0;以距离最近原则选择空驰出租车进行乘客的合乘匹配。

2.3 出租车合乘方案的计费标准

出租车合乘方案的的计费标准设计时应包含起步价和里程单价两个计费项目[3]，起步价p0元/2公里，超过2公里，按p1元/公里计价[4]。设计3人合乘计费方案如下：通过选取合适的聚类半径，可知核心区域乘客之间的起止位置都在内集中，直接选用“一口价”的定价计费模式。3人合乘的费用为：，D为核心区域半径。对外集中的乘客采用“相同起点”的计费模式，假定第1人的行程L1大于第2人的行程L2，则2人合乘计费方案分别为：， ，当外集中的乘客只能独乘时，据行程L采用独立乘车计费方案为。

3 数据处理与实验结果分析

为验证该出租车合乘方案的可行性，收集了某一城市某一时刻部分乘客的打车需求及空驰出租车位置信息如表1所示，采用模糊减法聚类算法进行实验。

通过Matlab对数据进行分析实验，实验结果表明：3人合乘人数为270人，90台车;2人合乘人数为666人，333台车，1人独立乘车人数为65人，65台车;共计所需出租车为488台，平均等待时间为503米。使用上述计费模型得出乘客支付费用在3人合乘最少，而此时出租车司机收益最高（见表2）。

4 结语

本文在多个起点至多个目的地的出租车合乘业务模型进行了研究，该方案充分考虑了乘客的等待时间、乘车费用以及所需空驰出租车数量、司机收益[5]等情况下的合乘。但仍存在一些不足之处，在人与车进行匹配时缺少了灵活性，该方案中的计费模型还有待完善和改进。

參考文献

[1]肖强，何瑞春，张薇，等.基于模糊聚类和识别的出租车合乘算法研究[J].交通运输系统工程与信息，2014（5）：119-125.

[2]胡继华，黄泽，邓俊，等.融合出租车驾驶经验的层次路径规划方法[J].交通运输系统工程与信息，2013， 13（1）：185-192.

[3]周和平.出租车合乘路径选择与费率优化模型[J].长沙理工大学学报（自然科学版），2011（01）：20-24.

[4]洪麟琳.基于合乘模式的出租车定价研究[D].哈尔滨工业大学，2012.

[5]邵增珍，王洪国，刘弘等.车辆合乘匹配问题中服务需求分派算法研究[J].清华大学学报（自然科学版），2013，（2）：252-258.

Design of Taxi Mixing Business Plan Based on Fuzzy Subtractive Clustering

ZHU Rui-lin1， LIU Zhi-peng2

（1.Chulan Experimental School， Changde City， Hunan Province， Changde Hunan   415000;

2.Changde Meteorological Bureau of Hunan Province， Changde Hunan  415000）

Abstract：The fuzzy subtraction clustering algorithm is used to design the taxi busning business plan. The passengers' initial position is divided into inner and outer sets based on the core area. The inner passengers choose the closest air-conditioned taxi from the core area to select a three-person matching plan. After the location is matched and the fitness is matched， the scheme of selecting two people or one person is selected， and the corresponding charging standards are respectively designed for different multiplication schemes. The results show that the program can not only reduce passenger travel expenses， but also increase the income of taxi drivers.

Key words：multiplication service; fuzzy clustering; inner set; outer set; billing standard