基于线性时序逻辑的移动端快递派送路径规划  

Express delivery path planning for mobile terminals based on linear temporal logic

作　　者：禹鑫燚[1] 郭永奎[1] 欧林林[1] 汪涛 卢靓 张爱美 Yu Xinyi Guo Yongkui Ou Linlin Wang Tao Lu Liang Zhang Aimei(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310000)

机构地区：[1]浙江工业大学信息工程学院,杭州310000

出　　处：《高技术通讯》2017年第6期544-553,共10页Chinese High Technology Letters

基　　金：863计划(2014AA041601-05);浙江省公益项目(2016C31064);浙江省自然科学基金(LY15F030015)资助项目

摘　　要：研究了快递派送的路径规划。针对目前快递派送任务点较多,快递员不熟悉派送区域的问题,提出了一种基于线性时序逻辑(LTL)的移动端多点快递派送路径规划方法。该方法利用移动端的百度地图应用包实现快递员的定位与导航任务,提出两层(顶层、底层)规划策略。顶层规划避开百度地图实际道路环境繁琐又庞大的建模,将快递派送问题转化为旅行推销员问题(TSP),仅将快递员派送任务地点建模为一个有限状态的加权切换系统,状态之间的切换权重基于百度地图的自驾导航距离,而非简单的直线距离,以达到底层规划结果符合实际环境,确保最后搜索的路径最优性,同时利用线性时序逻辑语言描述多点快递派送任务,从而将切换系统信息与派送任务信息相融合,构建一个任务可行网络拓扑,并在该网络拓扑上基于Dijkstra算法搜索出快递员离散的最优路径。底层规划完成离散路径的连续化,离散路径的任意相邻任务点间的路径规划基于百度地图实现,从而实现顶层规划的离散路径连续化,获得快递员可派单的实际派送路线。实验结果表明该方法能够解决多点派送任务与派送区域受约束的问题,并保证快递员派单路径的最优性。The path planning of express delivery was studied. Based on linear temporal logic （ LTL）, a multi-point express delivery path planning method for mobile terminals was proposed to solve the problems of large number of delivery points in the delivery daea and the courier＇ low familiarity with the delivery area. The method solves the problems of location and navigation by using the development package of the Baidu map on mobile phones. The proposed method can be divided into top path planning and bottom path planning. The top path planning translates the express delivery problem into the traveling salesman problem （TSP）. For avoiding the difficult and huge modeling of the actual road environment in the Baidu map, a weighted finite-state transition system is constructed by the express delivery locations. The transition weights between the states are on the basis of driving distance of the Baidu map rather than the straight-line distance, so that the bottom path planning results meet the actual situation and its optimality is guaranteed. The multi-point express delivery task is described by a linear temporal logic formula. Then, a feasible network topology related to the task is built by combining the above transition system with a linear temporal logic formula. The discrete optimal path of the courier can be obtained by using the Dijkstra algorithm in the network topology. For the bottom path planning, the actual continuous path between any two adjacent path points of the discrete path is generated based on the Baidu map. Thus, the discrete path in top path planning is translated to continuous trajectory to satisfy the courier express delivery task. The experimental results show that the proposed method can solve the delivery path planning problem of the large number of delivery points and the familiarity restriction of the courier for the delivery area, which ensures delivery route optimality.

关 键 词：快递派送 路径规划 线性时序逻辑(LTL) 移动端 

分 类 号：F252[经济管理—国民经济] TP301.6[自动化与计算机技术—计算机系统结构]