本文選題：TSP問題 + 遺傳算法��； 參考：《哈爾濱工業(yè)大學(xué)》2017年碩士論文

【摘要】：2016年,斯坦福大學(xué)價(jià)值鏈創(chuàng)新倡議研究中心與美國郵政服務(wù)局督察長辦公室聯(lián)合發(fā)布了《最后一英里快遞技術(shù)顛覆與創(chuàng)新白皮書》。白皮書中指出,四項(xiàng)新型的技術(shù)可能支撐物流行業(yè)帶來新的發(fā)展,即優(yōu)化商品配送流程的高級算法,參與配送系統(tǒng)的無人機(jī)技術(shù),參與機(jī)械分揀的機(jī)器人技術(shù),以及把人工從物流系統(tǒng)中解放出來的無人駕駛汽車技術(shù)。本文即針對優(yōu)化商品配送流程的高級算法,基于GA算法,結(jié)合實(shí)際解決配送過程中的TSP問題。物流行業(yè)中,物流的成本的問題一直是最重要的問題之一,過高的物流成本也是限制其行業(yè)發(fā)展的最大問題之一。要有效減少運(yùn)輸成本與配送成本,可以進(jìn)行配送渠道的優(yōu)化,配送人員的優(yōu)化,配送效率的提高等等方面來進(jìn)行。其中最容易實(shí)現(xiàn)的,不需要高成本的就是配送車輛的運(yùn)輸線路的優(yōu)化。由此,本文建立了基于實(shí)際配送問題中的TSP問題的配送路徑優(yōu)化模型,并通過用改進(jìn)的遺傳算法結(jié)合該實(shí)際問題來解決。本文利用遺傳算法解決實(shí)際配送過程中帶有限制條件的多目標(biāo)TSP問題,并針對實(shí)際問題提出改良算法與解決方案,保證可實(shí)現(xiàn)最優(yōu)解的前提下提高算法效率與收斂速度。論文主要研究內(nèi)容如下:1.對TSP問題與遺傳算法進(jìn)行研究。研究遺傳算法與TSP問題的歷史和研究現(xiàn)狀,介紹TSP問題的數(shù)學(xué)模型和遺傳算法的基本算例,對遺傳算法和改進(jìn)的遺傳算法進(jìn)行一定的歸納和分析,為后續(xù)工作提供前提條件。以遺傳算法理論為基礎(chǔ)建模并完成課題工作。2.建立基于路徑長度和時(shí)間為目標(biāo)的多目標(biāo)實(shí)際配送TSP問題數(shù)學(xué)模型,并實(shí)現(xiàn)實(shí)際物流配送問題的求取,得到最優(yōu)路徑。研究實(shí)際道路路徑的實(shí)現(xiàn)方案,解決實(shí)際道路地圖中道路路徑與消耗時(shí)間的建模,在遍歷道路和小區(qū)內(nèi)不同路段時(shí),車輛具有不同速度。在多目標(biāo)TSP問題上,加入容積的限定,當(dāng)容積到達(dá)閾值時(shí)返回,即容積限定的車輛TSP問題,在該限制條件下做出相應(yīng)解決方案并實(shí)現(xiàn)最優(yōu)路徑的計(jì)算。仿真紅綠燈等待,路況擁堵等可變因素,兩點(diǎn)間的時(shí)間結(jié)合實(shí)際問題計(jì)算得出。同時(shí)保證算法不進(jìn)行過多計(jì)算,保證算法的效率和收斂性。在仿真中根據(jù)實(shí)際應(yīng)用計(jì)算中出現(xiàn)的問題進(jìn)行算法的改進(jìn),保證仿真路徑和仿真時(shí)間與真實(shí)路徑真實(shí)時(shí)間的貼合,減小誤差。3.結(jié)合實(shí)際問題進(jìn)行算法的改進(jìn)。解決跨道路間難于通過變異得到最優(yōu)序列的問題,研究適應(yīng)于實(shí)際配送問題的適應(yīng)度函數(shù)與選擇算子,在實(shí)際問題中更優(yōu)質(zhì)地產(chǎn)生子代,同時(shí)更高效地選擇出優(yōu)秀子代。研究適用于城區(qū)道路的初始路徑解,提高基于道路路徑的初始解的質(zhì)量。研究適用于實(shí)際配送中的編碼方案,在訂單,路徑,區(qū)域,目標(biāo)等多個(gè)信息中確定最優(yōu)的編碼方案。本文提出了實(shí)際配送過程中的TSP問題解決方案,本文最終完成程序的編寫并進(jìn)行了仿真,驗(yàn)證了文中方法的可行性和實(shí)際效果,相對于無序的隨機(jī)配送和傳統(tǒng)的分區(qū)塊配送方法,在配送時(shí)間和配送總路徑上有一個(gè)較大的提升。
[Abstract]:In 2016, the Stanford University value chain innovation initiative research center and the U.S. Postal Service Inspector General Office jointly issued the "last mile delivery technology of subversion and innovation. The white paper pointed out in the white paper, four new technology may bring new development support of logistics industry, namely commodity distribution process optimization advanced algorithm, UAV technology in distribution system the participation of mechanical sorting robot technology, artificial and liberated from the logistics system of unmanned vehicle technology. In this paper, advanced algorithm optimization of commodity distribution process, based on the GA algorithm, to solve the TSP problem in the process of delivery. Combined with the actual logistics industry, the logistics cost is always one of the most important one of the biggest problems, the high cost of logistics is also limit the development of the industry. In order to effectively reduce the cost of transportation and distribution costs, can Optimization of distribution channels, optimize the distribution of personnel, improve the efficiency of distribution and so on. The most easy to realize the optimization of transport routes do not need high cost is the delivery vehicle. Thus, this paper establishes a model of routing optimization problem of TSP based on the actual distribution problems, and by combining the actual the problem with improved genetic algorithm to solve the multi-objective problem. TSP constraint based genetic algorithm to solve the actual distribution process, and puts forward the improved algorithm and the solution to the practical problems, which improve the efficiency of the algorithm and the convergence speed of the premise can realize the optimal solution. The main contents of this thesis are as follows: 1. the TSP problem and the genetic algorithm are studied. Research history and research status of genetic algorithm and TSP problem, introduces the mathematical model of TSP problem and genetic algorithm the basic example of genetic The genetic algorithm and the improved algorithm are summarized and analyzed, to provide a prerequisite for subsequent work. The genetic algorithm is based on the theory of modeling and complete the project work.2. a multi-objective mathematical model of the actual distribution of the TSP problem of path length and time based on the target, and realize the actual logistics distribution problem is obtained, the optimal path study on the practical realization scheme of the road path, road road map modeling to solve actual path and time consuming, in the area of different sections and traverse roads, vehicles with different speed. In the multi-objective TSP problem, adding volume limit, return when the volume reached the threshold, i.e. vehicle TSP problem limited volume and make the corresponding solutions in the restricted conditions and realize the calculation of the optimal path. The simulation of traffic lights for traffic congestion and other variable factors, between the two time combined with practical problems The calculated. At the same time to ensure the algorithm without too much calculation, to ensure the efficiency of the algorithm and the convergence of the algorithm. The improvement in the simulation according to the practical application problems in calculation, guarantee the simulation path and the simulation time and the true path of real time fitting algorithm is improved to reduce the error of.3. combined with the practical problems. To solve the cross it is difficult to get through the road between the variation of the optimal sequence problem, fitness function and selection operator adapted to the actual distribution problems in practical problems, more high-quality real estate and more efficient offspring, select excellent offspring. The initial path suitable for urban road solutions, improve the quality of the initial solution path based on the encoding scheme, which is suitable for the actual distribution in the study area, in order to determine the path encoding scheme of optimal target and other information in the actual distribution is put forward in this paper. The solution to the TSP problem in the process, the final completion of the program and the simulation verifies the feasibility of the method and the actual results, compared with the random distribution and disorder of the traditional block distribution method, there is a larger increase in the delivery time and delivery route.

