基于多车型和空车再平衡的出租车调度方法及调度系统

1.本技术属于出租车调度技术领域，具体涉及一种基于多车型和空车再平衡的出租车调度方法及调度系统。


背景技术：

2.随着我国城市化进程的不断加快，人们的生活水平不断提高，逐渐看重出行舒适度以及行驶效率。为了更好地缓解城市交通拥堵问题，需着重提高城市公共交通的运行效率，大力推行公共交通服务。出租车作为城市公共交通的重要一环，以其舒适的乘车体验和出发地、目的地灵活选择等特点，成为人们偏爱的出行方式之一，因此，完善出租车服务的重要性不言而喻。传统的出租车调度模式主要依靠司机长期的经营经验，可能会造成区域出租车空载率高以及乘客“打车难”的问题，乘客的出行体验和出租车的运营成本深受影响。而现有技术中的出租车调度方法，其大多只考虑出租车层面的分配管理，对乘客需求方面有所欠缺，没有很好的提高乘客的出行体验，所以，迫切需要开发出一种在提高用车效率的同时又能尽量满足乘客需求的新型出租车调度方案。


技术实现要素：

3.本发明公开了一种基于多车型和空车再平衡的出租车调度方法及调度系统，其可以有效解决背景技术中涉及的技术问题。
4.为实现上述目的，本发明的技术方案为：
5.一种基于多车型和空车再平衡的出租车调度方法，包括以下步骤：
6.步骤s1：获取乘客的乘车请求信息以及车辆实时状态，并每隔一段时间对状态为空车的车辆进行分配；
7.步骤s2：根据乘车请求信息以及车辆实时状态定义决策网络，包括车辆节点k、乘客请求节点r以及车辆最终停止节点s；
8.步骤s3：定义决策网络中的车辆最大化收益函数，包括：
9.步骤s31：定义软时间窗，包括乘客提交的期望上车时间窗和可接受时间窗，若车辆晚于期望上车时间窗到达，则需支付惩罚费用；
10.步骤s32：计算车辆接收乘客请求所得的利润，
[0011][0012]
p
ki
＝f(oi，di)-(d(sk，oi)+d(oi，di))
·ck-cp
ki
[0013]
其中，为车辆k在完成乘客请求i后接收请求j所得利润，p
ki
为处于空闲状态车辆k执行乘客请求i所得利润，函数f为乘客支出的车费，oj为乘客请求j的起点，dj为请求j目的地，di为车辆执行请求i的目的地，ck为车辆k单位行驶距离的行驶成本，为车辆k执行完请求i后执行请求j的惩罚费用，oi为乘客请求i的起点，sk为车辆k当前所在位置，co
ki
为车辆k处于空闲状态执行请求i的惩罚费用；
[0014]
步骤s33：根据利润构建车辆最大化收益函数；
[0015]
步骤s4：进一步定义决策网络中的约束条件；
[0016]
步骤s5：基于车辆最大化收益函数和约束条件对车辆进行调度。
[0017]
作为本发明的一种优选改进，步骤s1中，所述每隔一段时间对状态为空车的车辆进行分配的具体步骤包括：
[0018]
步骤s11：将调度区域划分成m个，计算每个区域内的乘客比和车辆比；
[0019]
步骤s12：计算m个区域中任意一个区域所需的车辆数其中，ai为第i个区域中的乘客数，bm为第m个区域中的实际车辆数；
[0020]
步骤s13：计算需要转移到第i个区域的车辆数bi为第i个区域中的实际车辆数；若则从其他区域分配空车到该区域；若则从该区域分配空车到其他区域。
[0021]
作为本发明的一种优选改进，步骤s2中，车辆节点k、乘客请求节点r和车辆最终停止节点s相连表示车辆接受并完成请求，最后处于空闲状态；车辆节点k直接和车辆最终停止节点s相连表示车辆未接收请求，一直处于空闲状态。
[0022]
作为本发明的一种优选改进，步骤s3中，所述最大化收益函数为：
[0023][0024]
其中，z为收益，和x
ki
为车辆接收请求的决策变量，p
′
ij
和p
′
ki
为车辆在接收订单后消耗的成本，pk′s为车辆未接收订单消耗的成本。
[0025]
作为本发明的一种优选改进，步骤s4中，所述约束条件包括：
[0026]
所有车辆只处于两种状态，接收某个订单或不接受任意一个订单；
[0027]
同一个请求只能被一辆车接收；
[0028]
车辆在执行完一个乘客请求后，只处于空闲状态或执行下一请求状态；
[0029]
车辆在一个决策周期结束时，要么在执行某个请求，要么处于空闲状态；
[0030]
乘客乘车人数小于车辆可容纳人数；
[0031]
车辆到达时间需要满足乘客提交的可接受时间窗。
[0032]
作为本发明的一种优选改进，步骤s5中，先根据步骤s1获取的乘客乘车请求信息以及车辆实时状态，计算车辆到达乘客请求起点的预计时间，寻找满足在乘客预期上车时间内到达的车辆，然后在此基础上，根据车辆最大化收益函数进行车辆调度。
[0033]
一种基于所述的基于多车型和空车再平衡的出租车调度方法的调度系统，包括乘客端、调度平台以及车载端；所述乘客端用于获取乘客乘车请求并发送至调度平台；所述调度平台用于接收乘客请求信息和获取车辆实时状态，并将符合乘客乘车需求的车辆进行绑定，生成订单；所述车载端用于接收调度平台生成的订单信息。
[0034]
本发明的有益效果如下：
[0035]
1、通过计算分析车辆的实时情况，并与乘客的期望上车时间窗匹配，将可以在预
期上车时间内到达的车辆和乘客进行绑定，减少了乘客的等待时间，提高了乘客的出行体验；
[0036]
2、通过对没有在期望时间内到达的车辆设置惩罚函数，减少了乘客等待时间成本，提高了出租车对乘客的吸引力；
[0037]
3、通过对多种车型的车辆分配以及空车再平衡调度，在车辆收益最大化的前提下，不仅能够最大程度利用出租车资源，同时也能尽可能满足乘客的需求。
附图说明
[0038]
图1为本技术实施例提供的调度流程示意图；
[0039]
图2为本技术实施例提供的空车再平衡示意图；
[0040]
图3为本技术实施例提供的决策网络示意图；
[0041]
图4为本技术实施例提供的调度系统的结构框架图。
具体实施方式
[0042]
下面将结合本发明实施例对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
[0043]
本技术实施例提供了一种基于多车型和空车再平衡的出租车调度方法，包括以下步骤：
[0044]
步骤s1：获取乘客的乘车请求信息以及车辆实时状态，并每隔一段时间对状态为空车的车辆进行分配。
[0045]
参阅图1所示，乘客将乘车请求提交到调度系统中，调度系统每隔1min进行一次整体的决策，获取乘客提交的乘车请求，同时获取出租车的实时状态。然后综合考虑1min内乘客到达的实时请求和未来30min内到达的预定请求。
[0046]
计算出租车到达请求起点的预计时间，并与乘客提交的预期上车时间进行匹配，寻找可以在预期上车时间内到达的出租车。但由于车辆10min内的行程是固定的，如果乘客请求已经和某一车辆绑定，则不会更换安排的车辆；如果车辆在接收请求后出发时间在10min以上，则可以重新分配车辆，以此减少乘客的等待时间。
[0047]
如图2所示，在现实生活中，时常会出现大量空闲出租车聚集以及乘客叫车难现象，而这是由于车辆分配的不合理导致。因此，调度系统在每个固定的时间段会进行一次更新决策，根据乘客的历史请求数据，对区域和时间段进行划分，然后预测各区域乘客需求量并为其分配空车，实现乘客和车辆匹配平衡，具体步骤如下：
[0048]
步骤s11：将调度区域划分成m个，每个区域内乘客比为a1：a2：
…
：ai：a
i+1
：
…
：am，车辆比为b1：b2：
…
：bi：b
i+1
：
…
：bm；其中，ai为第i个区域中的乘客数，am为第m个区域中的乘客数，bi为第i个区域中的实际车辆数，bm为第m个区域中的实际车辆数；
[0049]
步骤s12：计算第i个区域所需的车辆数
[0050]
步骤s13：计算需要转移到第i个区域的车辆数如果则代表该
区域乘客需求量大且车辆少，需要从其他区域分配空车到该区域；如果则代表该区域乘客需求量小且车辆多，需要从该区域分配空车到其他区域。通过计算分配，使出租车数量之比接近a1：a2：
…
：ai：a
i+1
：
…
：am，实现空车再平衡。
[0051]
步骤s2：定义决策网络。如图3所示，k为车辆节点即决策网络的起始节点、r为乘客请求节点、s为车辆最终停止节点。k、r和s相连表示车辆接收请求并完成，最后处于空闲状态；k直接和s相连表示车辆未接收请求，一直处于空闲状态。
[0052]
步骤s3：定义决策网络中的车辆最大化收益函数，包括：
[0053]
步骤s31：乘客发送请求时会提交期望上车时间窗[te,t
l
]，te为期望最早上车时间，t
l
为期望最晚上车时间，由于部分乘客对上车时间的要求比较宽松，所以会提供可接受时间窗[tte,tt
l
]，tte为可接受最早上车时间，tt
l
为可接受最晚上车时间。如果车辆晚于期望上车时间窗到达，则需接受一定的惩罚费用cp＝(t
arrive-t
l
)f，t
arrive
为车辆实际到达时间，f为单位时间内的惩罚费用。如果车辆提前或在期望上车时间窗内到达，则cp＝0。
[0054]
步骤s32：计算车辆接收乘客请求所得的利润，包括两种情况。
[0055]
第一种是车辆正在进行请求i，该车在完成请求i后可以在请求j的预期时间内到达请求j的起点，所以可以将该车和请求j进行匹配，所得利润为：
[0056][0057]
其中，为车辆k在完成乘客请求i后接收请求j所得利润，函数f为乘客支出的车费，oj为乘客请求j的起点，dj为请求j目的地，di为车辆执行请求i的目的地，ck为车辆k单位行驶距离的行驶成本，为车辆k执行完请求i后执行请求j的惩罚费用。
[0058]
第二种是车辆处于空闲状态，从当前位置到达请求起点的时间满足预期时间，从而匹配成功，所得利润为：
[0059]
p
ki
＝f(oi，di)-(d(sk，oi)+d(oi，di))
·ck-cp
ki
[0060]
其中，p
ki
为处于空闲状态车辆k执行乘客请求i所得利润，oi为乘客请求i的起点，di为车辆执行请求i的目的地，sk为车辆k当前所在位置，cp
ki
为车辆k处于空闲状态执行请求i的惩罚费用。
[0061]
步骤s33：根据利润构建车辆最大化收益函数：
[0062][0063]
其中，z为收益，和x
ki
为车辆接收请求的决策变量，p
′
ij
和p
′
ij
为车辆在接收订单后消耗的成本，比如驾驶人员的工资和订单提成等；p
k’s
为车辆未接收订单消耗的成本。
[0064]
步骤s4：进一步定义决策网络中的约束条件。
[0065]
第一，任意一辆车只处于两种状态，接收某个订单或不接受任意一个订单：
[0066][0067]
其中，x
ki
表示车辆k从当前位置前往请求i的起点，此时车辆k接收某一请求；x
ks
表示车辆k没有接收任何一个请求，处于待定状态。
[0068]
第二，为了最大程度提高出租车利用率，同一个乘客请求有且只能被一辆车接收：
[0069][0070]
其中，表示车辆正在进行请求i，经过分析计算得到车辆满足请求j的预期上车时间窗，从而接收成功；x
kj
表示车辆处于空闲状态，可以接受请求j。总之，任意一个请求只能被一辆车接收。如果在接收请求后，车辆出发时间在10min以上，则重新进行匹配，同样满足此约束。
[0071]
第三，车辆在执行完一个乘客请求后，只处于空闲状态或执行下一请求状态。
[0072][0073]
第四，车辆在一个决策周期结束时，要么在执行某个请求，要么处于空闲状态；
[0074][0075]
其中，n为车辆数量。
[0076]
第五，乘客乘车人数小于车辆可容纳人数。由于出租车车型多种多样，每种车型载客人数不同，乘客在发送请求时会提供乘车人数，调度平台根据人数匹配车型，以提高车辆利用率和乘客出行体验。
[0077][0078][0079]
其中，ni和nj为请求提供的乘车人数，ck为车辆可容纳人数。
[0080]
第六，车辆在接收请求后，其到达时间需要满足乘客提交的可接受时间窗约束。在现实生活中，一些乘客因为一些个人因素，对上车时间要求并不会过于严格，所以乘客在发送请求时会提供一个范围更大的可接受时间窗。为了提高出租车对乘客的吸引力，调度平台在进行车辆匹配时，需要考虑到乘客的可接受最晚上车时间。因此车辆到达乘客请求起点的时间不能晚于最大可接受时间。
[0081][0082][0083]
步骤s5：基于车辆最大化收益函数和约束条件对车辆进行调度。
[0084]
首先，由于步骤s1获取了乘客乘车请求信息以及车辆实时状态以计算车辆到达乘客请求起点的预计时间，然后寻找到满足在乘客预期上车时间内到达的车辆，所以，在车辆满足在预期上车时间内到达的基础上，根据车辆最大化收益函数进行车辆调度，并且该车辆的调度还需要满足约束条件。
[0085]
本技术实施例还提供了一种基于多车型和空车再平衡的出租车调度方法的调度系统，如图4所示，包括乘客端1、调度平台2以及车载端3。所述乘客端1用于获取乘客乘车请求并发送至调度平台2；所述调度平台2用于接收乘客请求信息和获取车辆实时状态，并将
符合乘客乘车需求的车辆进行绑定，生成订单；所述车载端3用于接收调度平台2生成的订单信息，完成乘客的乘车请求。
[0086]
本发明的有益效果如下：
[0087]
1、通过计算分析车辆的实时情况，并与乘客的期望上车时间窗匹配，将可以在预期上车时间内到达的车辆和乘客进行绑定，减少了乘客的等待时间，提高了乘客的出行体验；
[0088]
2、通过对没有在期望时间内到达的车辆设置惩罚函数，减少了乘客等待时间成本，提高了出租车对乘客的吸引力；
[0089]
3、通过对多种车型的车辆分配以及空车再平衡调度，在车辆收益最大化的前提下，不仅能够最大程度利用出租车资源，同时也能尽可能满足乘客的需求。
[0090]
上面结合附图对本技术的实施例进行了描述，但是本技术并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本技术的启示下，在不脱离本技术宗旨和权利要求所保护的范围情况下，还可做出很多形式，均属于本技术的保护之内。

