一种枢纽站接驳出租车合乘调度匹配方法

1.本发明属于交通运输技术领域，特别涉及一种枢纽站接驳出租车合乘调度匹配方法。


背景技术：

2.枢纽设计与建设是近年来城市规划、综合交通规划与交通建设的热点之一，但是部分城市的枢纽站公共交通接运服务并不理想，由于枢纽站接运公交系统发展较为缓慢，其提供的出行服务水平与枢纽站乘客的出行需求尚存在一定的差距。同时站内的通行能力、乘客数量的上升都意味着突发状况事故的风险也是在不断的增加。当轨道交通或地面公交服务缺失或不足时，出租车成为了主要的客运方式，特别是对于携带行李出行的乘客，出租车会更加成为首选的出行方式。然而跨市交通的运量较大，出行高峰时期会有大量的乘客有出行需求，传统出租车运营会由于服务效率较低、运力不足等问题从而导致高峰时段“打车难”问题，在枢纽站等人口聚集等地方由于出租车保有量无法满足出行需求。出租车合乘则能够满足大批量乘客的出行需求，但是在合乘出行中，部分乘客不能直接到达其目的地，产生绕路成本。
3.因此，如何合理的结合枢纽站出行用户的实际的出行地点，为乘客提供出租车合乘服务，并且需要考虑到最大化出租车司机的收益问题以及最小化乘客的合乘里程，是目前急需解决的问题，


技术实现要素：