【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：F252;TP18

【參考文獻(xiàn)】

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

1 孫文彬;王江;;一種基于遺傳算法的TSP問題多策略優(yōu)化求解方法[J];地理與地理信息科學(xué);2016年04期

2 文藝;潘大志;;用于求解TSP問題的改進(jìn)遺傳算法[J];計(jì)算機(jī)科學(xué);2016年S1期

3 吳高航;;Hopfield神經(jīng)網(wǎng)絡(luò)解TSP問題及能量函數(shù)參數(shù)分析[J];現(xiàn)代計(jì)算機(jī)(專業(yè)版);2016年09期

4 賴志柱;戈冬梅;張?jiān)破G;;求解TSP問題的改進(jìn)最鄰近法[J];貴州工程應(yīng)用技術(shù)學(xué)院學(xué)報(bào);2016年01期

5 吳虎勝;張鳳鳴;李浩;梁曉龍;;求解TSP問題的離散狼群算法[J];控制與決策;2015年10期

6 徐麗蕊;;城市配送TSP問題的LINGO求解[J];電子設(shè)計(jì)工程;2015年13期

7 崔慧嶺;柯宗武;姜楚喬;;一種求解TSP問題的融合算法[J];湖北師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2015年01期

8 姚偉權(quán);;基于Excel工作表實(shí)現(xiàn)GQPSO求解TSP問題[J];廣州城市職業(yè)學(xué)院學(xué)報(bào);2015年01期

9 段艷明;肖輝輝;;求解TSP問題的改進(jìn)果蠅優(yōu)化算法[J];計(jì)算機(jī)工程與應(yīng)用;2016年06期

10 姚明海;王娜;趙連朋;;改進(jìn)的模擬退火和遺傳算法求解TSP問題[J];計(jì)算機(jī)工程與應(yīng)用;2013年14期

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

1 王超學(xué);遺傳算法和蟻群算法及其在TSP問題和配電網(wǎng)重構(gòu)問題中的應(yīng)用研究[D];西安理工大學(xué);2007年

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

1 鮑文杰;多態(tài)蟻群算法在TSP問題應(yīng)用中的改進(jìn)與優(yōu)化[D];浙江師范大學(xué);2016年

2 邱大洪;基于混沌的蟻群算法及其應(yīng)用研究[D];北京化工大學(xué);2015年

3 孫康;改進(jìn)遷徙策略的TriBA并行遺傳算法及其在TSP問題上的應(yīng)用[D];中北大學(xué);2015年

4 馬堯;基于改進(jìn)的人工魚群算法在商旅問題中的應(yīng)用研究[D];西南交通大學(xué);2015年

5 晏雨;改進(jìn)的遺傳算法和分布估計(jì)算法求解TSP問題[D];重慶理工大學(xué);2013年

6 王娜;一種改進(jìn)的遺傳算法求解TSP問題[D];東北師范大學(xué);2010年

7 唐偉;基于改進(jìn)遺傳算法的TSP問題求解研究[D];大連海事大學(xué);2008年

8 孫海雷;改進(jìn)的遺傳算法求解TSP問題[D];重慶大學(xué);2007年

9 于興濤;一種改進(jìn)的遺傳算法及其在TSP求解中的應(yīng)用[D];山東大學(xué);2006年

10 林志毅;改進(jìn)的遺傳算法求解TSP問題[D];武漢理工大學(xué);2006年

，

本文編號：1741150