1.1 研究背景及意义

近年来，互联网得到迅速发展，衍生的电子商务也越来越普遍，网购也被大多数人所接受，随之带来的是快递物流压力，传统的快递物流模式已无法满足现在的生产生活需求。在物流的仓储拣货阶段，传统的人工拣货已逐渐被仓储机器人拣货代替，智能化仓库已经被大量研究，亚马逊公司装备Kiva机器人的智能化仓库已经带来巨大效益。而快递派送是物流的末端环节，其时效性直接影响客户的满意度，派送环节就是检验快递服务水平和质量的关键。然而，目前中国的快递行业仍然处于严重依赖人工的发展阶段，尤其在配送环节中，每个快递员的配送效率差异很大，浪费的时间和经济代价无法估量。随着近年物联网的兴起，信息技术也被逐渐应用到快递行业中去，便催生了“智能物流”的新兴概念。

其中，无人配送车正是“智能物流”的一个典型代表。作为短途自主配送机器人，路线规划自然是一项必备技能。除了由操作人员预先设定的简单方式之外，现在越来越多的机器人可以参照精准的卫星定位和地图测算，根据行驶过程中景物的变化，实时地智能改变既定路线。路径规划是决递配送路径寻优的核心技术之一，其目的是搜索一条从起始点到目标点确保配送小车能够完成指定配送任务并且能够达到一定的性能指标，类似时间与距离最短，耗能最小等。

随着电子商务的发展，传统的物流己无法适应现代物流所呈现出的品种样式多、批量配送低、批次配送频繁、周期短等特点。多点快递配送系统的应用可以大大提高电商仓储物流工作的效率，缓解当前物流行业供不应求的现状。因此，如何让配送员高效完成配送任务，提高电商的库存管理能力与配载能力是当快递业研究领域的热点之一。当前快递业问题具有物品种类多、存储面积大等特点，如何按照配送需求规划出合理的路径是提高配送员效率的关键。目前快递配送的研究主要集中在节省成本、研究点到点之间，针对具体环境和具体任务实现路径规划的研究较少。

由于路径规划中NP困难的复杂性，传统的路径规划方法计算量大动态的情况下无法达到性能指标。传统的路径规划方法只针对简单的点到且在有些复杂点路径规划问题，不能满足日渐复杂的配送任务需求。现有的A*算法不仅具有启发式算法的高效性，同时也能保证搜寻的路径结果为最短路径。现有的基于线性时序逻辑理论路径规划方法针对静态环境规划出满足任务需求的最优路径，其中结合了Dijkstra算法来进行路径寻优搜索出最优路径。

1.2国内外研究现状

配送任务的路径规划问题，也就是配送者从货物分发处出发，遍历所有派送点，最后回到分发处，找到一条最短的路径，该问题属于典型的旅行推销员问题(travelling salesman problem，TSP)。当前，关于路径规划问题，已经有了一些研究成果。

文献[1]基于Dijkstra算法研究了快递车辆配送路径优化问题，考虑了配送车辆行驶的最大距离以及配送负载约束建立约束条件，从配送起点开始搜索，依次搜索距离当前节点最近的地点作为下一节点，直至遍历所有派送点；文献[2]将A*算法与贪心算法相结合来解决物流配送路径的选择，A*算法加入了启发函数可以提高搜索效率，利用贪心算法思想实现多点派送的目的。但以上这两种方法，都是在经典的针对点对点路径规划算法基础之上，结合贪心算法思想实现多点派送的路径规划任务，该方法很难获得全局最优路径，大多得到的是次优路径，Dijkstra算法能保证两点间路径的最优性，但是难以获得多点快递派送这类复杂任务的最优路径。

针对复杂的任务，比如快递派送的遍历任务、持续监控工厂几个任务点的巡回任务，随着模态逻辑的深入研究，时序逻辑语言，例如计算树逻辑(CTL)和线性时序逻辑(LTL)能够便捷地描述复杂的时序任务，时序逻辑理论在路径规划领域的应用越来越被关注。文献[4]提供了一种方法解决了一类具有时序任务约束的机器人运动规划，文中采用三角分割法对环境进行离散抽象建模，采用LTL公式描述机器人按序访问、巡回等复杂的任务需求，用模型检测工具NUSMV规划出满足任务的离散路径，最后设计控制规则将离散路径转化为连续路径。文献[5]结合Büchi自动机理论，考虑时间权重，设计了最小瓶颈算法搜索出一条耗时最短的最优路径，解决了多点巡回问题。但该方法受任务节点顺序的影响，使得搜索路径并非全局最优，针对此问题，肖云涛，欧林林等人设计了一种扩展乘积自动机方法，确保多点巡回问题，不受任务公式顺序影响，所得路径为全局最优。文献[6]以派送员经过的总路程最短作为目标函数建立数学模型，基于最小生成树的深度优先搜索算法，搜索出满足任务的“亚优解”。但上述方法大多采用的是智能搜索算法，搜索所得路径是次优解，并不能保证是路径最短，而目前基于线性时序逻辑理论的路径规划方法可以满足复杂任务获得最优路径，但难以适用于快递员不断变化的派送环境。