本文關(guān)鍵詞： 車輛路徑規(guī)劃 蟻群算法 自適應(yīng)　出處：《吉林大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著電子商務(wù)的發(fā)展，其便利快捷的購(gòu)物特性，讓越來(lái)越多的人們選擇網(wǎng)上購(gòu)物這種方式，電商在人們生活中占據(jù)越來(lái)越重要的位置。由于其遠(yuǎn)距離特性，因此需要物流行業(yè)在其中起著配送的作用。由于在物流業(yè)務(wù)中，快遞普遍成本過(guò)高并且效率低下，因此提高運(yùn)送效率和降低快遞成本對(duì)于降低網(wǎng)購(gòu)成本具有很大的現(xiàn)實(shí)意義，車輛路徑規(guī)劃問(wèn)題（Vehicle Routing Problem，VRP）是公認(rèn)的解決物流配送問(wèn)題求解最低貨物成本的理論模型。貨物配送服務(wù)的關(guān)鍵是服務(wù)速度和質(zhì)量，在一個(gè)給定的期間內(nèi)，一組客戶和一組車輛，這些車輛被分配到一個(gè)或更多集運(yùn)點(diǎn)。通過(guò)對(duì)一個(gè)車隊(duì)來(lái)進(jìn)行約束操作并使用適當(dāng)?shù)墓肪W(wǎng)絡(luò)，VRP問(wèn)題的解被稱為確定的一組路線，每個(gè)車輛的起點(diǎn)和終點(diǎn)都在自己的集運(yùn)點(diǎn)。如此，，所有的客戶都被滿足，所有的操作約束都被滿足，并且整體的運(yùn)輸費(fèi)用最低。在過(guò)去的數(shù)十年中對(duì)快遞優(yōu)化方案正在逐漸增加，大量現(xiàn)實(shí)實(shí)例證實(shí)，使用大量的計(jì)算機(jī)程序應(yīng)用于規(guī)劃分配計(jì)劃中，可以在整體運(yùn)輸成本中產(chǎn)生大量的節(jié)約（通常較不做規(guī)劃節(jié)約5%-20%）。很容易看出來(lái)，這些節(jié)約在整體行業(yè)成本中是很重大的，事實(shí)上，運(yùn)輸過(guò)程包括生產(chǎn)和分配系統(tǒng)的全過(guò)程。并且運(yùn)輸成本也是最終成本的相關(guān)因素。 車輛路徑規(guī)劃問(wèn)題的研究可以減少很大一部分物流開(kāi)銷。到目前為止，出現(xiàn)了很多求解車輛路徑問(wèn)題的算法，有精確算法(accurate algorithm）和啟發(fā)式算法(heuristicsalgorithms）。其中,精確算法用來(lái)求解問(wèn)題最優(yōu)解的方式是嚴(yán)格的數(shù)學(xué)方法，啟發(fā)式算法則利用對(duì)狀態(tài)空間的位置評(píng)價(jià)來(lái)找到較好的位置，再基于這個(gè)位置進(jìn)行搜索，直到找到目標(biāo)為止。隨著問(wèn)題規(guī)模不斷地?cái)U(kuò)大，精確算法的計(jì)算量越來(lái)越大，還不能直接用來(lái)解決實(shí)際問(wèn)題。啟發(fā)式算法則可以根據(jù)不同的問(wèn)題要求來(lái)求解問(wèn)題。 基于VRP問(wèn)題的本質(zhì)，不太可能使用精確的方法求解VRP的大規(guī)模的實(shí)例。因此，大部分方法都依賴于啟發(fā)式方法來(lái)獲取近似解。許多方法已經(jīng)被用到了這個(gè)領(lǐng)域中，其中有選擇使用標(biāo)準(zhǔn)優(yōu)化技術(shù)的算法，例如，蟻群算法、遺傳算法、模擬退火和約束編程。我們?cè)谶@里關(guān)注于元啟發(fā)式算法，主要是蟻群算法。蟻群算法是啟發(fā)式算法中主流的一種算法。由Marco Dorigo于1992年受到螞蟻覓食行為啟發(fā)而提出，將其應(yīng)用到了組合優(yōu)化問(wèn)題中。通過(guò)實(shí)驗(yàn)結(jié)果表明，蟻群算法可以找到相對(duì)較好的解，而且具有很強(qiáng)的魯棒性。 在本文中，我們基于已有的研究成果，將自適應(yīng)思想與最大最小螞蟻系統(tǒng)相結(jié)合。在每次搜索循環(huán)的過(guò)程中，我們可以自適應(yīng)的決定精英螞蟻的數(shù)量。只要在搜索的過(guò)程中，達(dá)到了一定的要求，我們就可以把它當(dāng)作精英螞蟻，將它的信息素保留下去。在更新一條路徑上的信息素時(shí)，考慮兩點(diǎn)之間的距離，而不是均勻的將信息素釋放在路徑在。提出獎(jiǎng)勵(lì)懲罰制度，將螞蟻當(dāng)前走過(guò)的路徑與上一次的最優(yōu)路徑進(jìn)行比較，對(duì)螞蟻進(jìn)行等級(jí)劃分，將排名靠前的螞蟻所在的路徑上的信息素予以增強(qiáng)，排名靠后的螞蟻所在的路徑上的信息素予以減少。通常，可以尋找到較優(yōu)解。
[Abstract]:With the development of electronic commerce, its convenient shopping, let more and more people choose online shopping this way, electricity providers occupy an increasingly important position in people's life. Because of the characteristics of long distance, so the logistics industry plays a role. The distribution in the logistics business, the high cost of universal express and low efficiency, so as to improve transport efficiency and reduce the cost for the express has great practical significance to reduce the cost of online shopping, vehicle routing problem (Vehicle Routing, Problem, VRP) is a theoretical model to solve the matter as flow distribution problem solving minimum cost of the goods and delivery of the goods. The key is the speed and quality of service, in a period given that a group of customers and vehicles, these vehicles are assigned to one or more cargo. According to a team of constraints and make the operation With the appropriate highway network, the solution of the VRP problem is called a group of routes to determine the starting point and end point of each vehicle in its own container. So, all customers are satisfied, all the operating constraints are satisfied, and the overall transportation cost minimum. In the past ten years the number of Express optimization scheme is increasing gradually, confirmed that a large number of practical examples, the use of computer programs in the application of planning and allocation plan, can produce a large number of savings in the overall transport costs (usually do not plan to save 5%-20%). It is easy to see that these savings are significant in the overall cost in the industry, in fact, the transport process include the whole process of production and distribution system. And the related factors of transportation cost and final cost.
Study of vehicle routing problem can be reduced to a large part of logistics cost. So far, there has been a lot of vehicle routing problem solving algorithm, accurate algorithm (accurate algorithm) and heuristic algorithm (heuristicsalgorithms). Among them, the exact algorithm to solve the problem of optimal solution is a rigorous mathematical method, the heuristic algorithm is the use of position the evaluation of state space to find a better position, then search based on this position, until you find the target so far. As the problem scale continues to expand, the exact algorithm of calculation is more and more big, also can not be directly used to solve practical problems. The heuristic algorithm can request to solve the problem according to different problems.
The essence of VRP problem based on the example of large scale are less likely to use the method to solve VRP accurately. Therefore, most methods rely on heuristic methods to obtain approximate solutions. Many methods have been used in this field, which have the option to use standard optimization algorithms, such as ant colony algorithm, genetic algorithm, simulation annealing and constraint programming. We focus on meta heuristic algorithm here is the ant colony algorithm. Ant colony algorithm is a heuristic algorithm of mainstream algorithm. By Marco Dorigo in 1992 was inspired by the foraging behavior of ants is proposed, its application to combinatorial optimization problems. The experimental results show that the ant colony algorithm can find the relative a better solution, but also has strong robustness.
In this paper, we based on the existing research achievements, the adaptive thought and max min ant system combined. In each cycle of search process, we can determine the number of adaptive elite ants. As long as in the search process, meet the certain requirements, we can regard it as the elite ants. It's keeping. The pheromone updates a pheromone path, considering the distance between two points, and not even the pheromone release in the path. In the proposed penalty system, the current through the ant path compared with the optimal path at a time, carry on the classification of ants, will on the path where the ranking of the ant pheromone on the path to be enhanced, ranked by the ant's pheromone on be reduced. Usually, you can find a better solution.

