一种拼车调度方法

1.本发明涉及智能交通技术领域，特别是涉及一种拼车调度方法。


背景技术：

2.拼车已经成为我们日常生活中重要的交通方式，有助于减轻空气污染和缓解交通阻塞；顺风车是一种基于私家车拼车的共享出行方式，顺风车车主以满足自身出行需求为前提，与行程相似的乘客共同分摊出行成本；现有的拼车调度方法往往只能实现简单的拼车调度匹配和定价，难以满足多种复杂的需求和场景。


技术实现要素：

3.本发明提供一种拼车调度方法，考虑了候选司机和乘客双方多样的偏好需求(出发地坐标、目的地坐标、最大可容忍绕路比率、出价、要价)，保证候选司机的预期收入，节省乘客的乘车费用。
4.为实现上述效果，本发明的技术方案如下：
5.一种拼车调度方法，包括以下步骤：
6.步骤1：分别收集候选司机和乘客的出行信息，构建每个乘客的候选司机集合；
7.其中，定义候选司机为mi,i∈{1,2,...,m}，候选司机的集合为m＝{m1,m2,...,mm}，其中m为候选司机的数量；每个候选司机的行程其中分别表示候选司机的出发地坐标、目的地坐标、最大可容忍绕路比率、可提供的座位数量；定义乘客为nj,j∈{1,2,...,n}，乘客的集合为其中n为乘客的数量；每个乘客的行程其中分别表示乘客的出发地坐标、目的地坐标、最大可容忍等待时间、最大可容忍绕路比率、所需座位数量；
8.步骤2：将乘客依据近距离优先规则划分为多个联盟，构建初始联盟结构；
9.步骤3：构建每个联盟的出价和候选司机的要价；
10.步骤4：根据定价策略确定胜出者和失败者，并计算乘客总效用；
11.步骤5：对每位乘客执行切换操作调整乘客的分配，，判断切换操作是否满足切换规则，若不满足，保持联盟结构不变；若满足，更新联盟结构；
12.步骤6：判断当前联盟结构是否满足稳定性，若不满足，返回步骤5；若满足，结束流程，完成拼车调度。
13.进一步的，步骤1中构建每个乘客的候选司机集合具体步骤如下：
14.步骤1.1：遍历乘客集合对于乘客集合中的每个乘客，依次遍历候选司机集合m，对于每一个候选司机，判断候选司机与乘客能否匹配，具体步骤如下：
15.步骤1.1.1：判断乘客是否在候选司机的接载范围其中表示候选司机出发地和乘客出发地之间的欧氏距离，r表示候选司机的接载半径，若乘客不在候选司机接载范围内，则不考虑该候选司机；
16.步骤1.1.2：判断候选司机能否为乘客提供所需的座位数量若候选司机可提供的座位数量不足，则不考虑该候选司机；
17.步骤1.1.3：将乘客的出发地和目的地添加到候选司机当前的路径序列，生成最优路径，计算乘客的实际等待时间μj、实际行驶距离lj以及候选司机的实际行驶距离li；
18.步骤1.1.4：判断乘客的等待时间μj约束是否满足若不满足，则不考虑该候选司机；
19.步骤1.1.5：判断乘客的绕路约束是否满足其中为乘客的行程公里数，若不满足，则不考虑该候选司机；
20.步骤1.1.6：判断候选司机的绕路约束是否满足其中为候选司机行程公里数，若不满足，则不考虑该候选司机；
21.步骤1.2：将同时满足以上条件的候选司机添加到乘客对应的候选司机集合中，得到每个乘客的候选司机集合。
22.进一步的，步骤2中，将分配给同一候选司机的乘客定义为一个联盟ci,i∈{1,
…
,m}，联盟ci表示分配给候选司机mi的一组乘客，联盟和候选司机之间是一一对应的关系；没有匹配候选司机的一组乘客用联盟c0表示；联盟c0、联盟ci组成一个联盟结构联盟结构中包含所有的乘客并且任意两个联盟的交集为空集
23.进一步的，步骤2中构建初始联盟结构，具体步骤如下：
24.步骤2.1：遍历候选司机集合，对于每个候选司机，创建一个与候选司机对应的初始联盟，即空集；
25.步骤2.2：遍历乘客集合，对于每个乘客，在乘客对应的候选司机集合中，根据近距离优先规则，找出距离乘客出发地最近的候选司机，将乘客添加到该候选司机对应的联盟中。
26.进一步的，步骤3具体为：
27.步骤3.1：根据乘客的出发地和目的地得到乘客的行程公里数和行程时间并计算乘客的预估费用其中，φ表示为每公里费率，表示为每分钟费率；将乘客的预估费用作为乘客的出价
28.步骤3.2：计算联盟中乘客的最低出价联盟的出价为|ci|表示联盟ci中乘客的数量；
29.步骤3.3：根据候选司机的出发地和目的地得到候选司机的行程公里数和行程时间并计算候选司机的预期收入其中，ρ表示为每公里的燃料成本，σ表示为每分钟的人工成本；将候选司机的预期收入作为候选司机的要价
30.进一步的，步骤4的具体步骤如下：
31.步骤4.1：按照联盟中乘客的最低出价从高到低对联盟排序，得到一个有序的联盟集合
32.步骤4.2：遍历联盟集合c，根据定价策略确定胜出者和失败者；
33.步骤4.3：遍历完成后，计算乘客总效用
34.进一步的，步骤4.2具体过程如下：
35.步骤4.2.1：对于每一个联盟判断联盟的出价是否满足对应候选司机的要价其中κ为拼车平台收取的手续费率，用于维护和运营平台；若满足，执行步骤4.2.2；若不满足，执行步骤4.2.4；
36.步骤4.2.2：计算判断是否满足条件若满足，执行步骤4.2.3；若不满足，执行步骤4.2.4；
37.步骤4.2.3：将联盟中的乘客和对应的候选司机判定为胜出者，联盟中每个乘客需支付的费用为计算乘客的效用联盟对应候选司机mi的收入为
38.步骤4.2.4：将联盟中的乘客和对应的候选司机判定为失败者，联盟中每个乘客需支付的费用为乘客的效用联盟对应候选司机mi的收入为p
is
＝0。
39.进一步的，步骤5中，切换操作是一种改变联盟结构的手段，是指在一个联盟结构中，将一位乘客nj从当前联盟ci移除并添加到另一个联盟从而得到一个新的联盟结构定义切换规则为对一位乘客执行切换操作能够提高乘客总效用。
40.进一步的，步骤5中对每位乘客执行切换操作调整乘客分配，具体步骤如下：步骤5.1：记录当前的联盟结构以及乘客总效用；步骤5.2：遍历乘客对应的候选司机集合，执行步骤1.1.2-1.1.6判断乘客能否加入与候选司机对应的联盟中，直到找到一个该乘客能加入的新联盟；步骤5.3：若新联盟存在，则执行步骤5.4；若新联盟不存在，则进入下一次循环，判断下一个乘客；步骤5.4：将乘客从当前联盟移除，添加到新联盟中，形成新的联盟结构；步骤5.5：在新的联盟结构下执行步骤3和步骤4，得到新的乘客总效用；步骤5.6：若新的乘客总效用，则更新联盟结构；若不满足，则保持联盟结构不变。
47.进一步的，步骤6中，联盟结构的稳定性是指不能再通过切换操作改变联盟结构来
提高乘客总效用时，联盟结构是稳定的；判断联盟结构是否稳定的具体步骤如下：
48.步骤6.1：记录在当前联盟结构下的乘客总效用u；
49.步骤6.2：执行步骤5，得到最后一次迭代的新的乘客总效用u'；
50.步骤6.3：若最后一次迭代的新的乘客总效用u'》u，则联盟结构已更新，返回步骤6.1；若最后一次迭代的新的乘客总效用u'＝u，则表明当前联盟结构是稳定的，将在当前联盟结构下的匹配与定价结果作为最终结果，完成拼车调度。
51.与现有技术相比，本发明技术方案的有益效果是：
52.本发明充分考虑了候选司机和乘客双方多样的偏好需求(出发地坐标、目的地坐标、最大可容忍绕路比率、可提供的座位数量或所需座位数量)，在拼车平台的协调下进行实时匹配；不仅可以保证候选司机的预期收入，还可以在保证服务质量的前提下节省乘客的乘车费用，从而激励候选司机和乘客积极参与拼车。
附图说明
53.附图仅用于示例性说明，不能理解为对本发明的限制；为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。
54.图1为本发明实施例的方法流程图；
55.图2为本发明实施例的系统结构图；
56.图3a为本发明实施例的第一拼车路线图；
57.图3b为本发明实施例的第二拼车路线图。
具体实施方式
58.为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都是本发明保护的范围。
59.实施例1
60.为了便于理解，请参阅图1，本发明提供的一种拼车调度方法的一个实施例，包括以下步骤：
61.步骤1：建立拼车平台，分别收集候选司机和乘客的出行信息，构建每个乘客的候选司机集合；
62.其中，定义候选司机为mi,i∈{1,2,...,m}，候选司机的集合为其中m为候选司机的数量；每个候选司机的行程其中分别表示候选司机的出发地坐标、目的地坐标、最大可容忍绕路比率、可提供的座位数量和要价；定义乘客为nj,j∈{1,2,...,n}，乘客的集合为其中n为乘客的数量；每个乘客的行程其中分别表示乘客的出发地坐标、目的地坐标、最大可容忍等待时间、最大可容忍绕路比率、所需座位数量和
出价。
63.步骤2：将乘客依据近距离优先规则划分为多个联盟，构建初始联盟结构；
64.步骤3：构建每个联盟的出价和候选司机的要价；
65.步骤4：根据定价策略确定胜出者和失败者，并计算乘客总效用；
66.步骤5：对每位乘客执行切换操作调整乘客的分配，判断切换操作是否满足切换规则，若不满足，保持联盟结构不变；若满足，更新联盟结构；
67.步骤6：判断当前联盟结构是否满足稳定性，若不满足，返回步骤5；若满足，结束流程，完成拼车调度。
68.本发明有以下优势：(1)相较于职业出租车司机，本发明所涉方法利用私家车司机拥有比出租车司机更多的议价空间特性，激励乘客参与拼车；对于出租车司机，其定价往往依据时长与里程，而利用本发明所涉方法，可将私家车司机的要价拼车部分费用，给予先序上车乘客因遭遇道路交通拥堵、绕路而产生的时长费补偿，从而吸引乘客参与拼车出行；(2)相较于传统职业出租车司机接载多位拼车乘客，本发明所涉方法可以更好地保障司机的效用或者利益；当私家车拼车服务匹配乘客、司机时，接载后序乘客过程中乘车时间若超过了前序乘客地最大可容忍延迟时间，则给予乘客补偿，以提高拼车成功率，并保障司机的收益；本发明所涉方法可在保障私家车司机预期收入、乘客预算、司机与乘客绕路延迟需求，以及乘客等待乘车时间等复杂实际条件的基础上，提高拼车效率，优化乘客的费用。
69.实施例2
70.具体地，在实施例1的基础上，结合具体的实施例子对方案进行说明，进一步体现本方案的技术效果。具体为：
71.如图2所示，本发明可部署在远程服务器上，首先，乘客和候选司机双方分别提交出行的乘客信息、司机信息，乘客信息、司机信息对应图2中的
①
；乘客信息：出发地坐标、目的地坐标、最大可容忍等待时间、最大可容忍绕路比率、所需座位数量和出价；司机信息：出发地坐标、目的地坐标、最大可容忍绕路比率、可提供的座位数量和要价；然后，应用(联盟博弈)拍卖算法，在得到最优的候选司机乘客匹配的情况下，拼车平台(拍卖师)初始化后结合新的联盟结构、(联盟博弈)拍卖算法，根据定价策略计算候选司机的收入与共乘乘客的分摊费用并给出候选司机行驶的最优拼车路线(即按照最短路径进行遍历得到最优行驶接驳路径)，对应图2中的
②
；最后，司机端返回匹配结构和司机的收入，乘客端返回匹配结果和共乘乘客的分摊费用，对应图2中的
③
。乘客端app、候选司机端app均和拼车平台通过通信接口连接。
72.具体的，步骤1中构建每个乘客的候选司机集合具体步骤如下：
73.步骤1.1：遍历乘客集合对于乘客集合中的每个乘客，依次遍历候选司机集合m，对于每一个候选司机，判断候选司机与乘客能否匹配，具体步骤如下：
74.步骤1.1.1：判断乘客是否在候选司机的接载范围其中表示候选司机出发地和乘客出发地之间的欧氏距离，r表示候选司机的接载半径，若乘客不在候选司机接载范围内，则不考虑该候选司机；
75.在一个具体的实施例中，假设候选司机接载半径r＝5km，车辆行驶速度为ν＝48km/h；结果如表3所示：
76.表3乘客的候选司机集合表
77.乘客候选司机集合n1{m1,m2}n2{m1,m2,m3}n3{m1,m2}n4{m1,m2}n5{m1,m2,m3}
78.步骤1.1.2：判断候选司机能否为乘客提供所需的座位数量若候选司机可提供的座位数量不足，则不考虑该候选司机；
79.步骤1.1.3：将乘客的出发地和目的地添加到候选司机当前的路径序列，生成最优路径，计算乘客的实际等待时间μj、实际行驶距离lj以及候选司机的实际行驶距离li；
80.步骤1.1.4：判断乘客的等待时间μj约束是否满足若不满足，则不考虑该候选司机；
81.步骤1.1.5：判断乘客的绕路约束是否满足其中为乘客的行程公里数，若不满足，则不考虑该候选司机；
82.步骤1.1.6：判断候选司机的绕路约束是否满足其中为候选司机行程公里数，若不满足，则不考虑该候选司机；
83.步骤1.2：将同时满足以上条件的候选司机添加到乘客对应的候选司机集合中，得到每个乘客的候选司机集合。
84.在一个具体的实施例中，如图3所示，给定候选司机和乘客的出行信息如表1和表2所示：
85.表1候选司机信息表
[0086][0087]
表2乘客信息表
[0088][0089]
具体的，步骤2中，将分配给同一候选司机的乘客定义为一个联盟ci,i∈{1,
…
,m}，联盟ci表示分配给候选司机mi的一组乘客，联盟和候选司机之间是一一对应的关系；没有匹配候选司机的一组乘客用联盟c0表示；联盟c0[0090]
、联盟ci组成一个联盟结构联盟结构中包含所有的乘客并且任意两个联盟的交集为空集
[0091]
具体的，步骤2中构建初始联盟结构，具体步骤如下：
[0092]
步骤2.1：遍历候选司机集合，对于每个候选司机，创建一个与候选司机对应的初始联盟，即空集；初始化每个候选司机对应的联盟
[0093]
步骤2.2：乘客出发地与每个候选司机出发地之间的距离如表4所示，遍历乘客集合，对于每个乘客，在乘客对应的候选司机集合中，根据近距离优先规则，找出距离乘客出发地最近的候选司机，将乘客添加到该候选司机对应的联盟中；形成初始联盟结构第一拼车路线图如图3a所示；
[0094]
表4乘客出发地与候选司机出发地之间的距离表
[0095][0096]
具体的，步骤3具体为：
[0097]
步骤3.1：根据乘客的出发地和目的地得到乘客的行程公里数和行程时间并计算乘客的预估费用其中，φ表示为每公里费率(单位为元/公里)，表示为每分钟费率(单位为元/分钟)；将乘客的预估费用作为乘客的出价
[0098]
假设φ＝2.5(单位为元/公里)，(单位为元/分钟)；乘客的出价计算结果如表5所示：
[0099]
表5乘客出价的计算结果
[0100][0101]
步骤3.2：计算联盟中乘客的最低出价联盟的出价为|ci|表示联盟ci中乘客的数量；
[0102]
联盟出价计算结果如表6所示：
[0103]
表6联盟出价的计算结果
[0104][0105]
步骤3.3：根据候选司机的出发地和目的地得到候选司机的行程公里数和行程时间并计算候选司机的预期收入其中，ρ表示为每公里的燃料成本(单位为元/公里)，σ表示为每分钟的人工成本(单位为元/分钟)；将候选司机的预期收入作为候选司机的要价
[0106]
假设ρ＝2(单位为元/公里)，σ＝0.3(单位为元/分钟)；将候选司机的预期收入作为候选司机要价候选司机要价计算结果如表7所示：
[0107]
表7候选司机要价的计算结果
[0108][0109]
具体的，步骤4的具体步骤如下：
[0110]
步骤4.1：按照联盟中乘客的最低出价从高到低对联盟排序，得到一个有序的联盟集合满足
[0111]
步骤4.2：遍历联盟集合c，根据定价策略确定胜出者和失败者；具体过程如下：
[0112]
步骤4.2.1：对于每一个联盟判断联盟的出价是否满足对应候选司机的要价)其中κ为拼车平台收取的手续费率，用于维护和运营平台，取值范围一般在5％～20％；若满足，执行步骤4.2.2；若不满足，执行步骤4.2.4；
[0113]
步骤4.2.2：计算判断是否满足条件若满足，执行步骤4.2.3；若不满足，执行步骤4.2.4；其中，表示在满足司机要价条件下，联盟中每位乘客需要支付的最低费用；
[0114]
步骤4.2.3：将联盟中的乘客和对应的候选司机判定为胜出者，联盟中每个乘客需支付的费用为计算乘客的效用联盟对应候选司机mi的收入为
[0115]
步骤4.2.4：将联盟中的乘客和对应的候选司机判定为失败者，联盟中每个乘客需支付的费用为乘客的效用联盟对应候选司机mi的收入为p
is
＝0。
[0116]
在具体实施过程中，假设平台的手续费率κ＝0，对于联盟c1，计算得到执行步骤4.2.4，将联盟中的乘客和对应的候选司机判定为失败者，联盟c1中的乘客需支付费用为乘客效用联盟c1对应候选司机m1的收入为p
1s
＝0；
[0117]
对于联盟c2，计算得到计算执行步骤4.2.3，将联盟中的乘客和对应的
候选司机判定为胜出者，联盟c2中每个乘客需支付费用为计算乘客的效用效用联盟c2对应候选司机m2的收入为
[0118]
对于联盟c3，计算得到因为联盟c3是最后一个，后面没有其他执行步骤4.2.4，将联盟中的乘客和对应的候选司机判定为失败者，联盟c3中的乘客需支付费用为乘客效用联盟c3对应候选司机m3的收入为
[0119]
步骤4.3：遍历完成后，计算乘客总效用为：
[0120][0121]
具体的，步骤5中，切换操作是一种改变联盟结构的手段，是指在一个联盟结构中，将一位乘客nj从当前联盟ci移除并添加到另一个联盟从而得到一个新的联盟结构定义切换规则为对一位乘客执行切换操作能够提高乘客总效用；对每位乘客执行切换操作调整乘客分配具体步骤如下：
[0122]
步骤5.1：记录当前的联盟结构以及乘客总效用u＝＝10.19；
[0123]
步骤5.2：遍历乘客n5对应的候选司机集合{m1,m2,m3}，执行步骤1.1.2-1.1.6判断乘客能否加入与候选司机对应的联盟中，直到找到一个该乘客能加入的新联盟c1；
[0124]
步骤5.3：若新联盟c
′i存在，则执行步骤5.4；若新联盟c
′i不存在，则进入下一次循环，判断下一个乘客；将乘客n5从当前联盟c3移除，添加到新联盟c1中，形成新的联盟结构第二拼车路线图如图3b所示；
[0125]
步骤5.4：将乘客从当前联盟ci移除，添加到新联盟c
′i中，形成新的联盟结构
[0126]
步骤5.5：在新的联盟结构下执行步骤3和步骤4，得到新的乘客总效用u'；计算过程如表8所示：
[0127]
表8在新的联盟结构下执行步骤3和步骤4的计算结果
[0128][0129]
计算得到乘客总效用
[0130]
步骤5.6：若新的乘客总效用u”＝14.63》u＝＝10.19，则更新联盟结构＝14.63》u＝＝10.19，则更新联盟结构u＝u'＝14.63；若不满足，则保持联盟结构不变。步骤6：不能再通过切换操作改变联盟结构来提高乘客总效用，当前联盟再通过切换操作改变联盟结构来提高乘客总效用，当前联盟达到稳定，结束流程，完成拼车调度。
[0131]
上述方案中，本发明基于(联盟博弈)拍卖算法优化拼车调度，根据候选司机和乘
客的行程、供需信息对拼车调度方案进行数学建模，其中候选司机的信息包括候选司机的出发地、目的地、最大可容忍绕路比率、可提供的座位数量和要价，乘客的信息包括出发地、目的地、最大可容忍等待时间、最大可容忍绕路比率、所需座位数量和出价；在满足供需均衡，保障私家车司机要价收入的基础上，以最大化乘客总效用为求解目标，采用(联盟博弈)拍卖算法，在得到最优的候选司机乘客匹配的情况下，根据定价策略计算候选司机的收入与共乘乘客的分摊费用并给出候选司机行驶的最优拼车路线；
[0132]
本发明相较于现有的里程时长拼车计费算法而言，可以通过让候选司机部分让利，以及保障乘客无须支付交通拥堵费用的方式，激励乘客参与拼车；与此同时，所设计的方法可以保证拼车服务满足诚实性、个体合理性以及预算平衡性质，具备市场竞争力与应用价值。
[0133]
显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。

