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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2148235