技术特征：
1.一种基于多车型和空车再平衡的出租车调度方法，其特征在于，包括以下步骤：步骤s1：获取乘客的乘车请求信息以及车辆实时状态，并每隔一段时间对状态为空车的车辆进行分配；步骤s2：根据乘车请求信息以及车辆实时状态定义决策网络，包括车辆节点k、乘客请求节点r以及车辆最终停止节点s；步骤s3：定义决策网络中的车辆最大化收益函数，具体包括：步骤s31：定义软时间窗，包括乘客提交的期望上车时间窗和可接受时间窗，若车辆晚于期望上车时间窗到达，则需支付惩罚费用；步骤s32：计算车辆接收乘客请求所得的利润，p
ki
＝f(o
i
，d
i
)-(d(s
k
，o
i
)+d(o
i
，d
i
))
·
c
k-cp
ki
其中，为车辆k在完成乘客请求i后接收请求j所得利润，p
ki
为处于空闲状态车辆k执行乘客请求i所得利润，函数f为乘客支出的车费，o
j
为乘客请求j的起点，d
j
为请求j目的地，d
i
为车辆执行请求i的目的地，c
k
为车辆k单位行驶距离的行驶成本，为车辆k执行完请求i后执行请求j的惩罚费用，o
i
为乘客请求i的起点，s
k
为车辆k当前所在位置，cp
ki
为车辆k处于空闲状态执行请求i的惩罚费用；步骤s33：根据利润构建车辆最大化收益函数；步骤s4：进一步定义决策网络中的约束条件；步骤s5：基于车辆最大化收益函数和约束条件对车辆进行调度。2.根据权利要求1所述的方法，其特征在于，步骤s1中，所述每隔一段时间对状态为空车的车辆进行分配的具体步骤包括：步骤s11：将调度区域划分成m个，计算每个区域内的乘客比和车辆比；步骤s12：计算m个区域中任意一个区域所需的车辆数其中，a
i
为第i个区域中的乘客数，b
m
为第m个区域中的实际车辆数；步骤s13：计算需要转移到第i个区域的车辆数b
i
为第i个区域中的实际车辆数；若则从其他区域分配空车到该区域；若则从该区域分配空车到其他区域。3.根据权利要求1所述的方法，其特征在于，步骤s2中，车辆节点k、乘客请求节点r和车辆最终停止节点s相连表示车辆接受并完成请求，最后处于空闲状态；车辆节点k直接和车辆最终停止节点s相连表示车辆未接收请求，一直处于空闲状态。4.根据权利要求1所述的方法，其特征在于，步骤s3中，所述最大化收益函数为：其中，z为收益，和x
ki
为车辆接收请求的决策变量，p
′
ij
和p
′
ki
为车辆在接收订单后消耗的成本，p
k
′
s
为车辆未接收订单消耗的成本。
5.根据权利要求1所述的方法，其特征在于，步骤s4中，所述约束条件包括：所有车辆只处于两种状态，接收某个订单或不接受任意一个订单；同一个请求只能被一辆车接收；车辆在执行完一个乘客请求后，只处于空闲状态或执行下一请求状态；车辆在一个决策周期结束时，要么在执行某个请求，要么处于空闲状态；乘客乘车人数小于车辆可容纳人数；车辆到达时间需要满足乘客提交的可接受时间窗。6.根据权利要求1所述的方法，其特征在于，步骤s5中，先根据步骤s1获取的乘客乘车请求信息以及车辆实时状态，计算车辆到达乘客请求起点的预计时间，寻找满足在乘客预期上车时间内到达的车辆，然后在此基础上，根据车辆最大化收益函数进行车辆调度。7.一种基于如权利要求1-6所述的基于多车型和空车再平衡的出租车调度方法的调度系统，其特征在于，包括乘客端、调度平台以及车载端；所述乘客端用于获取乘客乘车请求并发送至调度平台；所述调度平台用于接收乘客请求信息和获取车辆实时状态，并将符合乘客乘车需求的车辆进行绑定，生成订单；所述车载端用于接收调度平台生成的订单信息。

技术总结
本申请公开了一种基于多车型和空车再平衡的出租车调度方法，包括：步骤S1，获取乘客乘车请求信息以及车辆实时状态，并每隔一段时间对状态为空车的车辆进行分配；步骤S2，根据乘车请求信息以及车辆实时状态定义决策网络；步骤S3，定义决策网络中的车辆最大化收益函数；步骤S4，进一步定义决策网络中的约束条件；步骤S5，基于车辆最大化收益函数和约束条件对车辆进行调度。本发明通过对多种车型的分配以及空车再平衡调度，在提高用车效率的同时能满足乘客的需求，提升了乘客的出行体验并降低了出租车的行驶成本。租车的行驶成本。租车的行驶成本。


技术研发人员：胡满江 徐依菲 王兹珑 王晓伟 边有钢 秦洪懋 朱颖
受保护的技术使用者：湖南大学
技术研发日：2023.04.11
技术公布日：2023/7/20