基于强化学习的在线订单配送时隙运能分配

陈淮莉+吴梦姣

摘要：为解决在线订单配送效率低、时隙运能分配不均衡和顾客满意度不高的问题，考虑价格和交付期对消费者选择行为的影响建立Logit模型，采用强化学习结合时隙运能分配特点对到达的订单群进行运能分配.算例模拟结果证明：采用强化学习能使每个时隙每辆车的运能分配均衡，且分配方法符合消费者的行为偏好；消费者对时隙价格偏好程度越高商家收益就越低.结论验证了采用强化学习解决时隙运能分配问题的可行性和有效性.

关键词： 时隙； 运能配置； Logit模型； 强化学习

中图分类号： F274； F502

文献标志码： A

Abstract： In order to solve the lower efficiency of online order delivery， the unbalanced capacity allocation of time slots and the lower customer satisfaction， the Logit model is established considering the influence of the price and lead time on the selection behavior of consumers. Considering the character of capacity allocation of time slot， the orders are assigned to the vehicles by the reinforcement learning. The example simulation results show that： the capacity of every time slot and every vehicle can be balanced by the reinforcement learning and the allocation method accords with the behavioral preference of consumers； the more attention consumers take to the price of time slot， the lower profit retails can get. The conclusion

verifies feasibility and effectiveness of adopting the reinforcement learning to solve the capacity allocation of time slot.

Key words： time slot； capacity allocation； Logit model； reinforcement learning

0 引 言

電子商务的兴起给传统零售业带来了新的发展方向，也给订单配送提出了更高的要求.除订单价格影响消费者的选择行为外，订单的交付期也成为消费者考虑的重要因素.时隙（time slot）在电子商务中指网络零售商提供给消费者选择的订单送达的交货时间窗[1]，如亚马逊、京东商城、当当网都向消费者提供了配送时隙选项，其中京东的“极速达”保证在服务时间（3 h）内将货物送至客户手上，但收费往往是常规配送的几倍.通过给消费者提供订单配送时隙表安排配送作业，一方面有利于消费者根据自身情况安排接收，提高客户满意度，另一方面有利于协调物流服务商的作业安排，合理规划车辆运能和配送时间线路，提升竞争能力.虽然电商的差异化交付期承诺可以满足消费者需求，但在承诺交付期时需根据自身车辆运能情况进行权衡.

CAMPBELL等[2]研究发现时隙价格会影响消费者的选择行为和商家的最终收益，采用价格激励方法可调控消费者的选择行为.在现实配送中，存在预先知道配送地点但对配送时间不明的问题，对此SROUR等[3]提出了混合整数规划模型，与传统的配送方式对比，该模型很大程度上提高了配送效率.陈淮莉等[4]从消费者选择模型出发建立了收益模型，通过求解模型得出区域和时隙宽度对消费者时隙选择行为的影响.李科峰等[5]研究了基于时隙配送的订单履约方法，并从时隙配送的角度建立了优化模型.元鹏鹏等[6]考虑时隙替代的客户选择行为，并结合交付期敏感度和时隙运能等因素建立了规划模型，对比分析了各种因素对收益的影响.

在实际的订单时隙管理中，订单接收和配送不仅需要考虑时隙定价，还需要结合时隙运能要求进行综合分析.强化学习（Reinforcement Learning，RL）是基于马尔科夫过程理论的随机动态系统的最优决策过程，是解决订单配置问题的一种较好的求解方法.郝鹃等[7]基于收益管理的思想研究了不确定环境下按订单生产（Made To Order， MTO）的企业的订单接收问题，把订单类型、订单价格和订单交付期作为系统状态划分标准，提出了解决订单接收问题的RL算法，并证明了算法的可行性.赵绍航[8]采用RL中的SMART（SemiMarkov Average Reward Technique）确定供应链库存中货物订购的必要性及订购的数量.SMART能够求解状态集和动作集都较大的RL问题.

