本文關鍵詞： 節(jié)約算法 帶時間窗的車輛路徑問題 分割配送 蜂群優(yōu)化算法 層次分析法　出處：《吉林大學》2017年碩士論文　論文類型：學位論文

【摘要】：21世紀初,物流產業(yè)成為推動經(jīng)濟全球化的重要服務行業(yè)。在國民經(jīng)濟水平的快速發(fā)展和宏觀調控的逐步改善下,中國的物流市場需求逐漸增加,產業(yè)水平保持較快發(fā)展。但中國物流產業(yè)的總成本仍是居高不下,根據(jù)《全國物流運行情況通報》得知,2014年社會物流總費用是10.6萬億元,2015年達到了10.8萬億元,而2016年1-11月的總費用為9.6萬億元。由此可見,物流行業(yè)的配送成本仍然過高。因此,減少物流產業(yè)的配送成本問題尤為重要。1959年,由Ramser和Dantzig提出的車輛路徑問題(Vehicle Routing Problem,簡稱VRP),一直是業(yè)內研究的熱點領域問題,其目標是盡可能減少路徑配送成本,得到最優(yōu)路徑。根據(jù)各類約束條件可將VRP問題進行分類,如帶車輛容積約束的VRP問題,帶時間窗約束的VRP問題,單車場或多車場的VRP問題等。而本文主要針對帶時間窗的車輛路徑問題(With Time Windows Vehicle Routing Problem,簡稱VRPTW)求解物流行業(yè)中可供選擇的最優(yōu)路徑�，F(xiàn)如今,解決VRPTW問題的算法也數(shù)不勝數(shù),主要基于兩個方面的算法:精確算法和啟發(fā)式算法。本文在經(jīng)典啟發(fā)式算法節(jié)約算法(CW算法)的基礎上進一步做出改進,在硬時間窗約束的條件下,加入分割配送思想,不僅提高了算法的精確度和可行性,減少了配送總運輸成本,還增加了車輛的載重率,提高了算法針對VRPTW問題的實效性。本文針對VRPTW問題,在原有CW算法中加入時間約束,使配送車輛必須在固定時間范圍內送達貨物,否則客戶拒絕接收貨物,即在CW算法中不僅對車輛載重控制,又添加了對時間的控制,多角度地接近現(xiàn)實問題。為將分割配送應用到CW算法中,文中定義了分割配送反應值這一概念,而為求解該反應值,本文介紹了蜂群優(yōu)化算法(Bee Colony Optimization Algorithm,簡稱BCO),該算法中提到了貨物對車輛的刺激值,該刺激值與車輛的運輸里程c和運輸時間t成正比,而運輸里程和運輸時間兩種影響因素對問題結果存在一定的間接影響,因此采用層次分析法(Analytic Hierarchy Process,簡稱AHP)求出兩種影響因素的權重,并作為因子a和b左右其影響程度。將以上思路結合在一起,得到分割配送反應值的計算公式H=△L/c~at~b(△L為CW算法中的節(jié)約值),從而按照反應值H從大到小的順序決定哪個客戶需求優(yōu)先被分割,再結合原有CW算法的解題步驟,得到VRPTW的最優(yōu)解。為驗證本文提出的改進CW算法的可行性和實用性,將改進CW算法應用到具體實例中,得到了問題的滿意解。同時與經(jīng)典CW算法對比分析,得知改進后算法的精確度更高,實用性更強,車輛裝載率更大。又進一步與其他學者的改進CW算法對比分析,得出本算法更適用于配送中心固定成本高于行駛成本的硬時間窗約束的VRP問題。
[Abstract]:In 21th century, logistics industry became an important service industry to promote economic globalization. With the rapid development of national economy and the gradual improvement of macro-control, the demand of logistics market in China gradually increased. However, the total cost of China's logistics industry is still high. According to the National Logistics Operation Bulletin, the total cost of social logistics was 10.6 tillion yuan in 2014 and 10.8 tillion yuan in 2015. From 2016 to November, the total cost was 9.6 tillion yuan. Thus, the cost of distribution in the logistics industry is still too high. Therefore, it is particularly important to reduce the cost of distribution in the logistics industry. The vehicle Routing problem proposed by Ramser and Dantzig has always been a hot topic in the field of research. Its goal is to reduce the cost of routing distribution as much as possible and to obtain the optimal route. According to various constraints, the VRP problem can be classified. For example, VRP problem with vehicle volume constraint, VRP problem with time window constraint, In this paper, the problem of vehicle routing with Time Windows Vehicle Routing problem is mainly used to solve the optimal path in logistics industry. Nowadays, there are too many algorithms to solve the problem of VRPTW. Based on two main algorithms: precise algorithm and heuristic algorithm. This paper further improves the classical heuristic algorithm based on the saving algorithm (CW algorithm), and adds the idea of segmentation and distribution under the condition of hard time window constraint. It not only improves the accuracy and feasibility of the algorithm, reduces the total transportation cost of distribution, but also increases the load rate of the vehicle, and improves the effectiveness of the algorithm for the VRPTW problem. In this paper, time constraints are added to the original CW algorithm for the VRPTW problem. The delivery vehicle must deliver the goods within a fixed time range, otherwise the customer refuses to receive the goods, that is, in the CW algorithm, not only the vehicle load control, but also the time control is added. In order to apply partitioned distribution to CW algorithm, the concept of split distribution response value is defined, and the response value is solved. In this paper, bee Colony Optimization algorithm is introduced. In this algorithm, the stimulation value of cargo to vehicle is mentioned, which is directly proportional to the transportation mileage c and the transport time t of the vehicle. The influence factors of transportation mileage and transportation time have some indirect influence on the result of the problem, so Analytic Hierarchy process (AHPP) is used to calculate the weight of the two factors. And as a factor a and b about its influence degree. The formula for calculating the response value of the partition distribution is obtained, H = L / C / C / T / B (L is the saving value in the CW algorithm), and then according to the order of the response value H from large to small to determine which customer needs to be partitioned first, and then combine the solution steps of the original CW algorithm. In order to verify the feasibility and practicability of the improved CW algorithm proposed in this paper, the improved CW algorithm is applied to a concrete example and the satisfactory solution of the problem is obtained. At the same time, it is compared with the classical CW algorithm. It is known that the improved algorithm has higher accuracy, better practicability and higher vehicle loading rate. Furthermore, it is compared with the improved CW algorithm proposed by other scholars. It is concluded that this algorithm is more suitable for the VRP problem with fixed cost higher than driving cost in distribution center.
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：F259.2;TP18

