【摘要】：近年來隨著互聯(lián)網(wǎng)的發(fā)展,特別是O2O模式的普及,物流業(yè)規(guī)模逐步增大。隨之而來的是業(yè)務(wù)員配送壓力的增大,他們目前面臨著兩個難題:第一個難題是隨著配送地址的增加,以往業(yè)務(wù)員通過經(jīng)驗或者直覺來選擇配送路徑的方法失效,由此導(dǎo)致配送物品時,路線選擇錯亂,效率低下且浪費能源。第二個難題是業(yè)務(wù)員面臨實時請求的增加,需要在短時間內(nèi)規(guī)劃出行路線。對于很多O2O業(yè)務(wù),用戶下單后,平臺會實時安排業(yè)務(wù)員派送物品,如果花費過多時間考慮地點派送順序,會導(dǎo)致服務(wù)效率降低。而目前市面上所有的地圖軟件都沒有提供實時的多站點路徑規(guī)劃功能,無法滿足用戶多方面的出行需要。本文通過TSP算法與在線電子地圖相結(jié)合的方式,實現(xiàn)優(yōu)化路徑的規(guī)劃和路線的可視化。為了解決以上存在的問題,本文提出多站點高效導(dǎo)航算法以及多站點高效導(dǎo)航系統(tǒng)。算法分為規(guī)劃算法和導(dǎo)航算法兩個部分,規(guī)劃算法設(shè)計中,本文以K-OPT算法作為基礎(chǔ),首先綜合多種初始環(huán)路構(gòu)造方法的優(yōu)缺點以及適用范圍,選擇適合開發(fā)環(huán)境的初始路徑構(gòu)造算法。其次,對算法主要參數(shù)K進行擇優(yōu),通過實際測試與對比,最后論證得出當K=4時,算法具有優(yōu)化性價比。最后,本文對工程環(huán)境中的距離矩陣生成方式進行改進,提出在距離矩陣中使用兩點間的曼哈頓距離矩陣替代兩點間的實際距離,并且通過測試證明,該改進在可接受的精度范圍內(nèi),能大大縮短算法運行時間。導(dǎo)航算法設(shè)計中,本文提出一個考慮實時路況的A*算法,通過改進估價函數(shù),使算法能在搜索時避開擁堵路段,為多站點高效導(dǎo)航系統(tǒng)中兩點間的路徑導(dǎo)航提供支持�；谏鲜鏊惴�,本文設(shè)計了多站點高效導(dǎo)航系統(tǒng),系統(tǒng)采用MVC架構(gòu),結(jié)合百度地圖API,實現(xiàn)了對地址集的優(yōu)化路徑的規(guī)劃以及結(jié)果路線展示,同時為用戶提供導(dǎo)航、路徑分析、快速通知等多種功能。接著本文介紹了基礎(chǔ)模塊,規(guī)劃模塊,附加功能模塊以及后臺分析模塊的具體實現(xiàn)細節(jié)。最后,通過實驗對本文提出的系統(tǒng)和算法進行測試,驗證系統(tǒng)和算法的性能。
[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.
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：F259.2;TP301.6

【參考文獻】

相關(guān)期刊論文 前10條

1 張波;趙雙明;;基于Android平臺的百度地圖開發(fā)研究[J];軟件導(dǎo)刊;2015年07期

2 程鋼;賈寶;毛明楷;梁曉莉;郭玉祥;;國內(nèi)在線地圖服務(wù)應(yīng)用現(xiàn)狀分析與評價[J];地理空間信息;2013年06期

3 程鋼;郭玉祥;賈寶;毛明楷;;國內(nèi)主流在線地圖API分析及優(yōu)化對策研究[J];測繪工程;2013年06期

4 孫迪;李沛鴻;;百度地圖API在WebGIS中的應(yīng)用[J];河南科技;2013年22期

5 吳華鋒;陳信強;毛奇凰;張倩楠;張壽春;;基于自然選擇策略的蟻群算法求解TSP問題[J];通信學(xué)報;2013年04期

6 戈艷艷;;基于eM-Plant與動態(tài)規(guī)劃算法的TSP問題應(yīng)用研究[J];物流工程與管理;2012年03期

7 王芳;;Google地圖開發(fā)研究[J];計算機與數(shù)字工程;2010年03期

8 彭璇;吳肖;;Google Map API在網(wǎng)絡(luò)地圖服務(wù)中的應(yīng)用[J];測繪信息與工程;2010年01期

9 陳濤;張思發(fā);;分支限界法求解實際TSP問題[J];計算機工程與設(shè)計;2009年10期

10 喬彥平;張駿;;基于一種改進遺傳模擬退火算法的TSP求解[J];計算機仿真;2009年05期

相關(guān)碩士學(xué)位論文 前2條

1 朱林杰;基于TSP的遺傳算法優(yōu)化研究[D];大連理工大學(xué);2007年

2 于龍振;基于Lin-Kernighan改進型算法的可視化TSP處理軟件的實現(xiàn)[D];青島大學(xué);2006年

，

本文編號：2148235