电商订单配置具有动态性.刘成丽[9]在进行突发事件的动态管理时，结合博弈论和RL的思想，从突发事件的紧急程度、事件队列等方面对动态任务分配进行建模，决定处理突发事件的先后顺序使平均任务效益最大.王金田[10]提出基于模拟退火的Q学习比普通的Q学习更适合解决电商的动态定价问题，从单销售商定价到双销售商定价进行订单动态管理.黄云霞[11]在解决信号接入问题时，运用改进的Q学习分析了用户接入共享空闲信道和独占空闲信道的方式，研究了双信道内无线网络动态频谱分配，提出了两种接入方式下的协作ε贪心算法，显著提高了信号接入效率.MICHAEL[12]运用RL的方法解决网络信息配置过程中的定价和能力配置问题，并与遗传算法进行对比.

综上，已有的订单时隙研究主要集中在时隙定价上，是通过静态定价模型引导消费者的时隙选择行为，忽略了时隙的运能限制和订单处理过程的动态性.RL的求解方式能够较好地体现订单动态性的特征，因此本文基于电商订单时隙配送的特点，并考虑消费者选择时隙的行为和时隙运能的限制，通过RL解决时隙运能的动态分配问题，期望得到最佳的分配策略，为电商运能分配决策提供参考.

1 基于RL的订单处理过程

在线订单处理流程主要分为订单提交、订单分配和订单配送等3个过程.以京东商城为例：消费者挑选完商品后填写配送地址，选择配送时隙，提交订单并付款；京东配送中心根据配送地址和时隙将订单分配给特定的运输车辆，然后进行商品分拣、出库，并装入特定车辆进行配送.在线订单处理流程是一个动态决策过程，当时隙运能固定时，当前订单分配结果直接影响到下一订单的分配，符合Markov决策过程.RL作为Markov决策过程的解决方案，能够与外界环境发生互动，并能根据订单特性不断选择较好的策略，强化此策略的动作选择.

1.1 参数定义

消费者选择概率是电商预测消费者行为的方法，通过下单时间和客户对价格、交付期的偏好，预测消费者选择特定时隙的概率.本文把消费者选择概率默认为系统预测消费者选择订单配送时隙的概率.

1.3 RL

从RL算法的角度看，每个随机到达的订单都使系统进入一个新状态.在每个状态下，系统对当前订单有两种動作选择，即接收订单或放弃订单.然而，由于时隙的特殊性，系统还需要分配订单配送时隙和配送车辆，然后进入下一状态，对下一订单再选择动作，即分配时隙和车辆.由此，定义RL中的状态集、动作集、即时收益函数和值函数的更新规则.

当前订单的状态值Q（sq，atm）=订单配送计划表×收益，状态集系统根据当前订单的动作选择再次更新配送计划表和已经获得的收益.

1.4 订单处理过程

综上，基于RL的订单时隙运能配置算法主要过程如下：输入运能限制表和即时收益矩阵；初始化动作值函数和计划表；以RL训练次数的设定值为循环迭代数处理订单.每个订单的处理过程（即动作选择过程）分为3步：第1步，根据交付期和订单价格，基于Logit模型在动作集中选择动作，得到收益rqt.如果该订单被配置时隙t和车辆m后未超过车辆m运能配置的最大值，则选择动作atm；否则，系统自动选择同时隙的其他车辆作为该订单的配置车辆；若选择此动作后，超过时隙运能最大限制，则系统放弃订单.第2步，由于订单配置过程中的状态转移概率为1，所以下一状态即为订单列表的下一订单，根据式（1）计算Q（sq，atm）.第3步，令sq←sq+1，计算下一订单.直到所有订单处理完毕.

按照上述算法流程，系统根据订单q的价格、配送时隙、已有计划表、运能限制等选择订单q的动作.动作结束后，系统更新计划表.计划表更新后处理下一订单，根据订单q+1的价格、配送时隙、更新后的计划表、运能限制等选择订单q+1的动作，再次更新计划表.以此循环不断更新计划表，直到处理完所有订单得到最终计划表.