【相似文獻】

相關期刊論文 前10條

1 馬安光;;棋子問題的算法分析——2003年第11期題解[J];程序員;2004年01期

2 馮舜璽;;新書推薦:《算法分析導論》[J];計算機教育;2006年05期

3 張力,慕曉冬;計算機算法分析淺談[J];武警工程學院學報;2002年04期

4 馬安光;;飛彈問題的算法分析——2003年第10期題解[J];程序員;2003年12期

5 蘇運霖;;《算法分析導論》評介[J];計算機教育;2006年07期

6 朱力強;;培養(yǎng)學生創(chuàng)新思維與能力的算法分析案例[J];計算機與信息技術;2007年11期

7 汪菊琴;;幾種常見特殊方陣的算法分析與實現(xiàn)[J];無錫職業(yè)技術學院學報;2009年05期

8 李涵;;“算法分析與設計”課程教學改革和實踐[J];中國電力教育;2010年16期

9 劉寧;管濤;;淺析案例教學法在算法分析與設計課程中的應用[J];科技風;2011年07期

10 胡峰;王國胤;;“算法分析與設計”教學模式探索[J];當代教育理論與實踐;2011年12期

相關會議論文 前10條

1 俞洋;田亞菲;;一種新的變步長LMS算法及其仿真[A];通信理論與信號處理新進展——2005年通信理論與信號處理年會論文集[C];2005年

2 周顥;劉振華;趙保華;;構造型的D~2FA生成算法[A];中國通信學會通信軟件技術委員會2009年學術會議論文集[C];2009年

