發(fā)布時間：2018-06-01 16:35

  本文選題：可拆分 + 車輛路徑問題　； 參考：《東北大學》2014年碩士論文

【摘要】：當今經(jīng)濟快速的發(fā)展,企業(yè)為了獲得更多的經(jīng)濟效益,已不僅僅局限于提供產(chǎn)品本身,同時開始著眼于利用附加服務來吸引更多的客戶,在此背景下,物流配送服務大面積興起。車輛路徑問題作為物流配送的關鍵環(huán)節(jié),是其重要的組成部分和研究方向。但是由于傳統(tǒng)車輛路徑問題約束了每個顧客點必須由一輛車進行服務,而在實際物流配送過程中為了節(jié)約成本,經(jīng)常存在將一個顧客點的需求拆分由一輛以上的車輛進行服務的情況,這啟發(fā)本文針對于可拆分的車輛路徑問題(SDVRP)進行研究。與此同時,考慮到問題建模中忽略了貨物重量對運送車輛數(shù)和總運輸費用的影響,因此求得的最優(yōu)路徑可能并非實際車輛數(shù)和費用最少的路徑。因此,我們又將車輛的載重量加入到目標中,提出了帶貨物權(quán)重的車輛路徑問題(SDWVRP)。這里的貨物權(quán)重是個廣義的概念,不僅僅局限于貨物載重量,還可以表示還可以代表運輸過程中貨物的優(yōu)先程度,緊急程度,以及顧客點的優(yōu)先級和重要程度。而相應的模型目標除了可以代表運輸過程中的總費用,還可以作為運輸過程中總碳排放量、易腐食品的損失量、危險品的風險值、物流運送效力、滿意度值、顧客總旅行時間和顧客點的優(yōu)先程度等。本文主要以物流配送問題為研究背景,具體研究工作包括：研究了SDVRP問題的背景和數(shù)學模型,設計了最大最小蟻群算法和禁忌搜索算法求解SDVRP司題,通過比較兩算法的求解效果,證明對于SDVRP問題模型來說,最大最小蟻群算法求解效果較優(yōu),并在兩算法求解結(jié)果的基礎上,分析出使用可拆分模型比不使用可拆分模型可以獲得更大的經(jīng)濟效益。實驗數(shù)據(jù)選取于VRP BENCHMARK實例庫中的實例,以地理位置分布類型和貨物權(quán)重類型對實例進行劃分,構(gòu)成7種實例分布組合,通過對以上實例進行測試分析,我們考察了在何種地理位置分布和貨物權(quán)重分布類型下,SDVRP建模效果更明顯。并且,通過對MMAS算法參數(shù)進行全因子分析,得出了最適合求解SDVRP問題的算法參數(shù)。在SDVRP問題的基礎上,將顧客點貨物權(quán)重可能對路徑規(guī)劃產(chǎn)生的影響考慮到問題中,我們提出了SDWVRP問題模型,并且根據(jù)問題自身特點,設計出改進的最大最小蟻群算法用于求解SDWVRP問題。通過對SDWVRP模型與SDVRP模型的比較,討論將貨物權(quán)重考慮到問題求解中的必要性和可行性,指出對于不同類型實例來說,SDWVRP模型均有較好的表現(xiàn)。同時指出,在貨物權(quán)重相差較大和地理位置較為分散時,考慮貨物權(quán)重因素的建模效果更好。通過對SDWVRP模型與WVRP模型的比較,說明考慮拆分策略對問題求解的意義,經(jīng)過對大量實例的測試分析,證明可拆分策略可以更明顯的減少運輸過程中使用的運輸車輛數(shù),進而降低運輸總費用,減少企業(yè)總成本。綜上,通過實驗測試可以說明,考慮可拆分和貨物權(quán)重的模型求解效果,會受到顧客點地理位置分布類型和權(quán)重分布類型的影響,特定的地理位置和權(quán)重分布組合可以得到更好的求解效果。
[Abstract]:With the rapid economic development today, in order to obtain more economic benefits, enterprises have not only limited the product itself, but also focus on the use of additional services to attract more customers. In this context, the logistics and distribution service has sprung up in a large area. Vehicle routing problem is the key link of logistics distribution, and it is an important part of its component part. But because of the traditional vehicle routing problem, each customer point must be served by a car, and in order to save the cost in the actual logistics distribution process, there is often a situation of splitting the demand of a customer point by more than one vehicle. This inspires this article for the disassembled vehicle road. At the same time, considering the effect of the weight of the goods on the number of vehicles and the total cost of transportation, the optimal path may not be the path to the actual number of vehicles and the least cost. Therefore, we add the vehicle's load to the target and propose a vehicle with the weight of the goods. The vehicle routing problem (SDWVRP). The weight of the goods here is a generalized concept, not limited to the weight of the cargo, but also represents the priority, the urgency, the priority and the importance of the customer's points in the transportation process, and the corresponding model targets can represent the total cost of the transport process, as well as the total cost of the transportation process. It can be used as the total carbon emissions in the process of transportation, the amount of perishable food, the risk value of dangerous goods, the effectiveness of logistics transportation, the value of satisfaction, the customer's total travel time and the priority of the customer points. This paper mainly takes the logistics distribution as the research background, and the specific research work includes the background and mathematical model of the SDVRP problem. The maximum minimum ant colony algorithm and tabu search algorithm are considered to solve the SDVRP problem. By comparing the results of the two algorithm, it is proved that the maximum minimum ant colony algorithm is better in solving the SDVRP problem model. On the basis of the results of the two algorithm, it is found that the use of the split model can be better than that without the use of the split model. The experimental data are selected in the example of the VRP BENCHMARK case base, the geographical location distribution type and the weight type of the goods are divided into 7 instances. By testing and analyzing the above examples, we examine the SDVRP modeling under the location distribution and the distribution of goods weight. The effect is more obvious. Furthermore, through the full factor analysis of the MMAS algorithm parameters, the most suitable algorithm parameters for solving the SDVRP problem are obtained. On the basis of the SDVRP problem, the effect of the possible weight of the customer point goods on the path planning is taken into consideration. The SDWVRP model is proposed and the design is designed according to the characteristics of the problem. The improved maximum and minimum ant colony algorithm is used to solve the SDWVRP problem. By comparing the SDWVRP model with the SDVRP model, the necessity and feasibility of taking the weight of the goods into consideration in the problem solving are discussed. It is pointed out that the SDWVRP model has better performance for different types of examples. By comparing the SDWVRP model with the WVRP model, it shows the significance of considering the dismantling strategy to solve the problem, and through a large number of examples, it is proved that the dismantling strategy can reduce the number of transportation vehicles used in the transport process, and then reduce the transportation. Overall cost, reduce the total cost of the enterprise. In summary, the experimental test can show that the effect of the model solving effect considering the disassembly and the weight of the goods will be influenced by the location distribution type and the weight distribution type of the customer point, and the specific geographical location and the weight distribution combination can get better results.
【學位授予單位】：東北大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：U116.2;F252

【參考文獻】

相關期刊論文 前5條

1 張家善;王志宏;陳應顯;;一種基于精英策略的改進蟻群算法及應用[J];計算機系統(tǒng)應用;2012年10期

2 李康順;徐福梅;張文生;湯銘端;;一種基于啟發(fā)式演化算法的最優(yōu)-最差螞蟻系統(tǒng)[J];中南大學學報(自然科學版);2010年02期

3 唐加福;孔媛;潘震東;董穎;;基于劃分的蟻群算法求解貨物權(quán)重車輛路徑問題[J];控制理論與應用;2008年04期

4 潘震東;唐加福;韓毅;;帶貨物權(quán)重的車輛路徑問題及遺傳算法[J];管理科學學報;2007年03期

5 李仁安,袁際軍;基于改進遺傳算法的物流配送路線優(yōu)化研究[J];武漢理工大學學報;2004年12期

相關博士學位論文 前1條

1 鐘石泉;物流配送車輛路徑優(yōu)化方法研究[D];天津大學;2007年

，

本文編號：1964886