【正文】 ? ，7) ，每輛車的行駛里程為 ( i =1，? ， 7)，且最大行駛距離≤ 500km，七星 關(guān)區(qū)為 0 點(diǎn)，客戶點(diǎn) 1 ， 2 ， ? ， 7 。,17 939。,169 1116 ??????? rrkmC kmkmCLL 5 0 04 1 11 6 921 2 93 2 239。39。以下討論與剩下的點(diǎn)相關(guān)的 ijC? 。由于 47C? 優(yōu)于 57C? ,故合并 4,7 兩點(diǎn)，則 },7,4{39。因此 0470形成一回路。 IIBBkmLrIII ???????? (I 不為空集 )。因?yàn)?kmciNic i 43}71,|m in{ 020 ????? ， 1872?r ，所以就有顧客點(diǎn) 0， 2 構(gòu)成一個(gè)子回路， }0,2,0{1?T ，此時(shí) kmL 861? 。1? 。因?yàn)?kmciiiNic i 96}2,171,|m i n{ 040 ??????? 且，此時(shí)654?r ，所以就有點(diǎn) 0,4 構(gòu)成一個(gè)子回路 }0,4,0{2?T ,此時(shí) kmL 1922? 。 0 3 1 2 4 7 5 6 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 15 頁(yè) 共 20 頁(yè) 再繼續(xù)尋找新的點(diǎn) kmcic i 102}6,5,3|m in{ 050 ??? ，此時(shí) 21139。 再次對(duì)剩余的顧客點(diǎn)按照上訴方法進(jìn)行優(yōu)化，可構(gòu)成另子回路 }0,6,3,0{3 ?T 。 從表 9的對(duì)比中可知，從車輛需求數(shù)的角度來(lái)看，兩種優(yōu)化后的方案與優(yōu)化前方案相比較都節(jié)約了 3/7 的車輛需求，但采用節(jié)約算法優(yōu)化后的方案需求車輛較占優(yōu)勢(shì)。優(yōu)化后的方案能減少了公司車輛的損耗和資源的浪費(fèi)，給該廠帶去更多的效益。因此，從燃油消耗的角度上考慮，節(jié)約算法也是最優(yōu)。 從支出的總費(fèi)用角度來(lái)考慮，優(yōu)化后的方案的費(fèi)用支出依次 元和 元，與原方案的為 元相比較，節(jié)約算法最優(yōu)。例如，并未考慮具體的道路信息，運(yùn)輸規(guī)章等。節(jié)約算法和改進(jìn)后的最近插入法都是解決 VRP 模型的算法。從配送中心到最終客戶的物流，在配送領(lǐng)域里，其是一個(gè)調(diào)度問題。在他的指導(dǎo)下，我不僅在論文工作方面得到了諄諄教誨，更從導(dǎo)師處認(rèn)識(shí)了嚴(yán)謹(jǐn)細(xì)致的治學(xué)態(tài)度、寬厚正直的待人之道，此當(dāng)為我輩學(xué)子之不盡的人生財(cái)富。 衷心地感謝在我完成論文的過(guò)程中給與幫助和支持的所有老師、同學(xué)和朋友！ 。 最后感謝畢節(jié)卷煙廠提供寶貴的資料。 如今，物流行業(yè)快速發(fā)展，在此背景下，畢節(jié)卷煙廠以至于整個(gè)中國(guó)的卷煙業(yè)都需要將先進(jìn)物流理論利用到企業(yè)的生產(chǎn)活動(dòng)中，并與實(shí)踐相結(jié)合，同時(shí)又考慮到現(xiàn)代產(chǎn)品具有的特殊的意義，把與第三方物流公司保持積極地合作與積極拓展自己的經(jīng)營(yíng)方式相結(jié)合，給企業(yè)注入新的血液和活力。在實(shí)際的求解過(guò)程中，應(yīng)根據(jù)配送路徑優(yōu)化的具體情況和各種算法的適用范圍，利用最適宜的求解方法，找到最終的優(yōu)化配送路線。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 18 頁(yè) 共 20 頁(yè) 結(jié) 論 本文針對(duì)畢節(jié)卷煙廠 7 個(gè)縣市配送狀況進(jìn)行了線路規(guī)劃，運(yùn)用節(jié)約算法、和改進(jìn)的最近插入法兩種方法進(jìn)行了計(jì)算分析，通過(guò)對(duì)兩種結(jié)果的對(duì)比，最后選擇出了一個(gè)最優(yōu)方案，經(jīng)過(guò)效益分析，證明了優(yōu)化后的配送里程數(shù)縮短了 674km，節(jié)約燃油 升，從而降低了每天的運(yùn)輸費(fèi)用大概 元，除此以外，節(jié)約貨車 3 臺(tái)，司機(jī) 4 人次，也使得閑置下來(lái)的貨車和司機(jī)還可以應(yīng)對(duì)一些緊急情況，提高了公司的服務(wù)質(zhì)量。但是，本文的配送距離略有超出配送最佳范圍，模型存在著一定的缺陷。兩種優(yōu)化后的方案均能使公司在人員安排上將更具有彈性，還能降低公司費(fèi)用的支出。 從燃油消耗的角度考慮，優(yōu)化后的兩種方案的消耗分別為 升和 升，與優(yōu)化前的 升相比較，兩種優(yōu)化方案也都降低了油耗量，但仍以節(jié)約算法優(yōu)化后的方案消耗更少的油。因此，在用車角度上考慮，節(jié)約算法優(yōu)化后的方案比較節(jié)省成本。 表 8：改進(jìn)后的最近插入法優(yōu)化結(jié)果 路線 運(yùn)距 運(yùn)貨量 車型 司機(jī)數(shù) 0120 214km 329 5 噸貨車 1 04750 377km 211 5 噸貨車 2 0360 455km 182 5 噸貨車 2 030 266km 330 5 噸貨車 1 由圖表可知，經(jīng)過(guò)改進(jìn)后的最近插入法進(jìn)行優(yōu)化后， 該廠每天需 5噸貨車 4輛進(jìn)行配送，司機(jī) 6 人次 ，所需工資 720 元，運(yùn)輸總里程為 1312 千米，消耗的柴油 升，所需燃油費(fèi) 元，一共花費(fèi) 元 . 圖 6：改進(jìn)的最近插入法求解線路結(jié)果 0 3 2 1 6 4 7 5 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 16 頁(yè) 共 20 頁(yè) 兩種優(yōu)化路線選擇與評(píng)價(jià) 由上文可知，在運(yùn)用節(jié)約算法和改進(jìn)后的最近插入法分別對(duì)配送線路進(jìn)行優(yōu)化后，可得到三種不同的優(yōu)化方案，因此還需要通過(guò)一系列指標(biāo)來(lái)評(píng)價(jià)方案的優(yōu)劣性。2 ? 。?r , kmL 27339。以下繼續(xù)找出一個(gè)最小回路進(jìn)行新回路求解。由于對(duì)稱性，無(wú)論將 1插入到 0 和 2 之間往返路徑中，結(jié)果都是一樣的，這樣，構(gòu)成了一個(gè)新的子回路 }0,2,1,0{1?T ， 32939。 至此，合并結(jié)束 最后得到的優(yōu)化結(jié)果如表 7，優(yōu)化路線如圖 5所示： 表 7：節(jié)約法優(yōu)化結(jié)果 路線 運(yùn)距 運(yùn)貨量 車型 司機(jī)數(shù) 03160 411km 325 5 噸貨車 2 0470 273km 119 2 噸貨車 1 0250 218km 279 5 噸貨車 1 030 258km 330 5 噸貨車 1 由圖表可知，經(jīng)過(guò)節(jié)約算法進(jìn)行優(yōu)化后， 該廠每天需 5 噸貨車 3輛和 2噸貨車 1 輛進(jìn)行配送，司機(jī) 5人次，所需工資 600 元，運(yùn)輸總里程為 1160 千米，消耗的柴油 升，所需燃油費(fèi) 元，一共花費(fèi) 元。,27 939。,11939。 (6)對(duì)于 3301465492,100 7557 ??????? rrkmC kmkmCLL 500436100216621025775 ?????????? ， 2121 ,1 IIBB ??? (I 不為空集 )。 (3)對(duì)于 kmC 14356 ?? ，因 3304179232539。,32539。 1 IIBBkmLrIII ???????? (I 不為空集 )。首先確定各縣市之間的最短距離，如表 4 所示： 表 4：各縣市里程表 縣市 畢節(jié)市 黔西縣 大方縣 金沙縣 赫章縣 納雍縣 織金縣 威寧縣 畢節(jié)市 0 115 43 133 96 102 129 166 黔西縣 0 56 74 190 124 75 260 大方縣 0 100 133 73 94 206 金沙縣 0 233 172 193 258 赫章縣 0 134 220 75 納雍縣 0 88 168 織金縣 0 258 威寧縣 0 數(shù)據(jù)來(lái)源：百度地圖 根據(jù)最短距離表，計(jì)算出用戶間的節(jié)約里程，并由大到小排列，編制節(jié)約里程 △ c 順序表，如表 5 和表 6 所示。 原配送路線基本數(shù)據(jù)分析 目前，畢節(jié)卷煙廠各配送線路里程，配送任務(wù)的基本情況如表 2所示。 (2) 每輛車完成任務(wù)之后都要回到源點(diǎn) 0處。 2T 貨車每百公里耗油 8L， 5T 車每百公 里耗油 12L。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 10 頁(yè) 共 20 頁(yè) ④重復(fù)步驟①和③，直到每一個(gè)節(jié)點(diǎn)都被歸入某一個(gè)子回路中 。否則，轉(zhuǎn)①尋找新的一條回路。 (2)由于最近插入法解決的是同一回路運(yùn)輸問題，因此，本文在此方法基礎(chǔ)上對(duì)其進(jìn)行改進(jìn)和修正，以便能解決多回路運(yùn)輸 VRP 問題。 ②在剩下的節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn) kv 。它是一個(gè)典型的 NP 難題，在大規(guī)模的線路優(yōu)化問題中無(wú)法利用它求得最優(yōu)解。從節(jié)約值中的最大的值開始，直到節(jié)約里程0 j i 0 j i 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 9 頁(yè) 共 20 頁(yè) 的隊(duì)列空為止 ,重復(fù)下列步驟 :按照節(jié)約里程 隊(duì)列從大到小的順序 ,分析客戶 i 和 j 之間合并的可能性 (是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過(guò) 2),將 i, j 連接起來(lái) ,即可令 。確定各車輛配送點(diǎn)集 12, , , mI I I??? 令 ??jIj? , j =1,2,? ,n (先采取單點(diǎn)配送 )。相應(yīng)的變化值，叫做節(jié)約距離 ijC? ，如式①所示。 ③限制條件： N 不大于 m；每一個(gè)訂單都要完成；每輛車完成任務(wù)后都要回淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 8 頁(yè) 共 20 頁(yè) 到源點(diǎn) 0v ；車輛的容量限制不能超過(guò)；特殊問題還需 考慮時(shí)窗限制；運(yùn)輸規(guī)章限制。 該問題研究目標(biāo)是：對(duì)一系列顧客需求點(diǎn)設(shè)計(jì)適當(dāng)?shù)穆肪€，使車輛有序地通過(guò)他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等），達(dá)到一定的優(yōu)化目標(biāo)（如里程最短，費(fèi)用最小，時(shí)間盡量少等）。 (2)多回路運(yùn)輸 —— VRP 模型 。線路優(yōu)化問題的常用算法，基本上分為精確算法和啟發(fā)式算法兩大類。從煙草企業(yè)的角度上看，煙草配送直接關(guān)系到企業(yè)經(jīng)濟(jì)效 益的好壞和核心競(jìng)爭(zhēng)力的強(qiáng)弱。經(jīng)綜合分析發(fā)現(xiàn)該廠所采用的配送模式的主要缺陷在于： (1)