多站点高效导航算法研究与实现

发布时间：2018-07-27 15:15

【摘要】：近年来随着互联网的发展,特别是O2O模式的普及,物流业规模逐步增大。随之而来的是业务员配送压力的增大,他们目前面临着两个难题:第一个难题是随着配送地址的增加,以往业务员通过经验或者直觉来选择配送路径的方法失效,由此导致配送物品时,路线选择错乱,效率低下且浪费能源。第二个难题是业务员面临实时请求的增加,需要在短时间内规划出行路线。对于很多O2O业务,用户下单后,平台会实时安排业务员派送物品,如果花费过多时间考虑地点派送顺序,会导致服务效率降低。而目前市面上所有的地图软件都没有提供实时的多站点路径规划功能,无法满足用户多方面的出行需要。本文通过TSP算法与在线电子地图相结合的方式,实现优化路径的规划和路线的可视化。为了解决以上存在的问题,本文提出多站点高效导航算法以及多站点高效导航系统。算法分为规划算法和导航算法两个部分,规划算法设计中,本文以K-OPT算法作为基础,首先综合多种初始环路构造方法的优缺点以及适用范围,选择适合开发环境的初始路径构造算法。其次,对算法主要参数K进行择优,通过实际测试与对比,最后论证得出当K=4时,算法具有优化性价比。最后,本文对工程环境中的距离矩阵生成方式进行改进,提出在距离矩阵中使用两点间的曼哈顿距离矩阵替代两点间的实际距离,并且通过测试证明,该改进在可接受的精度范围内,能大大缩短算法运行时间。导航算法设计中,本文提出一个考虑实时路况的A*算法,通过改进估价函数,使算法能在搜索时避开拥堵路段,为多站点高效导航系统中两点间的路径导航提供支持。基于上述算法,本文设计了多站点高效导航系统,系统采用MVC架构,结合百度地图API,实现了对地址集的优化路径的规划以及结果路线展示,同时为用户提供导航、路径分析、快速通知等多种功能。接着本文介绍了基础模块,规划模块,附加功能模块以及后台分析模块的具体实现细节。最后,通过实验对本文提出的系统和算法进行测试,验证系统和算法的性能。
[Abstract]:In recent years, with the development of Internet, especially the popularization of O 2 O mode, the scale of logistics industry is gradually increasing. With the increase of distribution pressure, they are facing two difficult problems. The first problem is that with the increase of distribution address, the methods used by salespeople to choose the distribution path through experience or intuition have failed. This leads to misalignment, inefficiency and a waste of energy when delivering goods. The second problem is that salespeople are faced with an increase in real-time requests and need to plan their travel routes in a short period of time. For many O2O services, the platform will arrange the delivery of goods in real time after the user places an order. If too much time is spent considering the delivery order of the location, the service efficiency will be reduced. At present, all the map software on the market does not provide real-time multi-site path planning function, which can not meet the needs of users in many aspects of travel. In this paper, the optimal path planning and route visualization are realized by the combination of TSP algorithm and online electronic map. In order to solve the above problems, this paper proposes a multi-site efficient navigation algorithm and multi-site efficient navigation system. The algorithm is divided into two parts: programming algorithm and navigation algorithm. In the design of the programming algorithm, based on the K-OPT algorithm, this paper first synthesizes the advantages and disadvantages of various initial loop construction methods as well as the applicable scope. Select the initial path construction algorithm suitable for the development environment. Secondly, the main parameter K of the algorithm is selected. Through the actual test and comparison, it is proved that when K = 4, the algorithm has the optimized performance-to-price ratio. Finally, this paper improves the distance matrix generation method in engineering environment, and proposes to replace the actual distance between two points by Manhattan distance matrix between two points in the distance matrix. The improvement can greatly shorten the running time of the algorithm within the acceptable precision range. In the design of navigation algorithm, this paper proposes an A * algorithm considering real time traffic conditions. By improving the evaluation function, the algorithm can avoid congested sections in search and provide support for the path navigation between two points in a multi-site efficient navigation system. Based on the above algorithm, this paper designs a multi-site efficient navigation system. The system uses MVC architecture and Baidu map API, realizes the optimization path planning and the result route display of address set, and provides the navigation and path analysis for users at the same time. Quick notification and other functions. Then this paper introduces the implementation details of basic module, planning module, additional function module and background analysis module. Finally, the system and algorithm proposed in this paper are tested by experiments to verify the performance of the system and algorithm.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：F259.2;TP301.6

【参考文献】