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

【摘要】：21世紀(jì)初,物流產(chǎn)業(yè)成為推動(dòng)經(jīng)濟(jì)全球化的重要服務(wù)行業(yè)。在國(guó)民經(jīng)濟(jì)水平的快速發(fā)展和宏觀調(diào)控的逐步改善下,中國(guó)的物流市場(chǎng)需求逐漸增加,產(chǎn)業(yè)水平保持較快發(fā)展。但中國(guó)物流產(chǎn)業(yè)的總成本仍是居高不下,根據(jù)《全國(guó)物流運(yùn)行情況通報(bào)》得知,2014年社會(huì)物流總費(fèi)用是10.6萬(wàn)億元,2015年達(dá)到了10.8萬(wàn)億元,而2016年1-11月的總費(fèi)用為9.6萬(wàn)億元。由此可見,物流行業(yè)的配送成本仍然過高。因此,減少物流產(chǎn)業(yè)的配送成本問題尤為重要。1959年,由Ramser和Dantzig提出的車輛路徑問題(Vehicle Routing Problem,簡(jiǎn)稱VRP),一直是業(yè)內(nèi)研究的熱點(diǎn)領(lǐng)域問題,其目標(biāo)是盡可能減少路徑配送成本,得到最優(yōu)路徑。根據(jù)各類約束條件可將VRP問題進(jìn)行分類,如帶車輛容積約束的VRP問題,帶時(shí)間窗約束的VRP問題,單車場(chǎng)或多車場(chǎng)的VRP問題等。而本文主要針對(duì)帶時(shí)間窗的車輛路徑問題(With Time Windows Vehicle Routing Problem,簡(jiǎn)稱VRPTW)求解物流行業(yè)中可供選擇的最優(yōu)路徑�，F(xiàn)如今,解決VRPTW問題的算法也數(shù)不勝數(shù),主要基于兩個(gè)方面的算法:精確算法和啟發(fā)式算法。本文在經(jīng)典啟發(fā)式算法節(jié)約算法(CW算法)的基礎(chǔ)上進(jìn)一步做出改進(jìn),在硬時(shí)間窗約束的條件下,加入分割配送思想,不僅提高了算法的精確度和可行性,減少了配送總運(yùn)輸成本,還增加了車輛的載重率,提高了算法針對(duì)VRPTW問題的實(shí)效性。本文針對(duì)VRPTW問題,在原有CW算法中加入時(shí)間約束,使配送車輛必須在固定時(shí)間范圍內(nèi)送達(dá)貨物,否則客戶拒絕接收貨物,即在CW算法中不僅對(duì)車輛載重控制,又添加了對(duì)時(shí)間的控制,多角度地接近現(xiàn)實(shí)問題。為將分割配送應(yīng)用到CW算法中,文中定義了分割配送反應(yīng)值這一概念,而為求解該反應(yīng)值,本文介紹了蜂群優(yōu)化算法(Bee Colony Optimization Algorithm,簡(jiǎn)稱BCO),該算法中提到了貨物對(duì)車輛的刺激值,該刺激值與車輛的運(yùn)輸里程c和運(yùn)輸時(shí)間t成正比,而運(yùn)輸里程和運(yùn)輸時(shí)間兩種影響因素對(duì)問題結(jié)果存在一定的間接影響,因此采用層次分析法(Analytic Hierarchy Process,簡(jiǎn)稱AHP)求出兩種影響因素的權(quán)重,并作為因子a和b左右其影響程度。將以上思路結(jié)合在一起,得到分割配送反應(yīng)值的計(jì)算公式H=△L/c~at~b(△L為CW算法中的節(jié)約值),從而按照反應(yīng)值H從大到小的順序決定哪個(gè)客戶需求優(yōu)先被分割,再結(jié)合原有CW算法的解題步驟,得到VRPTW的最優(yōu)解。為驗(yàn)證本文提出的改進(jìn)CW算法的可行性和實(shí)用性,將改進(jìn)CW算法應(yīng)用到具體實(shí)例中,得到了問題的滿意解。同時(shí)與經(jīng)典CW算法對(duì)比分析,得知改進(jìn)后算法的精確度更高,實(shí)用性更強(qiáng),車輛裝載率更大。又進(jìn)一步與其他學(xué)者的改進(jìn)CW算法對(duì)比分析,得出本算法更適用于配送中心固定成本高于行駛成本的硬時(shí)間窗約束的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.
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：F259.2;TP18

【相似文獻(xiàn)】

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

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

2 馮舜璽;;新書推薦:《算法分析導(dǎo)論》[J];計(jì)算機(jī)教育;2006年05期

3 張力,慕曉冬;計(jì)算機(jī)算法分析淺談[J];武警工程學(xué)院學(xué)報(bào);2002年04期

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

5 蘇運(yùn)霖;;《算法分析導(dǎo)論》評(píng)介[J];計(jì)算機(jī)教育;2006年07期

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

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

8 李涵;;“算法分析與設(shè)計(jì)”課程教學(xué)改革和實(shí)踐[J];中國(guó)電力教育;2010年16期

9 劉寧;管濤;;淺析案例教學(xué)法在算法分析與設(shè)計(jì)課程中的應(yīng)用[J];科技風(fēng);2011年07期

10 胡峰;王國(guó)胤;;“算法分析與設(shè)計(jì)”教學(xué)模式探索[J];當(dāng)代教育理論與實(shí)踐;2011年12期

相關(guān)會(huì)議論文 前10條

1 俞洋;田亞菲;;一種新的變步長(zhǎng)LMS算法及其仿真[A];通信理論與信號(hào)處理新進(jìn)展——2005年通信理論與信號(hào)處理年會(huì)論文集[C];2005年

2 周顥;劉振華;趙保華;;構(gòu)造型的D~2FA生成算法[A];中國(guó)通信學(xué)會(huì)通信軟件技術(shù)委員會(huì)2009年學(xué)術(shù)會(huì)議論文集[C];2009年

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

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

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

6 王萬(wàn)青;張曉輝;;改進(jìn)的A~*算法的高效實(shí)現(xiàn)[A];2009全國(guó)測(cè)繪科技信息交流會(huì)暨首屆測(cè)繪博客征文頒獎(jiǎng)?wù)撐募痆C];2009年

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

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

9 張悅;尤楓;趙瑞蓮;;利用蟻群算法實(shí)現(xiàn)基于程序結(jié)構(gòu)的主變?cè)治鯷A];第五屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議論文集[C];2008年

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

相關(guān)重要報(bào)紙文章 前1條

1 科文;VIXD算法分析Web異常[N];中國(guó)計(jì)算機(jī)報(bào);2008年

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

1 魏哲學(xué);樣本斷點(diǎn)距離問題的算法與復(fù)雜性研究[D];山東大學(xué);2015年

2 劉春明;基于增強(qiáng)學(xué)習(xí)和車輛動(dòng)力學(xué)的高速公路自主駕駛研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2014年

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

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

5 卜晨陽(yáng);演化約束優(yōu)化及演化動(dòng)態(tài)優(yōu)化求解算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年

6 劉新旺;多核學(xué)習(xí)算法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

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

8 曾國(guó)強(qiáng);改進(jìn)的極值優(yōu)化算法及其在組合優(yōu)化問題中的應(yīng)用研究[D];浙江大學(xué);2011年

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

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

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

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

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

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

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

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

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

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

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

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

10 李智明;基于改進(jìn)FastICA算法的混合語(yǔ)音盲分離[D];上海交通大學(xué);2015年

，

本文編號(hào)：1495666