本发明涉及在线叫车订单分配，尤其涉及一种基于强化学习的定价、分配和重定位联合优化方法、装置和存储介质。
背景技术：
1、信息技术的蓬勃发展促使许多行业的商业模式发生了重大变化，也催生了滴滴、uber和lyft等流行的在线叫车平台。在这些平台的支持下，人们在交通出行方面受到的限制大大减少。在典型的网约车平台中，潜在乘客在提交出行请求即输入出发地和目的地后，会收到一个报价。如果请求者接受该报价，那么他/她的请求会转换为平台中的一个待处理订单。在每个时隙结束时，针对所有有效订单和空闲司机，平台决策两者间的匹配方案。定价、订单分配和车辆重定位是网约车系统中的核心模块，也是影响平台效率和乘客与司机双方体验的重要决策任务。定价利用请求者的价格敏感性来调控客户请求到平台订单的转换，进而会影响后续决策的结果。原因在于定价会改变平台中的订单分布。订单分配的目的是将订单分配给合适的空闲司机。理想的分配决策应该是基于当前的供需分布获得的，并且从长远来看是有益的。车辆重定位的目的是将富余的闲置车辆引导到未来有更多乘客的区域。不难理解，当前的分配决策和重定位决策会直接改变司机当前的位置和司机未来的空间分布，间接影响未来决策的结果。同时，司机位置的变更反过来会影响定价决策。一个典型的例子是uber采用的峰时定价机制。
2、显然，定价、订单分配和重定位是密切相关的。它们的相关性表现在两个方面：一是它们都可以调节供需关系，二是它们相互影响彼此的决策。因此，多任务联合优化被提出。它期望联合优化多个相关任务以产生单任务优化无法实现的更好的决策。通常，这能明显优化平台的运营效率。然而，以前的研究要么单独优化定价、订单分配和重定位中的一个，要么联合优化订单分配和重定位(或定价)，忽略了这三项任务间的重要相关性。这极大地限制平台和司机的经济收益、乘客出行请求的完成数量，会对平台的长期发展造成不利影响。现有的解决方案尚存在巨大的优化空间。基于此，本发明提出联合优化定价、分配和重定位以提高网约车平台的长期效率。然而，这个考虑更全面的问题也更为复杂和困难。其主要挑战有：首先，定价、订单分配和重定位虽然高度相关，但它们在本质上是不同的。要找到一种有效的方式将三者联系起来使它们朝着同一个目标协同优化是十分困难的。换句话说，定价、订单分配和重定位的联合优化很难被建模出来。其次，决策的执行是连续的、不可逆的。只有定价确定了平台中的订单，分配和重定位才能进行。因此，该联合优化问题既涉及多阶段决策，又涉及复杂的协作。第三，整个决策过程具有高度的时空动态性。这种时空动态性是指需求(请求)和供给(司机)在空间和时间两个维度上都在一直动态变化。
3、近年来，不同于传统基于规则的启发式方法，现有针对在线叫车平台决策任务的研究工作大多应用强化学习来获得更好的解决方案。这源于强化学习在决策任务上的优异表现，所作决策往往是长期有益的。这对平台的长期发展更为有利，同时也能充分提高司机的经济收入和乘客的体验。然而，现有基于强化学习和不基于强化学习的方法普遍存在一个问题，即要么单独优化定价、订单分配和重定位中的一个，要么联合优化订单分配和重定位(或定价)，忽略了定价、分配和重定位三项任务间的重要相关性，使得所获得的结果可能是次优的，无法获得最优的结果。
技术实现思路
1、本发明的目的在于提供一种基于强化学习的定价、分配和重定位联合优化方法、系统、装置和存储介质，是一种基于多模型交互强化学习的解决方案，基于强化学习对定价、分配和重定位三项任务进行联合优化能够获得更好的解，以提高在线叫车平台的长期效率，包括平台和司机的经济效益以及乘客出行请求的完成数量。
2、为实现本发明目的，本发明提供的一种基于强化学习的定价、分配和重定位联合优化方法，包括以下步骤：
3、对系统进行建模，定义优化问题，包括目标、约束和决策变量；
4、将优化问题转化为多智能体情形下的部分可观测马尔科夫决策过程，确定观测、动作和奖励；
5、基于历史数据训练用于实时估计出行请求数量的动态环境信息感知的需求预测模型；
6、在系统中部署多臂赌博机算法，收集定价记录，在线训练定价模型；
7、在系统中部署sac算法，收集司机轨迹经验，在线训练融合重定位的分配模型，中间穿插使用启发式算法产生的决策结果矫正训练方向。
8、所述对系统进行建模，包括：
9、考虑服务范围为一个城市的在线叫车系统，它包含一组状态不断动态变化的司机和一组由请求转换而来的待处理订单；
10、将城市划分为g个均匀的网格，得到网格化的地图
11、将一天离散为t个等长的时隙，记为
12、定义i表示在线叫车平台在时隙t收到的出行请求，用元组<oi，di，pi>表示，其中，oi表示请求的起点，di表示请求的目的地，pi表示请求的基础价(起点oi和目的地di都是由经度和纬度组成的二元组)；
13、定义由请求i在顾客确认交易即同意平台的报价后转化而得的待处理订单为j，用元组<oj，dj，pj>表示，其中，oi表示订单的起点，di表示订单的目的地，pj表示订单的成交价格(即pi与多臂赌博机定价算法确定的定价系数ci的乘积)；
14、定义κ表示平台中的一个司机，用元组表示，其中，和分别表示司机κ在时隙t的状态和位置，表示自司机κ完成上一个订单以来的空闲时长；
15、注意，每个司机κ有两种状态，即占用和空闲，且对于任意时隙t，只有处于空闲状态的司机才能参与决策过程；
16、平台作为决策中心，为每个实时产生的出行请求i进行定价，并在每个时隙t的末尾求解订单与司机间的匹配决策；
17、总商品交易额是所有已完成订单的成交价格，表示为：
18、
19、式中，表示在时隙t内产生并最终成功交易的出行请求，表示在时隙t内成功交易的订单；
20、成功率为已完成请求占所有请求的百分比，表示为：
21、
22、式中，表示在时隙t内产生的出行请求。
23、进一步地，所述定义优化问题，包括：
24、将定价、分配和重定位的联合优化建模为一个两阶段的决策优化问题，其中，第一阶段为上下文特征感知的实时动态定价，第二阶段为融合重定位的订单分配；
25、对于每个请求i，其期望立即收益表示为：
26、u(xi，ci)＝f(xi，ci)cipi＝f(xi，ci)ci(μdisi+ωduri)
27、其中，f(xi，ci)表示请求i在定价系数ci下转换为订单的概率即请求者(乘客)接受交易价格cipi的概率，xi表示请求i的上下文特征，disi和duri分别表示请求i的预计行程距离和预计行程时间，μ和ω分别表示单位距离费用和单位时间费用；
28、对于每个请求i，如果其成功地转换成订单，并在时隙t被司机κ完成，那么其收益为其即时收益和重定位司机κ的未来影响的总和，表示为：
29、
30、其中，δt表示i的行程时长且其大小为完成行程所消耗的时隙数，γ为一个0到1之间折扣因子，vθ是用于评估环境好坏的值函数，s(di)表示请求i的目的地状态，表示司机κ的当前状态；
31、优化目标是寻找最佳联合决策以最大化长期的总商品贸易额和成功率：
32、
33、其中，表示在时隙t产生的请求，表示在时隙t结束时处于空闲状态的司机；
34、u′(xi，ci)表示司机κ服务请求i的期望总收益，定义为：
35、
36、式中，ci与bjκ为决策变量，其中，ci表示定价系数，由定价模型根据请求i的上下文特征从预设的集合中选择得到，bjκ∈{0，1}为分配决策，表示是否将订单j分配给司机κ；
37、需要满足的第一个约束为每个司机最多可同时服务一个请求：
38、
39、需要满足的第二个约束为每个请求只能由一个司机服务：
40、
41、需要满足的第三个约束为司机与出行请求的起点的距离应该在有限范围内：
42、
43、需要满足的第四个约束为司机服务出行请求所获得的纯利润应该大于0：
44、
45、其中，η表示平台的收入抽成比例，β表示单位行程成本，md表示最大分配距离。
46、进一步地，所述确定观测，包括：
47、将平台中的每个司机视为一个智能体，且将每个司机的活动视为一个部分可观测马尔可夫决策过程；
48、在时隙t的末尾，每个司机κ观测周围地理环境的局部信息；所述局部信息包括当前的时隙t、该司机所在的地图网格该司机所在网格附近的空闲司机数量该司机所在网格附近的出行请求数量
49、在时隙t，司机κ的观测定义为如下元组：
50、
51、注意，司机完成一个订单通常需要多个时隙，因此正在服务订单的司机的观测是没有意义的；对于每个司机κ，其下一次观测记为其中，δt表示司机κ服务订单所需的时隙数。
52、进一步地，所述确定动作，包括：
53、在时隙t，如果有由请求转化而来的新订单，所有司机κ根据当前的观测选择一个动作来决定匹配哪个订单或者重定位到哪个区域；
54、将每个网格视为司机的候选动作；如果一个司机采取动作aκ，则分配给该司机的订单的目的地必须位于ak对应的网格中；对于每个司机κ，将其所在网格的相邻网格，包括其当前所在网格，视为其候选的重定位动作，记为
55、因此，每个司机κ的动作空间为且其大小为g+9。
56、进一步地，所述确定奖励，包括：
57、每个司机κ在执行完动作后获得的奖励被设置为订单的价格；特别地，如果智能体执行重定位动作，则其获得的奖励为0；
58、一个动作(服务订单或重定位到某个区域)一般需要跨越多个时隙才能被完成，因此对智能体获得的奖励进行折扣，即给定折扣因子γ，服务行程时长为δt个时隙且价格为pj的订单j的奖励为
59、进一步地，所述基于历史数据训练用于实时估计出行请求数量的动态环境信息感知的需求预测模型，包括：
60、预处理数据集，获得训练数据集合其中，ixi为包含环境特征和历史信息的特征矩阵，iyi为需求分布矩阵；
61、构建基于卷积神经网络的预测器，其中，该预测器的输入是7个包含重要环境特征和历史信息的2维矩阵，输出是1个2维矩阵；所述输入矩阵在训练时对应ixi，其中，矩阵的每个元素对应地图中某个网格的特征值；所述输入矩阵的特征包括日期的周期性(包括一周中的哪一天、一天中的哪个小时和一小时中的哪个周期)、环境特征(包括天气类型、温度和风速)以及历史信息(历史平均需求分布)；所述输出矩阵在训练时对应iyi，其中，该矩阵的每个元素值是未来10分钟对应网格内未来请求的数量；
62、以均方误差作为损失函数，利用adam优化器训练该预测器。
63、进一步地，所述在线训练定价模型，包括：
64、基于上下文感知的多臂赌博机算法linucb构建定价模型，随机初始化定价模型各条臂的参数；所述定价模型的每条臂对应一个定价系数；
65、在时隙t，每当一个新的出行请求i出现，定价模型根据请求i的上下文特征xi为其选择定价系数ci；所述上下文特征xi包括请求i出现的时间gt(i)、请求i的起点网格g(oi)、请求i的终点网格g(di)、请求i的预计行程距离disi、请求i的预计行程时长duri、请求i的基础价pi以及请求i的起点和终点周围的供需特征；
66、在收集到一系列的上下文向量、执行的臂和相应的预期收益后，任意臂的参数θc可通过岭回归估计出来：
67、
68、式中，dc为一个e×d特征矩阵(每行对应一个请求的上下文特征向量)，uc是对应dc的e维预期收益向量，id是d×d单位矩阵，e为用于训练臂参数的上下文特征向量的个数，d为每个上下文特征向量的维度；
69、进而，最优定价系数ci可由下式计算：
70、
71、其中，且对于任意δ＞0，为一个常数；
72、利用产生的定价记录更新定价模型各条臂的参数，重复经验收集、模型训练两个主要步骤，迭代优化定价模型。
73、进一步地，所述在线训练融合重定位的分配模型，包括：
74、随机初始化离散sac模型的网络参数；所述sac模型包含1个actor网络、1个v-critic网络和2个q-critic网络，其中，actor网络输出动作概率分布，用于帮助选择动作，v-critic网络用于对状态进行评分，q-critic用于对状态、动作组合进行评分；所述采用2个q-critic的原因是防止过估计；
75、在时隙t的末尾，sac分配模型根据司机κ的观测为其选择一个动作所述动作若为分配动作，则将目的地在对应的网格内且价格最高的订单分配给司机κ，若为重定位动作，则将司机κ重定位至对应的网格；
76、软状态值的计算公式定义如下：
77、
78、目标q值的计算公式定义如下：
79、
80、actor网络的更新可以通过最大化上述软状态值实现：
81、
82、在更新q-critic时，可以通过最小化如下均方误差来实现：
83、
84、在更新v-critic时，可以通过最小化如下均方误差来实现：
85、
86、式中，λ为温度参数，为从经验回放池中采样的一组经验，为司机κ在时隙t获得的奖励，δt为完成行程所需的时隙数，ψ为actor网络参数，φ1和φ2为q-critic网络参数，和为q-critic目标网络参数，θ为v-critic网络参数，为actor网络的输出(具体指在观测为时所有动作的采样概率分布)，为q-critic目标网络的输出(具体指q-critic目标网络对观测与所有动作的组合对的评分分布)，为q-critic网络的输出(具体指q-critic网络对观测和动作组合的评分)，为v-critic网络的输出(具体指v-critic网络对观测的评分)；
87、利用产生的司机轨迹经验更新分配模型各网络的参数，重复经验收集、模型训练两个主要步骤，迭代优化分配模型；在该过程中，每隔固定回合数便清空一次经验回放池，使用kuhn-munkres算法收集一定数量的经验，以矫正模型的训练；
88、注意，定价模型的训练与分配模型的训练紧密关联、相互影响，具体地，定价模型与分配模型在交互中朝着共同的目标学习；定价模型所作定价决策的预期收益取决于sac分配模型中的v-critic网络，而定价模型通过调控请求向订单的转换影响订单集，从而影响分配模型的输出；也就是说，本质上，这些组件以相互指导的方式进行学习以实现联合优化，原因在于它们的更新是高度相互依赖的。
89、本发明所采用的另一技术方案是：
90、一种基于强化学习的定价、分配和重定位联合优化系统，其特征在于，用于实现前述方法，包括以下模块：
91、建模模块，用于对系统进行建模，定义优化问题，包括目标、约束和决策变量；
92、转化模块，用于将优化问题转化为多智能体情形下的部分可观测马尔科夫决策过程，确定观测、动作和奖励；
93、需求预测模型训练模块，用于基于历史数据训练用于实时估计出行请求数量的动态环境信息感知的需求预测模型；
94、定价模块，用于部署多臂赌博机算法，收集定价记录，在线训练定价模型；
95、分配模块，用于收集司机轨迹经验，在线训练融合重定位的分配模型，并穿插使用启发式算法产生的决策结果矫正训练方向。
96、本发明所采用的另一技术方案是：
97、一种基于强化学习的定价、分配和重定位联合优化装置，包括：
98、至少一个处理器；
99、至少一个存储器，用于存储至少一个程序；
100、当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现上所述方法。
101、本发明所采用的另一技术方案是：
102、一种计算机可读存储介质，其中存储有处理器可执行的程序，所述处理器可执行的程序在由处理器执行时用于执行如上所述方法。
103、与现有技术相比，本发明的有益效果至少是：
104、(1)本发明方法在训练阶段，通过生成额外的经验来矫正模型的训练，有效地加快了模型的收敛速度。
105、(2)本发明考虑联合优化定价、订单分配和车辆重定位三项任务，以实现单任务优化无法实现的更优决策，从而显著提高了在线叫车平台和司机的经济收益(总商品贸易额)以及乘客出行请求的完成数量(成功率)。
1.一种基于强化学习的定价、分配和重定位联合优化方法，其特征在于，包括以下步骤：对系统进行建模，定义优化问题，包括目标、约束和决策变量；
2.根据权利要求1所述的一种基于强化学习的定价、分配与重定位联合优化方法，其特征在于，所述对系统进行建模，包括：
3.根据权利要求2所述的一种基于强化学习的定价、分配和重定位联合优化方法，其特征在于，所述定义优化问题，包括：
4.根据权利要求1所述的一种基于强化学习的定价、分配和重定位联合优化方法，其特征在于，所述确定观测，包括：
5.根据权利要求1所述的一种基于强化学习的定价、分配和重定位联合优化方法，其特征在于，所述基于历史数据训练用于实时估计出行请求数量的动态环境信息感知的需求预测模型，包括：
6.根据权利要求1所述的一种基于强化学习的定价、分配和重定位联合优化方法，其特征在于，所述在线训练定价模型，包括：
7.根据权利要求1所述的一种基于强化学习的定价、分配和重定位联合优化方法，其特征在于，所述在线训练融合重定位的分配模型，包括：
8.一种基于强化学习的定价、分配和重定位联合优化系统，其特征在于，用于实现权利要求1-7任一所述的方法，包括以下模块：
9.一种基于强化学习的定价、分配和重定位联合优化装置，其特征在于，包括：
10.一种计算机可读存储介质，其中存储有处理器可执行的程序，其特征在于，所述处理器可执行的程序在由处理器执行时用于执行如权利要求1-7任一项所述方法。
