本发明属于机器学习和物流管理的交叉领域,尤其是涉及对未来订单分布进行分析的物流配送调度算法。
背景技术：
互联网、移动营销、新零售的发展，使得o2o即时物流成为一种重要的运营方式。即时物流调度与传统物流的不同在于高波动性、即时性两大特征，要求平台能够在较短的时间内做出物流调度方案，同时还需要根据订单的变化不断更新调度方案。由于订单的高波动性，如果不考虑未来的订单集，会造成调度方案的短视性。但是对于o2o即时物流，其配送规模很大，拥有数量庞大的商家和消费者，通常在一个5km×5km的配送区域内，拥有超过100个商家，近万的消费者，组成一个大规模的配送网络，但对于某个决策时刻点，配送区域内的订单数目一般不到300个，配送网络的连接非常稀疏。对于一个大规模的稀疏网络，要进行高频的订单集实时预测非常困难，因此需要一个新的方法来支持对大规模网络的订单集进行高频的实时预测，并将该预测结果整合到调度模型中，优化调度方案，提升企业运营效率，降低运营成本。
现有的物流调度算法，主要分为两类：静态的调度方案、动态的调度方案。静态的调度方案中，订单不会动态更新，平台只需要做一次决策。动态的调度方案考虑了随时间不断更新的订单，平台会进行多次的决策，给出调度方案。
上述算法大都未考虑未来订单的信息，而目前考虑未来订单的主流方法有两种，第一种方式假定需求服从一定的随机分布，并利用历史数据估计随机分布的参数，第二种方法通过机器学习的方法去预测网络中每一个连接发生的概率。但是这些方法均不适用于大规模的稀疏网络。
技术实现要素：
针对现有技术存在的问题，本发明的目的在于设计提供一种基于场景推演的物流配送调度算法的技术方案。
本发明采用如下技术方案：
确定调度决策周期时长τa，场景片段时长τs，当前决策时刻t，向前追溯的历史场景数目p；一个订单c包含起点、终点、产生时间等信息，提取时刻t所有未完成的订单组成的订单集
具体步骤如下：
1.数据准备:
1.1确定调度决策周期时长τa，场景片段时长τs，当前决策时刻t，向前追溯的历史场景数目p。
1.2提取时刻t未完成的订单集
1.3提取时刻t的场景特征集
1.4对于时刻
2.场景计算:
2.1对于时刻j，计算时刻t的场景与时刻j的场景的特征子集
2.2时刻t的场景与时刻j的场景距离是多类特征的距离的加权平均
其中
2.3选取与当前场景st距离最小的场景sj*，其中
2.4提取时刻j*往后时长τs的订单集
3.根据时刻t未完成的订单集
4.根据所述调度目标信息，利用启发式求解算法生成物流配送调度方案。
上述方案中，1.1所述的调度决策周期时长τa指平台两次物流调度决策的间隔。比如平台每隔5分钟对骑手进行一次调度，τa＝5分钟。τa的取值范围可以是单位为分钟、小时的任意数值。
上述方案中，1.1所述的选取场景片段的时长τs是指要预测的未来订单场景的时间长度，τs要大于或等于τa。比如预测未来30分钟的订单场景，τs＝30分钟。
上述方案中，1.3所述的场景特征集包括但不限于外部环境特征，时刻t往前时长τs的订单分布，时刻t往后时长τs的订单分布。
上述方案中，1.3所述的场景特征集中，由于时刻t往后时长τs的订单分布是未知的，可以将服务区域分网格，对每个网格进行需求预测，需求预测算法可以采用的任意现有的需求预测算法。
上述方案中，2.1所述的距离计算采用任意计算向量的距离方法，包括但不限于余弦距离、欧式距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离。
上述方案中，3所述的配送调度模型的调度目标包括但不限于，最小化配送成本，最大化配送利润，最大化订单准时率。
上述方案中，4所述生成物流配送调度方案的算法采用任意求解整数规划的启发式算法，包括但不限于禁忌搜索、遗传算法、蚁群算法、模拟退火算法。
本发明设计了一种基于场景推演的物流配送调度方案，主要特点是利用当前的场景与历史场景库的相似度进行推演，从而对大规模网络的订单集进行高频实时预测，并将此整合到物流配送决策过程中，实现高频调度，进行全局优化。
附图说明
图1是本发明实施例的基于场景推演的物流配送调度算法流程图。
具体实施方式
下面结合附图和具体实施例对本发明进一步作详细说明.这些实施例仅用于解释和说明本发明的内容，不作为对本发明的保护范围限定。本发明的范围由权利要求书来限定，其中某些要素的改变、替换等是都包含在本发明的保护范围之内。
实施例一
基于场景推演的物流配送调度算法流程图如图1所示。某大型外卖配送门店，数据库内有用2017年5月1日-2017年6月14日的运营记录。现计划对该门店提供物流配送调度方案。每个调度决策周期长度τa为5分钟，场景片段的长度τs为30分钟，追溯的场景数目p为20000。
提取时刻t未完成的订单集
提取时刻t外部环境特征
网格化配送区域，将订单的配送区域划分为l个网格。
提取时刻t往前时长τs订单，并统计每个网格到每个网格的订单数目，得到的订单分布特征如下
对于历史场景库中每一个时刻j，提取场景的外部环境特征
对于历史场景库中每一个时刻j，提取时刻j往前时长τs的订单分布特征
利用闵可夫斯基距离公式计算时刻t与历史场景库中每一个时刻j的距离
选取距离最小时刻j*满足
提取场景库中时刻j*往后时长τs的订单集
基于最小化配送成本的目标函数，采用模拟退火算法的方法对问题进行求解，给出最优的决策方案。
实施例二
某大型o2o即时平台共有超过10万个门店，数据库内拥有2016年1月1日-2019年2月31日所有门店的运营记录。现计划对包含22个门店的一个区域提供物流配送调度方案。每个调度决策周期长度τa为5分钟，场景片段的长度τs为30分钟，追溯的场景数目p为50000。
提取时刻t未完成的订单集
提取时刻t外部环境特征
网格化配送区域，将订单的配送区域划分为l个网格。
提取时刻t往前时长τs订单，并统计每个网格到每个网格的订单数目，得到的特征如下
基于需求预测算法，预测时刻t往后时长τs的订单分布，即预测每个网格的订单数目，得到的特征如下
对于历史场景库中每一个时刻j，提取场景j的外部环境特征
对于历史场景库中每一个时刻j，提取时刻j往前时长τs的订单分布特征
对于历史场景库中每一个时刻j，提取时刻j往后时长τs的订单分布特征
利用余弦距离公式计算当天与过去各天的距离
选取距离最小时刻j*满足
提取场景库中时刻j*往后时长τs的订单集
基于最小化配送成本的目标函数，采用禁忌搜索的方法对问题进行求解，给出最优的决策方案。
1.一种基于场景推演的物流配送调度算法，其特征在于，该方法具体为：
确定调度决策周期时长τa，场景片段时长τs，当前决策时刻t，向前追溯的历史场景数目p；一个订单c包含起点、终点、产生时间等信息，提取时刻t所有未完成的订单组成的订单集
2.根据权利要求1所述的方法，其特征在于，将历史订单集作为对未来订单集的预测。
3.根据权利要求1所述的方法，其特征在于，针对每一个决策时刻t，提取当前场景的属性特征集st，特征集可以由多种不同类型的特征子集
4.根据权利要求1所述的方法，其特征在于，场景st和场景sj距离的计算综合了多维特征的距离
其中
5.根据权利要求1所述的方法，其特征在于，计算场景st和场景sj的特征子集
6.根据权利要求1所述的方法，其特征在于，选取与当前场景st距离最小的场景
7.根据权利要求1所述的方法，其特征在于，构建调度模型时，考虑的订单集同时包括时刻t未完成的订单集
8.根据权利要求1所述的方法，其特征在于，采用的调度目标信息包括但不限于最小化配送成本，最大化配送利润，最大化订单准时率。
9.根据权利要求1所述的方法，其特征在于，采用的启发式算法包括但不限于禁忌搜索、遗传算法、蚁群算法、模拟退火算法。
技术总结