技术特征：
1.一种拼车调度方法，其特征在于，包括以下步骤：步骤1：分别收集候选司机和乘客的出行信息，构建每个乘客的候选司机集合；其中，定义候选司机为m
i
,i∈{1,2,...,m}，候选司机的集合为m＝{m1,m2,...,m
m
}，其中m为候选司机的数量；每个候选司机的行程其中分别表示候选司机的出发地坐标、目的地坐标、最大可容忍绕路比率、可提供的座位数量；定义乘客为n
j
,j∈{1,2,...,n}，乘客的集合为其中n为乘客的数量；每个乘客的行程其中分别表示乘客的出发地坐标、目的地坐标、最大可容忍等待时间、最大可容忍绕路比率、所需座位数量；步骤2：将乘客依据近距离优先规则划分为多个联盟，构建初始联盟结构；步骤3：构建每个联盟的出价和候选司机的要价；步骤4：根据定价策略确定胜出者和失败者，并计算乘客总效用；步骤5：对每位乘客执行切换操作调整乘客的分配，，判断切换操作是否满足切换规则，若不满足，保持联盟结构不变；若满足，更新联盟结构；步骤6：判断当前联盟结构是否满足稳定性，若不满足，返回步骤5；若满足，结束流程，完成拼车调度。2.根据权利要求1所述一种拼车调度方法，其特征在于，步骤1中构建每个乘客的候选司机集合具体步骤如下：步骤1.1：遍历乘客集合对于乘客集合中的每个乘客，依次遍历候选司机集合m，对于每一个候选司机，判断候选司机与乘客能否匹配，具体步骤如下：步骤1.1.1：判断乘客是否在候选司机的接载范围其中表示候选司机出发地和乘客出发地之间的欧氏距离，r表示候选司机的接载半径，若乘客不在候选司机接载范围内，则不考虑该候选司机；步骤1.1.2：判断候选司机能否为乘客提供所需的座位数量若候选司机可提供的座位数量不足，则不考虑该候选司机；步骤1.1.3：将乘客的出发地和目的地添加到候选司机当前的路径序列，生成最优路径，计算乘客的实际等待时间μ
j
、实际行驶距离l
j
以及候选司机的实际行驶距离l
i
；步骤1.1.4：判断乘客的等待时间μ
j
约束是否满足若不满足，则不考虑该候选司机；步骤1.1.5：判断乘客的绕路约束是否满足其中为乘客的行程公里数，若不满足，则不考虑该候选司机；步骤1.1.6：判断候选司机的绕路约束是否满足其中为候选司机行程公里数，若不满足，则不考虑该候选司机；步骤1.2：将同时满足以上条件的候选司机添加到乘客对应的候选司机集合中，得到每个乘客的候选司机集合。3.根据权利要求2所述一种拼车调度方法，其特征在于，步骤2中，将分配给同一候选司机的乘客定义为一个联盟c
i
,i∈{1,
…
,m}，联盟c
i
表示分配给候选司机m
i
的一组乘客，联盟
和候选司机之间是一一对应的关系；没有匹配候选司机的一组乘客用联盟c0表示；联盟c0、联盟c
i
组成一个联盟结构联盟结构中包含所有的乘客并且任意两个联盟的交集为空集4.根据权利要求3所述一种拼车调度方法，其特征在于，步骤2中构建初始联盟结构，具体步骤如下：步骤2.1：遍历候选司机集合，对于每个候选司机，创建一个与候选司机对应的初始联盟，即空集；步骤2.2：遍历乘客集合，对于每个乘客，在乘客对应的候选司机集合中，根据近距离优先规则，找出距离乘客出发地最近的候选司机，将乘客添加到该候选司机对应的联盟中。5.根据权利要求4所述一种拼车调度方法，其特征在于，步骤3具体为：步骤3.1：根据乘客的出发地和目的地得到乘客的行程公里数和行程时间并计算乘客的预估费用其中，φ表示为每公里费率，表示为每分钟费率；将乘客的预估费用作为乘客的出价步骤3.2：计算联盟中乘客的最低出价联盟的出价为|c
i
|表示联盟c
i
中乘客的数量；步骤3.3：根据候选司机的出发地和目的地得到候选司机的行程公里数和行程时间并计算候选司机的预期收入其中，ρ表示为每公里的燃料成本，σ表示为每分钟的人工成本；将候选司机的预期收入作为候选司机的要价6.根据权利要求5所述一种拼车调度方法，其特征在于，步骤4的具体步骤如下：步骤4.1：按照联盟中乘客的最低出价从高到低对联盟排序，得到一个有序的联盟集合步骤4.2：遍历联盟集合c，根据定价策略确定胜出者和失败者；步骤4.3：遍历完成后，计算乘客总效用7.根据权利要求6所述一种拼车调度方法，其特征在于，步骤4.2具体过程如下：步骤4.2.1：对于每一个联盟判断联盟的出价是否满足对应候选司机的要价其中κ为拼车平台收取的手续费率，用于维护和运营平台；若满足，执行步骤4.2.2；若不满足，执行步骤4.2.4；步骤4.2.2：计算判断是否满足条件若满足，执行步骤4.2.3；若不满足，执行步骤4.2.4；步骤4.2.3：将联盟中的乘客和对应的候选司机判定为胜出者，联盟中每个乘客需
支付的费用为计算乘客的效用联盟对应候选司机m
i
的收入为步骤4.2.4：将联盟中的乘客和对应的候选司机判定为失败者，联盟中每个乘客需支付的费用为乘客的效用联盟对应候选司机m
i
的收入为p
is
＝0。8.根据权利要求7所述一种拼车调度方法，其特征在于，步骤5中，切换操作是一种改变联盟结构的手段，是指在一个联盟结构中，将一位乘客n
j
从当前联盟c
i
移除并添加到另一个联盟从而得到一个新的联盟结构定义切换规则为对一位乘客执行切换操作能够提高乘客总效用。9.根据权利要求8所述一种拼车调度方法，其特征在于，步骤5中对每位乘客执行切换操作调整乘客分配，具体步骤如下：步骤5.1：记录当前的联盟结构以及乘客总效用步骤5.2：遍历乘客对应的候选司机集合，执行步骤1.1.2-1.1.6判断乘客能否加入与候选司机对应的联盟中，直到找到一个该乘客能加入的新联盟c
′
i
；步骤5.3：若新联盟c
′
i
存在，则执行步骤5.4；若新联盟c
′
i
不存在，则进入下一次循环，判断下一个乘客；步骤5.4：将乘客从当前联盟c
i
移除，添加到新联盟c
′
i
中，形成新的联盟结构步骤5.5：在新的联盟结构下执行步骤3和步骤4，得到新的乘客总效用步骤5.6：若新的乘客总效用则更新联盟结构若不满足，则保持联盟结构不变。10.根据权利要求9所述一种拼车调度方法，其特征在于，步骤6中，联盟结构的稳定性是指不能再通过切换操作改变联盟结构来提高乘客总效用时，联盟结构是稳定的；判断联盟结构是否稳定的具体步骤如下：步骤6.1：记录在当前联盟结构下的乘客总效用u；步骤6.2：执行步骤5，得到最后一次迭代的新的乘客总效用u'；步骤6.3：若最后一次迭代的新的乘客总效用u'>u，则联盟结构已更新，返回步骤6.1；若最后一次迭代的新的乘客总效用u'＝u，则表明当前联盟结构是稳定的，将在当前联盟结构下的匹配与定价结果作为最终结果，完成拼车调度。

技术总结
本发明公开了一种拼车调度方法，步骤1：分别收集候选司机和乘客的出行信息，构建每个乘客的候选司机集合；步骤2：将乘客依据近距离优先规则划分为多个联盟，构建初始联盟结构；步骤3：构建每个联盟的出价和候选司机的要价；步骤4：根据定价策略确定胜出者和失败者，并计算乘客总效用；步骤5：对每位乘客执行切换操作调整乘客的分配，判断切换操作是否满足切换规则，若不满足，保持联盟结构不变；若满足，更新联盟结构；步骤6：判断当前联盟结构是否满足稳定性，若不满足，返回步骤5；若满足，结束流程，完成拼车调度。通过本发明方法进行拼车调度，节省乘客的乘车费用，从而激励候选司机和乘客积极参与拼车。积极参与拼车。积极参与拼车。


技术研发人员：陈龙 袁杏仪 黄家乐 武继刚
受保护的技术使用者：广东工业大学
技术研发日：2023.03.07
技术公布日：2023/7/21