【摘要】：隨著經(jīng)濟全球化的快速擴張以及信息化產(chǎn)業(yè)的扶搖直上,物流作為新興服務(wù)業(yè),廣闊的前景和增值功能有目共睹,正在全球范圍內(nèi)有著飛躍性的進(jìn)步。在物流諸多環(huán)節(jié)中,降低運輸成本、提高運輸效率有助于加速物流業(yè)的發(fā)展。因此,作為運輸?shù)暮诵膯栴}的車輛路徑問題得到了充足的研究,并取得了豐富的研究成果。它通過組織、優(yōu)化貨物的運輸線路,在滿足一定的約束前提下,以最低的運輸費用、最短的運輸距離、最少的運輸時間等為目標(biāo),將貨物送達(dá)目的地。 本文基于對車輛路徑問題的數(shù)學(xué)模型,結(jié)合之前學(xué)者采用各種算法進(jìn)行的豐富研究,設(shè)計了改進(jìn)的粒子群算法應(yīng)用于車輛路徑問題,以及用遺傳算法求解同時供貨和取貨任務(wù)的隨機車輛路徑問題。本文所做工作如下： (1)簡要介紹了車輛路徑問題的研究進(jìn)程與現(xiàn)狀,以及研究意義,介紹了車輛路徑問題的數(shù)學(xué)模型、精確算法、啟發(fā)式算法和智能優(yōu)化算法等。 (2)概要介紹了遺傳算法優(yōu)勝劣汰、粒子群算法群體趨優(yōu)的基本思想、算法步驟流程以及在各領(lǐng)域的應(yīng)用。 (3)主要研究用粒子群算法求解有能力約束的車輛路徑問題,由于粒子速度受到前一次速度的影響,進(jìn)而影響算法的搜索能力,本文針對粒子群算法中慣性權(quán)重的選擇,采用線性與非線性結(jié)合的取值方式。實驗結(jié)果表明,改進(jìn)后,搜索最優(yōu)解的成功率得到提高,全局搜索能力有所進(jìn)步,并且計算精度也得到改善。而對于較大規(guī)模的車輛路徑問題,采用粒子群算法與遺傳算法相結(jié)合的方案,引入遺傳算法特有的交叉算子的思想。實驗結(jié)果顯示,改進(jìn)后,較好的避免了早熟收斂,同時提高了收斂速度與精度。 (4)針對同時供貨和取貨任務(wù)的隨機車輛路徑問題,由于信息的不確定性,考慮到使用不依賴于具體的問題的遺傳算法進(jìn)行求解,結(jié)合問題采用自然數(shù)編碼的方式,并對算法中選擇算子進(jìn)行改進(jìn),保證保存最優(yōu)個體,并對基本案例進(jìn)行了測試,得到良好的結(jié)果。
[Abstract]:With the rapid expansion of economic globalization and information industry, logistics, as a new service industry, has broad prospects and value-added functions, and is making great progress in the world. In many aspects of logistics, reducing transportation cost and improving transportation efficiency are helpful to accelerate the development of logistics industry. Therefore, the vehicle routing problem, which is the core problem of transportation, has been fully studied, and a lot of research results have been obtained. Through organizing and optimizing the transportation line of goods, it can reach the destination with the aim of the lowest transportation cost, the shortest transportation distance and the least transportation time, under the premise of satisfying certain constraints. In this paper, based on the mathematical model of vehicle routing problem, combined with the abundant research of previous scholars using various algorithms, an improved particle swarm optimization algorithm is designed to apply to the vehicle routing problem. Genetic algorithm is used to solve the stochastic vehicle routing problem. The work of this paper is as follows: (1) the research process and current situation of the vehicle routing problem are briefly introduced. The mathematical model, exact algorithm, heuristic algorithm and intelligent optimization algorithm of the vehicle routing problem are introduced. (2) the basic ideas of genetic algorithm (GA), particle swarm optimization (PSO) and its application in various fields are briefly introduced. (3) Particle Swarm Optimization (PSO) algorithm is mainly used to solve the vehicle routing problem with capacity constraints. Because the particle velocity is affected by the previous velocity, and then the search ability of the algorithm is affected, this paper aims at the choice of inertia weight in PSO. A combination of linear and nonlinear values is adopted. The experimental results show that the success rate of searching the optimal solution is improved, the global search ability is improved, and the computational accuracy is improved. For the large scale vehicle routing problem, particle swarm optimization (PSO) combined with genetic algorithm (GA) is adopted, and the idea of crossover operator which is unique to GA is introduced. The experimental results show that the improved method can avoid premature convergence and improve the speed and precision of convergence. (4) for the random vehicle routing problem with both supply and delivery tasks, considering the uncertainty of information, considering the use of genetic algorithm which does not depend on the specific problem, the method of natural number coding is used to solve the problem. The selection operator in the algorithm is improved to ensure the preservation of the optimal individual, and the basic cases are tested and good results are obtained.
【學(xué)位授予單位】：安徽理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP18

【參考文獻(xiàn)】

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

1 劉瑞;劉悅;;基于交叉和自適應(yīng)權(quán)重的混合粒子群優(yōu)化算法[J];信息技術(shù);2010年11期

2 祝崇雋,劉民,吳澄;供應(yīng)鏈中車輛路徑問題的研究進(jìn)展及前景[J];計算機集成制造系統(tǒng)-CIMS;2001年11期

3 李婭;王東;;多策略優(yōu)化的蟻群算法求解帶時間窗車輛路徑問題[J];計算機與數(shù)字工程;2013年04期

4 彭春林;梁春華;周泓;;求解同時取貨和送貨車輛路徑問題的改進(jìn)遺傳算法[J];系統(tǒng)仿真學(xué)報;2008年09期

5 李寧,鄒彤,孫德寶;車輛路徑問題的粒子群算法研究[J];系統(tǒng)工程學(xué)報;2004年06期

6 李寧,鄒彤,孫德寶;帶時間窗車輛路徑問題的粒子群算法[J];系統(tǒng)工程理論與實踐;2004年04期

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

1 陸琳;不確定信息車輛路徑問題及其算法研究[D];南京航空航天大學(xué);2007年

2 周輝仁;遞階遺傳算法理論及其應(yīng)用研究[D];天津大學(xué);2008年

3 劉逸;粒子群優(yōu)化算法的改進(jìn)及應(yīng)用研究[D];西安電子科技大學(xué);2013年

，

本文編號：2335844