3 賴桃桃;馮少榮;張東站;;一種基于劃分和密度的快速聚類算法[A];第二十五屆中國數(shù)據(jù)庫學術會議論文集（一）[C];2008年

4 劉遠新;鄧飛其;羅艷輝;舒添慧;;ERP柔性平臺下物流運輸配送系統(tǒng)算法分析[A];第二十六屆中國控制會議論文集[C];2007年

5 王樹西;白碩;姜吉發(fā);;模式合一的“減首去尾”算法[A];第二屆全國學生計算語言學研討會論文集[C];2004年

6 王萬青;張曉輝;;改進的A~*算法的高效實現(xiàn)[A];2009全國測繪科技信息交流會暨首屆測繪博客征文頒獎論文集[C];2009年

7 孫煥良;邱菲;劉俊嶺;朱葉麗;;IncSNN——一種基于密度的增量聚類算法[A];第二十三屆中國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2006年

8 韓建民;岑婷婷;于娟;;實現(xiàn)敏感屬性l-多樣性的l-MDAV算法[A];第二十七屆中國控制會議論文集[C];2008年

9 張悅;尤楓;趙瑞蓮;;利用蟻群算法實現(xiàn)基于程序結構的主變元分析[A];第五屆中國測試學術會議論文集[C];2008年

10 王旭東;劉渝;鄧振淼;;正弦波頻率估計的修正Rife算法及其FPGA實現(xiàn)[A];全國第十屆信號與信息處理、第四屆DSP應用技術聯(lián)合學術會議論文集[C];2006年

相關重要報紙文章 前1條

1 科文;VIXD算法分析Web異常[N];中國計算機報;2008年

相關博士學位論文 前10條

1 魏哲學;樣本斷點距離問題的算法與復雜性研究[D];山東大學;2015年

2 劉春明;基于增強學習和車輛動力學的高速公路自主駕駛研究[D];國防科學技術大學;2014年

3 張敏霞;生物地理學優(yōu)化算法及其在應急交通規(guī)劃中的應用研究[D];浙江工業(yè)大學;2015年

4 李紅;流程挖掘算法研究[D];云南大學;2015年

5 卜晨陽;演化約束優(yōu)化及演化動態(tài)優(yōu)化求解算法研究[D];中國科學技術大學;2017年

6 劉新旺;多核學習算法研究[D];國防科學技術大學;2013年

7 于濱;城市公交系統(tǒng)模型與算法研究[D];大連理工大學;2006年

8 曾國強;改進的極值優(yōu)化算法及其在組合優(yōu)化問題中的應用研究[D];浙江大學;2011年

9 肖永豪;蜂群算法及在圖像處理中的應用研究[D];華南理工大學;2011年

10 陳耿;面向中觀審計的規(guī)則發(fā)現(xiàn)算法研究[D];東南大學;2005年

相關碩士學位論文 前10條

1 黃廈;基于改進蟻群算法的柔性作業(yè)車間調度問題研究[D];昆明理工大學;2015年

2 李平;基于Hadoop的信息爬取與輿情檢測算法研究[D];昆明理工大學;2015年

3 趙官寶;基于位表的關聯(lián)規(guī)則挖掘算法研究[D];昆明理工大學;2015年

4 殷文華;移動容遲網(wǎng)絡中基于社會感知的多播分發(fā)算法研究[D];內蒙古大學;2015年

5 徐翔燕;人工魚群優(yōu)化算法及其應用研究[D];西南交通大學;2015年

6 李德福;基于小世界模型的啟發(fā)式尋路算法研究[D];華中師范大學;2015年

7 鄭海彬;一種面向MAPREDUCE的DATASHUFFLE的優(yōu)化方法[D];蘇州大學;2015年

8 趙曉寒;輪換步長PSO算法及SMVSC參數(shù)優(yōu)化[D];沈陽理工大學;2015年

9 安豐洋;基于無線網(wǎng)絡的廣播算法研究[D];曲阜師范大學;2015年

10 李智明;基于改進FastICA算法的混合語音盲分離[D];上海交通大學;2015年

，

本文編號：1495666