【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP18

【相似文獻(xiàn)】

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

1 鄒海洋;;蟻群算法在車輛路徑選擇上的應(yīng)用[J];科技信息;2011年23期

2 潘登;鄭應(yīng)平;陸小芳;;避免車輛路徑擁塞的動(dòng)態(tài)蟻群算法[J];計(jì)算機(jī)工程;2008年05期

3 雷暉;楊皎平;張麗鳳;田洋;;具有模糊時(shí)間窗的轉(zhuǎn)運(yùn)聯(lián)盟車輛路徑及遺傳優(yōu)化[J];計(jì)算機(jī)系統(tǒng)應(yīng)用;2014年03期

4 陳文蘭;戴樹(shù)貴;;車輛路徑安排問(wèn)題算法研究綜述[J];滁州學(xué)院學(xué)報(bào);2007年03期

5 李惠珠;宋海清;;基于GIS的物流配送車輛調(diào)度實(shí)現(xiàn)與應(yīng)用[J];長(zhǎng)春師范學(xué)院學(xué)報(bào);2011年04期

6 戴樹(shù)貴;陳文蘭;潘蔭榮;胡幼華;;多配送中心車輛路徑安排問(wèn)題混合蟻群算法[J];四川大學(xué)學(xué)報(bào)(工程科學(xué)版);2008年06期

7 戴意愿;文桂林;周華安;;乘客運(yùn)輸?shù)能囕v路徑規(guī)劃策略[J];計(jì)算機(jī)工程與應(yīng)用;2013年12期

8 許敏;邱朝陽(yáng);;帶時(shí)間窗限制的車輛調(diào)度子路徑平衡性研究[J];電腦與電信;2009年07期

9 劉曉

本文編號(hào)：1517149