1.5 探索空间

在RL中，

通常用ε贪心策略解决探索未知空间和现有知识利用问题，即以概率ε随机选择行动，以概率1-ε选择最优的行动.一方面鉴于电商消费者选择的特性，选择Logit模型作为选择最优动作的方法，这是因为与贪心策略相比，Logit模型能更好地描述消费者的时隙选择行为，不以回报值最大作为探索未知空间和利用现有知识的依据，同时，既考虑选择概率大的配送时隙也考虑选择概率小的配送时隙，甚至考虑放弃时隙选择的可能性；另一方面结合Logit模型，设置探索空间阈值，在数据量大时能够更快地得出结果，保证结果收敛且收益值较高.

2 算 例

假设配送时间为8：00—20：00，时隙长度为2 h，共有4辆配送车辆.车辆和时隙的初始运能分配见表1.每辆车每个时隙的运能限制都为50个单位，如初始运能分配计划中车辆1在8：00—10：00内需要完成40个订单的配送，且车辆1在此时隙最多能承担50个单位货物的配送.假设在4：00—8：00内按照泊松分布到达300个订单，对这部分订单进行运能配置.采用MATLAB 2013a进行算例模拟.设置RL训练次数为500，α=0.99，γ=0.98，Uq0=10，β1=0.1，β2=0.1，服从泊松分布的λ=3.

2.1 运能分配分析

在订单分配过程中，电商需要权衡利润与成本的关系.对临时到达的订单商家会选择把该订单加入已有的配送任务计划中，或当订单规模达到一定程度后，考虑增加新的配送任务，充分利用已有的计划运能或增加新的运能，使配送成本不至于过高，也使每辆车每时隙的任务分配均衡.经过模拟运行，得到各时隙的订单接收情况，表2是运行结果，300个订单中放弃24个订单，剩余的276个订单得到运能分配.

每时隙每辆车并不都是有初始任务分配的，如对于时隙14：00—16：00，车辆1是没有配送任务的，车辆运能浪费.通过RL，对临时到达的订单进行分配后车辆和时隙的运能达到了均衡，说明RL用于解决运能分配问题具有可行性.从结果可知，大多数订单选择时隙8：00—10：00，此时隙的运能到达限制，得到了充分利用，时隙10：00—12：00的订单量次于时隙8：00—10：00的订单量，这符合消费者的实际需求.

2.2 价格偏好对总收益的影响

客户对价格的偏好程度会影响商家的总收益.图1是基于RL进行运能分配时β2对订单总收益的影响.从图1可明显看出，β2值越大，总收益越小.这说明，β2值越大消费者对价格的偏好程度越高.此类消费者为价格敏感型消费者，表现为某时隙价格越高，消费者对此时隙的选择可能性就越小.

高价格订单的消费者对交付期敏感，对时隙价格不敏感，而低价格订单的消费者则相反.对此，考察订单等级与消费者放弃订单次数的关系.按照订单价格细分订单等级：A等级订单的价格服从均匀分布[50，150]，B等级订单的价格服从均匀分布（150，250]，C等级订单的价格服从均匀分布（250，350].对消费者放弃订单次数进行模拟，订单等级越高β2值越小.图2是消费者放弃订单次数频数直方图，放弃订单次数在20到100之间，对频数不超过10的数据未在图中标示.