4.为了解决枢纽站接驳出租车合乘调度匹配的问题，本发明提供了一种枢纽站接驳出租车合乘调度匹配方法，以出租车司机收益最大化及乘客合乘里程最小为目标，将出行目的地相似的乘客进行匹配合乘，通过寻找最优合乘乘客，为出租车提供可搭载出行的乘客。
5.为了实现上述目的，本发明提供一种枢纽站接驳出租车合乘调度匹配方法，包括如下步骤：
6.步骤1，以出租车司机收益最大化以及乘客合乘里程最小为目标，将枢纽站接驳调度匹配方法分解为乘客的出行目的地方向划分及乘客的目的地选取、乘客合乘出行成本分担与乘客合乘出行路径问题，同时考虑到不同时段下的票价、绕路比例、出行时间以及载客量的约束，从而得到枢纽站接驳出租车合乘调度模型；
7.步骤2，对乘客出行区域划分，利用dbscan聚类算法对乘客进行出行目的地特征选取，确定出行目的地类别相同或相近的乘客；
8.步骤3，利用非支配排序遗传算法对合乘路径规划问题进行求解，得到合乘出行的最优路径，计算出租车司机的收益以及乘客的合乘里程。
9.所述步骤1中，在枢纽站接驳出租车调度匹配方法中，建立出租车合乘最短路模型，以出租车司机收益最大化与乘客合乘里程最小为目标，假设条件包括：
10.1)乘客合乘出行的目的地随机分布在路网的各个节点中；
11.2)在道路网中，出租车以恒定的速度行驶；
12.3)仅考虑载客容量约束，不考虑乘客所携带的行李容量约束。
13.所述步骤1具体包括如下步骤：
14.步骤11，确定出租车的收益与乘客的合乘里程；
15.在接驳模型中，出租车的收益被表示为r1[0016][0017]
其中，r
ij
表示第i辆出租车搭载第j个乘客所获得的收益，i表示出租车，i＝1,2,
…
,m，j表示乘客，j＝1,2,
…
,n。
[0018][0019]
其中，为乘客j单独的出行距离，为乘客u单独的出行距离，di为出租车i在一次合乘出行中的总出行距离，ei为出租车i在一次出行中的总费用。
[0020]
在出行中，乘客的合乘里程被表示为c
[0021][0022]
其中，c
ij
为第i辆出租车中第j个乘客的合乘里程。
[0023]
步骤12，确定出行时段票价。
[0024]
出租车在市区中行驶时，行驶的时间段、里程不同，所收取的费用也不相同，出租车所收取费用被表示为ei[0025][0026]
其中，α为出租车基础价格，即生活中所说的起步价格，d
min
为出租车基础里程，即起步里程，d
most
为出租车的最大单向行驶里程，β为超过基础里程的收费费率，t1为出租车在行驶过程中的低速行驶时间/拥堵时间，γ为超过最大单向行驶里程后的额外费率，β3为燃油附加费。
[0027][0028]
其中，α1为白天行驶时基础价格，δ
day
为白天的时间段，δ
day
∈[5,23)，α2为夜间行驶基础价格，δ
night
为夜间时间段，δ
night
∈[23,5)。
[0029]
[0030]
其中，β1为白天行驶时收费费率，β2为夜间收费费率。
[0031]
步骤13，枢纽站接驳出租车调度匹配模型。
[0032]
乘客在枢纽站时，当乘客决定合乘时，乘客选择是否选择第i辆出租车出行，此时决策函数为k
ij
。
[0033][0034]
其中，k
ij
为合乘变量，当乘客j决定合乘并乘坐出租车i时，k
ij
＝1，否则，k
ij
＝0。
[0035]
在合乘出行中，乘客需先向系统提交订单，会产生预定费用r2。
[0036][0037]
其中，g为每位乘客的预约费用，pi为第i辆出租车内的乘客数量。
[0038]
在合乘出行的过程中，行驶成本r3与出行的距离di有关，即：
[0039][0040]
其中，τ为出租车的每公里行驶成本。
[0041]
总收益r为：
[0042]
r＝r1+r
2-r3[0043]
此时目标函数f为：
[0044][0045]
在出行过程中，乘客对于出行的时间有着要求，因此乘客出行时间约束被表示为：
[0046]
t
min
+t1≤t
ij
≤t
max
+t1[0047][0048]
其中，t
ij
是第i辆出租车中第j个乘客的出行时间，v
car
为车辆在道路中的行驶速度，t
min
为乘客j在理论上的最少出行时间，t
max
为乘客j在理论上的最多出行时间。
[0049][0050]
其中，v
max
为出租车在道路中行驶的规定最大运行速度
[0051][0052]
其中，v
min
为出租车在道路中规定行驶的最低速度。
[0053]
在合乘时，车内的乘客数量不能超过车辆的最大载客人数，即车内乘客数量约束为：
[0054]
p
min
≤pi≤p
max
[0055]
其中，最少的合乘乘客数量为p
min
，一般取值为0，即无乘客，最多可以有p
max
位乘
客，一般取值为4，即车辆满载。
[0056]
经过合乘后，司机的收益应当不低于接送单乘客出行时的收益，因此司机收益约束为：
[0057][0058]
其中，rj为出租车单独载乘客j的收入。
[0059]
在乘客利用出租车合乘出行的过程中，需要对乘客的绕行里程比例做出规定，防止出租车司机进行绕行从而影响到乘客的合乘体验，给定一个乘客对于合乘绕行的接受比例ωj，若出现超过绕行比例的情况，乘客可以拒绝搭乘车辆的请求。
[0060][0061]
ωj≤ω
max
[0062]
其中，乘客j在车i中的合乘里程，ω
max
为最大绕行比例
[0063]
在合乘中，每位乘客只能被一辆出租车所接受，因此访问约束被表示为：
[0064][0065]
其中，k
ij
被表示为出租车i接受乘客j，当乘客j被接受后，不能被其它车辆所接受。
[0066]
所述步骤2具体包括如下步骤：
[0067]
步骤21，划分出行方向
[0068]
以枢纽站为起点，以乘客的目的地为终点，对乘客的走向按照东北、东南、西北、西南四个方向进行划分，将每个方向的乘客分为一类，共计分为四类。
[0069]
步骤22，确定邻域半径与样本点
[0070]
给定数据集d＝{d(η)|η＝0,1,
…
,n}，对于任意点a
η
，计算点a
η
到集合d的子集d
η
＝{d1,d2,
…
,d
η-1
,d
η+1
,
…
,dn}中所有点之间的距离，距离按照从小到大的顺序排序，假设排序后的距离集合为d＝{d1,d2,
…
,d
η-1
,d
η+1
,
…
,dn}，则d
η
就被称为η-距离，表示点a
η
到所有其他点(除了a
η
点)之间距离第η短的距离。对待聚类集合中每个点a
η
都计算η-距离，最后得到所有点的η-距离集合d＝{d1,d2,
…
,dn}。
[0071]
步骤23，dbscan聚类
[0072]
dbscan的算法具体实施过程如下：
[0073]
step1.输入乘客出行目的地集合a＝{a1,a2,
…
,an}，根据η-距离设置邻域参数(eps,minpts)的值；
[0074]
step2.当样本集合中的任意一点邻域中至少包含着minpts个样本点，那么此点就是这个区域中的核心对象。核心点集合设置为ω，初始化核心点集合初始化聚类簇数h＝0，初始化访问集合γ＝a，划分簇集合
[0075]
step3.找到样本点ai的领域eps内的子样本集合na＝{ai}，如果子样本集合的样本个数满足|n
eps
(ai)|≥minpts，将样本点ai加入核心点集合ω＝ω∪{ai}；
[0076]
step4.如果核心点此时结束，否则转入step5；
[0077]
step5.在核心点集合ω中，随机选择一个核心点o，初始化当前类簇的核心点队列ω
cur
＝{o}，初始化类别序号n＝n+1，初始化当前类簇样本集合hn＝{o}，更新为访问样本集合γ＝γ-{o}
[0078]
step6.如果当前核心点队列则当前类簇hn生成完毕，更新类簇划分hn＝{h1,h2,
…
,hn}，更新核心点的集合ω＝ω-hn，此时转入step3，否则更新核心点的集合ω＝ω-hn；
[0079]
step7.在当前类簇核心点队列ω
cur
中取出一个核心点o'，通过邻域值eps找出所有的邻域子样本集合n
eps
(o')，令
△
＝n
eps
(o')∩γ，更新当前的类簇样本集合hn＝hn∪
△
，更新为访问样本集合γ＝γ
‑△
，更新ω
cur
＝ω
cur
∪(
△
∩ω)-{o'}，此时转入step5；
[0080]
step8.重复以上过程，直到类簇不再发生变化，确定类簇以及噪声点。
[0081]
确定不同类簇后，开始对不同类簇中的乘客进行出行路径分配。
[0082]
所述步骤3具体包括如下步骤：
[0083]
步骤31，计算位置之间距离
[0084]
在路网中，利用各个点的经纬度，通过计算可得到各个点之间的距离：
[0085][0086]
其中，dis表示点与点之间的距离，r是地球的半径，lat是纬度，lng是经度，
△
lat是两点间纬度差的平均值，
△
lng是两点间经度差的平均值。
[0087][0088][0089]
其中，lat1是第一个点的纬度，lat2是第二个点的纬度，lng1是第一个点的经度，lng2是第二个点的经度。
[0090]
步骤32，求解出行路径
[0091]
通过计算不同位置之间的距离，并确定目标区域的乘客数量后，利用带精英策略的非支配排序遗传算法对出行路径进行求解。
[0092]
步骤321，根据合乘的乘客数量配置相应数量的出租车，设定种群的最大规模数量n,最大的迭代次数g
max
，生成初始种群，将乘客乘车状态初始化，设置初始迭代次数g＝1。
[0093]
步骤322，导入乘客合乘的目的地结合及路网之间的出行距离数据，计算两个目标函数的值。
[0094]
步骤323，对于当前的种群中所有个体按照非支配关系进行排序，并且获得相应的适应度值。
[0095]
步骤324，对当前的种群进行遗传交叉操作，针对每一辆出租车，随机将其中的一位乘客与另外一辆出租车中的乘客进行交换。
[0096]
步骤325，对当前种群进行遗传变异操作，针对每一辆出租车，随机在其中重新生成一个新的解，从而产生子代种群。
[0097]
步骤326，将父代种群与子代种群进行合并，对新种群进行非支配排序，产生一系列非支配解集并计算拥挤度，从中选取出优良个体进入下一代的种群，此时，迭代次数g＝g
+1。
[0098]
步骤327，循环步骤322-步骤326，将迭代次数g与最大迭代次数g
max
判断比较，当g》g
max
时，则迭代终止，输出近似pareto解集。
[0099]
与现有技术相比，本发明的有益效果是：本发明能让出租车司机利用乘客合乘出行增加额外的收益，降低司机的工作强度，同时满足枢纽站中的乘客出行需求，避免乘客到站高峰时期车辆需求不足的困难。
[0100]
本发明提供了一种枢纽站接驳出租车合乘调度匹配方法，以出租车司机收益最大化及乘客合乘里程最小为目标，将出行目的地相近或顺路的乘客进行匹配合乘，通过寻找最优合乘乘客，为出租车提供可搭载出行的乘客，提高出租车司机的收益，同时有效提高了接运服务的质量，满足了枢纽乘客出行中多样化、多层次的需求。
附图说明
[0101]
图1为枢纽站接驳出租车调度匹配的方法流程图；
[0102]
图2为实施例研究区域示意图；
[0103]
图3路网示意图。
具体实施方式
[0104]
以下结合附图1、2和3，对本发明的结构作进一步描述。包括以下步骤：
[0105]
步骤1，以出租车司机收益最大化以及乘客合乘里程最小为目标，将枢纽站接驳调度匹配方法分解为乘客的出行目的地方向划分及乘客的目的地选取、乘客合乘出行成本分担与乘客合乘出行路径问题，同时考虑到不同时段下的票价、绕路比例、出行时间以及载客量的约束，从而得到枢纽站接驳出租车合乘调度模型；
[0106]
步骤2，对乘客进行出行区域划分，对具有相同出行特征的乘客利用dbscan聚类算法进行出行目的地选取，对于目的地在一定范围内的乘客进行选取，从而对此区域的乘客进行合乘出行匹配；
[0107]
步骤3，匹配完成后利用非支配排序遗传算法对合乘路径规划问题进行求解，得到合乘出行的最优路径，计算出租车司机的收益以及乘客的合乘里程。
[0108]
(1)数据的前期准备与处理:实施例应用于成都市高铁站。四川省成都市，为四川省的省会，是一个超大城市。城市总面积14335平方千米，常住人口2119.2万人。成都市包括9001个路口，四个高铁站，分别为成都东站、成都南站、成都西站、成都站。实施例的gps轨迹数据来源于成都市出租车公司，含有出租车动态轨迹信息，即出租车编号、车辆轨迹经度、纬度、时间以及载客状态。实施例中情景为中午高铁列车到达成都东站，前往西北区域的乘客人数最为密集，聚类结果所得9名乘客为一类簇，且分别前往不同的目的地。
[0109]
(2)模型中的参数设定：在出租车的日常行驶中，起步价格α为13元，起步里程d
min
为3km，最大里程d
most
为15km，白天每公里收费β为2.3元/km，拥堵时间t1为5min，夜间每公里收费γ为3.45元/km，最小行驶时间t
min
为10min，最大行驶时间t
most
为40min，最大行驶速度v
max
为70km/h，最小行驶速度v
min
为20km/h，车内乘客最小人数p
min
为0人，最多乘客人数p
max
为4人，预定费用为5元，τ每公里的行驶成本为0.45元，最大绕行比例ωj为2。
[0110]
(3)计算基础：遗传算法及dbscan算法均调用了numpy库编写，在python3.8平台上
运行。所有计算都在i7-10510u 1.80ghz处理器和16gb ram的计算机上进行。
[0111]
(4)结果
[0112]
经过计算，需要三辆出租车，a线路为乘客从高铁站出发，先到达4号乘客目的地，再到达6号乘客的目的地，最后将7号乘客送到目的地；b线路为从成都东站出发，先将12号乘客送到目的地，然后将9号乘客送到目的地，最后将14号乘客送到目的地；c线路为从成都东站出发，先将2号乘客送到目的地，再将17号乘客送到目的地，最后将16号乘客送到目的地。所有线路完成后，三辆出租车的总收入为305.2元，9位乘客的总合乘里程为96.2km。
[0113]
基于合乘的枢纽站调度接驳模型能让出租车司机增加极大收益，通过合乘提高了车辆的使用效率，一次的出行将多位乘客送到目的地，也使枢纽站出行乘客能够节约等待车辆时间，避免了乘客在是枢纽站内的滞留，极大的提升了枢纽站的转运效率。
[0114]
最后应说明的是：以上示例仅用以说明本发明而并非限制本发明所描述的技术方案；因此，尽管本说明书参照上述的示例对本发明已进行了详细的说明，但是，本领域的普通技术人员应当理解，仍然可以对本发明进行修改或等同替换；而一切不脱离发明的精神和范围的技术方案及其改进，其均应涵盖在本发明的权利要求范围当中。

技术特征：
1.一种枢纽站接驳出租车合乘调度匹配方法，其特征在于，包括如下步骤：步骤1，以出租车司机收益最大化以及乘客合乘里程最小为目标，将枢纽站接驳调度匹配方法分解为乘客的出行目的地方向划分及乘客的目的地选取、乘客合乘出行成本分担与乘客合乘出行路径问题，同时考虑到不同时段下的票价、绕路比例、出行时间以及载客量的约束，从而得到枢纽站接驳出租车合乘调度模型；步骤2，对乘客出行区域划分，利用dbscan聚类算法对乘客进行出行目的地特征选取，确定出行目的地类别相同或相近的乘客；步骤3，利用非支配排序遗传算法对合乘路径规划问题进行求解，得到合乘出行的最优路径，计算出租车司机的收益以及乘客的合乘里程；所述步骤1中，在枢纽站接驳出租车调度匹配方法中，建立出租车合乘最短路模型，以出租车司机收益最大化与乘客合乘里程最小为目标，假设条件包括：1)乘客合乘出行的目的地随机分布在路网的各个节点中；2)在道路网中，出租车以恒定的速度行驶；3)仅考虑载客容量约束，不考虑乘客所携带的行李容量约束；所述步骤1具体包括如下步骤：步骤11，确定出租车的收益与乘客的合乘里程；在接驳模型中，出租车的收益被表示为r1其中，r
ij
表示第i辆出租车搭载第j个乘客所获得的收益，i表示出租车，i＝1,2,
…
,m，j表示乘客，j＝1,2,
…
,n；其中，为乘客j单独的出行距离，为乘客u单独的出行距离，d
i
为出租车i在一次合乘出行中的总出行距离，e
i
为出租车i在一次出行中的总费用；在出行中，乘客的合乘里程被表示为c其中，c
ij
为第i辆出租车中第j个乘客的合乘里程；步骤12，确定出行时段票价；出租车在市区中行驶时，行驶的时间段、里程不同，所收取的费用也不相同，出租车所收取费用被表示为e
i
其中，α为出租车基础价格，即生活中所说的起步价格，d
min
为出租车基础里程，即起步
里程，d
most
为出租车的最大单向行驶里程，β为超过基础里程的收费费率，t1为出租车在行驶过程中的低速行驶时间/拥堵时间，γ为超过最大单向行驶里程后的额外费率，β3为燃油附加费；其中，α1为白天行驶时基础价格，δ
day
为白天的时间段，δ
day
∈[5,23)，α2为夜间行驶基础价格，δ
night
为夜间时间段，δ
night
∈[23,5)；其中，β1为白天行驶时收费费率，β2为夜间收费费率；步骤13，枢纽站接驳出租车调度匹配模型；乘客在枢纽站时，当乘客决定合乘时，乘客选择是否选择第i辆出租车出行，此时决策函数为k
ij
；其中，k
ij
为合乘变量，当乘客j决定合乘并乘坐出租车i时，k
ij
＝1，否则，k
ij
＝0；在合乘出行中，乘客需先向系统提交订单，会产生预定费用r2；其中，g为每位乘客的预约费用，p
i
为第i辆出租车内的乘客数量；在合乘出行的过程中，行驶成本r3与出行的距离d
i
有关，即：其中，τ为出租车的每公里行驶成本；总收益r为：r＝r1+r
2-r3此时目标函数f为：在出行过程中，乘客对于出行的时间有着要求，因此乘客出行时间约束被表示为：t
min
+t1≤t
ij
≤t
max
+t1其中，t
ij
是第i辆出租车中第j个乘客的出行时间，v
car
为车辆在道路中的行驶速度，t
min
为乘客j在理论上的最少出行时间，t
max
为乘客j在理论上的最多出行时间；其中，v
max
为出租车在道路中行驶的规定最大运行速度其中，v
min
为出租车在道路中规定行驶的最低速度；在合乘时，车内的乘客数量不能超过车辆的最大载客人数，即车内乘客数量约束为：p
min
≤p
i
≤p
max
其中，最少的合乘乘客数量为p
min
，取值为0，即无乘客，最多可以有p
max
位乘客，取值为4，即车辆满载；经过合乘后，司机的收益应当不低于接送单乘客出行时的收益，因此司机收益约束为：其中，r
j
为出租车单独载乘客j的收入；在乘客利用出租车合乘出行的过程中，需要对乘客的绕行里程比例做出规定，防止出租车司机进行绕行从而影响到乘客的合乘体验，给定一个乘客对于合乘绕行的接受比例ω
j
，若出现超过绕行比例的情况，乘客可以拒绝搭乘车辆的请求；ω
j
≤ω
max
其中，乘客j在车i中的合乘里程，ω
max
为最大绕行比例在合乘中，每位乘客只能被一辆出租车所接受，因此访问约束被表示为：其中，k
ij
被表示为出租车i接受乘客j，当乘客j被接受后，不能被其它车辆所接受；所述步骤2具体包括如下步骤：步骤21，划分出行方向以枢纽站为起点，以乘客的目的地为终点，对乘客的走向按照东北、东南、西北、西南四个方向进行划分，将每个方向的乘客分为一类，共计分为四类；步骤22，确定邻域半径与样本点给定数据集d＝{d(η)|η＝0,1,
…
,n}，对于任意点a
η
，计算点a
η
到集合d的子集d
η
＝{d1,d2,
…
,d
η-1
,d
η+1
,
…
,d
n
}中所有点之间的距离，距离按照从小到大的顺序排序，假设排序后的距离集合为d＝{d1,d2,
…
,d
η-1
,d
η+1
,
…
,d
n
}，则d
η
就被称为η-距离，表示点a
η
到所有其他点即除了a
η
点之间距离第η短的距离；对待聚类集合中每个点a
η
都计算η-距离，最后得到所有点的η-距离集合d＝{d1,d2,
…
,d
n
}；步骤23，dbscan聚类
dbscan的算法具体实施过程如下：step1.输入乘客出行目的地集合a＝{a1,a2,
…
,a
n
}，根据η-距离设置邻域参数(eps,minpts)的值；step2.当样本集合中的任意一点邻域中至少包含着minpts个样本点，那么此点就是这个区域中的核心对象；核心点集合设置为ω，初始化核心点集合初始化聚类簇数h＝0，初始化访问集合γ＝a，划分簇集合step3.找到样本点a
i
的领域eps内的子样本集合n
a
＝{a
i
}，如果子样本集合的样本个数满足|n
eps
(a
i
)|≥minpts，将样本点a
i
加入核心点集合ω＝ω∪{a
i
}；step4.如果核心点此时结束，否则转入step5；step5.在核心点集合ω中，随机选择一个核心点o，初始化当前类簇的核心点队列ω
cur
＝{o}，初始化类别序号n＝n+1，初始化当前类簇样本集合h
n
＝{o}，更新为访问样本集合γ＝γ-{o}step6.如果当前核心点队列则当前类簇h
n
生成完毕，更新类簇划分h
n
＝{h1,h2,
…
,h
n
}，更新核心点的集合ω＝ω-h
n
，此时转入step3，否则更新核心点的集合ω＝ω-h
n
；step7.在当前类簇核心点队列ω
cur
中取出一个核心点o'，通过邻域值eps找出所有的邻域子样本集合n
eps
(o')，令
△
＝n
eps
(o')∩γ，更新当前的类簇样本集合h
n
＝h
n
∪
△
，更新为访问样本集合γ＝γ
‑△
，更新ω
cur
＝ω
cur
∪(
△
∩ω)-{o'}，此时转入step5；step8.重复step2-7，直到类簇不再发生变化，确定类簇以及噪声点；确定不同类簇后，开始对不同类簇中的乘客进行出行路径分配；所述步骤3具体包括如下步骤：步骤31，计算位置之间距离在路网中，利用各个点的经纬度，通过计算可得到各个点之间的距离：其中，dis表示点与点之间的距离，r是地球的半径，lat是纬度，lng是经度，
△
lat是两点间纬度差的平均值，
△
lng是两点间经度差的平均值；lng是两点间经度差的平均值；其中，lat1是第一个点的纬度，lat2是第二个点的纬度，ln g1是第一个点的经度，ln g2是第二个点的经度；步骤32，求解出行路径通过计算不同位置之间的距离，并确定目标区域的乘客数量后，利用带精英策略的非支配排序遗传算法对出行路径进行求解；步骤321，根据合乘的乘客数量配置相应数量的出租车，设定种群的最大规模数量n,最大的迭代次数g
max
，生成初始种群，将乘客乘车状态初始化，设置初始迭代次数g＝1；步骤322，导入乘客合乘的目的地结合及路网之间的出行距离数据，计算两个目标函数
的值；步骤323，对于当前的种群中所有个体按照非支配关系进行排序，并且获得相应的适应度值；步骤324，对当前的种群进行遗传交叉操作，针对每一辆出租车，随机将其中的一位乘客与另外一辆出租车中的乘客进行交换；步骤325，对当前种群进行遗传变异操作，针对每一辆出租车，随机在其中重新生成一个新的解，从而产生子代种群；步骤326，将父代种群与子代种群进行合并，对新种群进行非支配排序，产生一系列非支配解集并计算拥挤度，从中选取出优良个体进入下一代的种群，此时，迭代次数g＝g+1；步骤327，循环步骤322-步骤326，将迭代次数g与最大迭代次数g
max
判断比较，当g>g
max
时，则迭代终止，输出近似pareto解集。

技术总结
本发明公开了一种枢纽站接驳出租车合乘调度匹配方法。本发明以出租车司机收益最大化以及乘客合乘里程最小为目标，将枢纽站接驳调度匹配方法分解为乘客的出行目的地方向划分及乘客的目的地选取、乘客合乘出行成本分担与乘客合乘出行路径问题，同时考虑到不同时段下的票价、绕路比例、出行时间以及载客量等约束，得到枢纽站接驳出租车合乘调度模型；然后利用DBSCAN聚类算法对乘客进行出行目的地特征选取，确定出行目的地类别相同或相近的乘客；最后利用非支配排序遗传算法对合乘路径规划问题进行求解，得到合乘出行的最优路径。本发明提高出租车司机的收益，同时提高了接运服务的质量，满足了枢纽乘客出行中多样化、多层次、个性化的需求。性化的需求。性化的需求。


技术研发人员：周雨阳 王旭涛 王沛钰
受保护的技术使用者：北京工业大学
技术研发日：2023.03.21
技术公布日：2023/7/25