从图2的结果可知，受运能的限制，消费者放弃这3个等级订单的次数较为稳定，大部分在[50，80）中.A等级订单属于低价格等级订单，消费者放弃该类订单的次数比其余两类订单的少；C等级订单价格较高，消费者放弃该类订单的次数较多.C等级订单的消费者对时隙价格不敏感，其选择行为主要是由时隙的交付期和运能决定的，A等级订单消费者则相反.

综上，提出如下建议：对网络零售商配送运能不足的问题，通过预测订单量和时隙选择行为进行运能规划，提前租赁车辆填补运能，做到及时发货、准时配送；通过时隙定价均衡时隙运能分配，降低物流人员的工作压力；采用低价促销、组合促销等吸引消费者购物，增加边际效益；提高信息技术水平，建设智能化仓库，加快订单处理速度.

3 结束语

根据消费者对网络零售配送时隙的偏好，分析影响偏好的因素，建立Logit模型并作为强化学习（RL）动作挑选的策略，同时设置运能配置规则.通过算例分析发现：在B2C环境的订单运能分配中采用RL方法能够使每辆车每时隙的运能分配得到均衡，并且符合消费者对交付期的偏好；消费者对商品价格和时隙价格的偏好程度越高商家收益就越低，对整体价格偏低的订单，建议商家通过接收更多此类订单来增加边际效益.算例分析得出的结果与市场经济现象相符合，说明基于RL解决在线订单配送时隙运能配置问题是科学和有效的.在今后的研究中，希望加入运输成本因素，考虑运能外包或租用运输车辆的情况；同时可根据消费者的订单配送需求的紧急情况，对订单进行分类处理，把运能优先分配给愿意额外多支付配送费用的加急订单.

参考文献：

[1]AGATZ N， CAMPBELL A， FLEISCHMANN M， et al. Time slot management in attended home delivery[J]. Transportation Science， 2011， 45（3）： 435449. DOI： 10.1287/trsc.1100.0346.

[2]CAMPBELL A M， SAVELSBERGH M W P. Decision support for consumer direct grocery initiatives[J]. Transportation Science， 2005， 39（3）： 313327. DOI： 10.1287/trsc.1040.0105.

[3]SROUR F J， AGATZ N， OPPEN J. Strategies for handling temporal uncertainty in pickup and delivery problems with time windows[J/OL]. Transportation Sciences， Articles in Advance： 117[20160514]. http：//dx.doi.org/10.1287/trsc.2015.0658.

[4]陳淮莉， 马娟娟. 区域和时隙宽度影响下网络零售商配送时隙激励定价[J]. 上海海事大学学报， 2015， 36（1）： 3337. DOI： 10.13340 /j.jsmu.2015.01.006.

[5]李科峰， 陈淮莉， 孔德宽， 等. 网购环境下基于时隙配送的时效产品订单履约方法[J]. 华中师范大学学报（自然科学版）， 2015， 49（4）： 557561.

[6]元鹏鹏， 郝杨杨， 李恒. 客户选择网络零售配送时隙动态规划模型[J]. 辽宁工程技术大学学报（自然科学版）， 2015， 34（11）： 13161323. DOI： 10.11956/j.issn.10080562.2015.11.020.

[7]郝鹃， 余建军， 周文慧. 基于平均强化学习的订单生产方式企业订单接受策略[J]. 计算机应用， 2013， 33（4）： 976979. DOI： 10.3724 /SP.J.1087.2013.00976.

[8]赵绍航. 供应链联合补充问题的强化学习算法[D]. 哈尔滨： 哈尔滨理工大学， 2015.

[9]刘成丽. 应急任务动态分配和协作研究[D]. 武汉： 华中科技大学， 2012.

[10]王金田. 基于强化学习的电子销售市场动态定价研究[D]. 合肥： 合肥工业大学， 2009.

[11]黄云霞. 基于改进Q学习的认知无线网络动态频谱接入算法研究[D]. 成都： 电子科技大学， 2009.

[12]MICHAEL S. Dynamic pricing and automated resource allocation for complex information services： reinforcement learning and combinatorial auctions[M]. Germany： Johann Wolfgang Goethe University， 2007： 89132.

[13]聂冲， 贾生华. 离散选择模型的基本原理及其发展演进评介[J]. 数量经济技术经济研究， 2005（11）： 151159.

[14]YANG X， STRAUSS A K， CURRIE C S M， et al. Choicebased demand management and vehicle routing in efulfillment[J]. Transportation Science， 2016， 50（2）： 473488.

（编辑 赵勉）