【正文】 同時(shí)，感謝評(píng)閱本文的各位老師，敬請(qǐng)?zhí)岢鰧氋F的意見(jiàn)，并予以指正。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 19 頁(yè) 共 20 頁(yè) 參 考 文 獻(xiàn) [1] 陳輝 .劉春草 .朱志軍 .物流配送管理中的路徑優(yōu)化問(wèn)題研究 [J].西安電子科技大學(xué)學(xué)報(bào) .20xx(5). [2] 張得志 .謝如鶴 .羅榮武 .物流配送網(wǎng)絡(luò)優(yōu)化模型及其求解算法 [J].武漢理工大學(xué)學(xué)報(bào) .20xx(4). [3] 賈楠 .任遠(yuǎn) .物流配送問(wèn)題中 VRP 的數(shù)學(xué)模型及其求解算法 ,北京交通大學(xué) .20xx(4). [4] 劉志強(qiáng) .丁一鵬 .盛煥華 .物流配送系統(tǒng)設(shè)計(jì) .北京 .清華大學(xué)出版社 .20xx. [5] 李軍 .郭耀煌 .物流配送車(chē)輛優(yōu)化調(diào)度理論與方法 . 北京中國(guó)物資出版社 .20xx. [6] 梁晨著 .如何進(jìn)行物流服務(wù)管理 .北京 .北京大學(xué)出版社 .20xx. [7] 張鐸 .林自葵 .電子商務(wù)與現(xiàn)代物流 .北京 .清華大學(xué)出版社 .20xx. [8] 陳子俠 .張藥 .陳穎 .物流中心規(guī)劃設(shè)計(jì) .北京 .高等教育出版社 .20xx. [9] 段朝輝 .益陽(yáng)地區(qū)煙草配送系統(tǒng)整合方案 [J].企業(yè)技術(shù)開(kāi)發(fā) .20xx. [10] 杜亮 .重慶煙草物流研究 [J].中國(guó)市場(chǎng) .20xx. [11] 葉小龍 .魏國(guó)辰 .煙草企業(yè)物流配送網(wǎng)絡(luò)研究 [J].中國(guó)流通經(jīng)濟(jì) .20xx(4). [12] 謝鵬 .配送時(shí)間及配送陳本研究 [J].物流科技 20xx(3). [13] 謝勝利 .求解 TSP 問(wèn)題的一種改進(jìn)的遺傳算法 .計(jì)算機(jī)工程與應(yīng)用 .20xx. [14] 劉云忠 .宣慧玉 .車(chē)輛路徑問(wèn)題的模型及算法研究綜述 [J].管理工程學(xué)報(bào) .20xx. 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 20 頁(yè) 共 20 頁(yè) 致 謝 值此拙作完成之際，我首先要衷心地感謝 趙中奇指導(dǎo)老師 ，他為本人從事這一方向的研究給予了充分的鼓勵(lì)和悉心的指導(dǎo)。 目前，對(duì)配送成本要求最低和滿足客戶對(duì)時(shí)間的高要求已成為眾多企業(yè)在配送中的主要問(wèn)題，而這部分問(wèn)題主要是研究物流配送路徑優(yōu)化模型和算法 來(lái)解決。 對(duì)車(chē)輛路徑問(wèn)題的求解方法有很多種，本文主要采用的兩種方法盡管都能 夠?qū)η蠼饪尚械呐渌吐肪€方案得得出整體的優(yōu)化結(jié)果，但是這只能是可行解而不是精確解。在計(jì)算過(guò)程中也將一些因素理想化了，與實(shí)際情況不完全相符。因此 ，從該廠人力資源消耗的角度考慮，節(jié)約算法和改進(jìn)后的最近插入法都使人力資源得到了優(yōu)化。配送線路優(yōu)化后，不僅能減少畢節(jié)卷煙廠配送過(guò)程中燃油費(fèi)用的支出，還能降低社會(huì)資源的浪費(fèi)。 表 9：優(yōu)化結(jié)果對(duì)比表 狀態(tài) 優(yōu)化前 優(yōu)化后 節(jié)約算法 改進(jìn)后的最 近插入法 各車(chē)型車(chē)次(次 ) 2t 4 1 0 5t 4 3 4 總運(yùn)輸里程 (km) 1834 1160 1312 節(jié)約里程數(shù)（ km） 674 522 油耗（ L） 節(jié)約油耗（ L） 司機(jī)（次） 9 5 6 節(jié)約人力（次） 4 3 總費(fèi)用（元） 節(jié)約費(fèi)用（元） 從總運(yùn)輸里程角度考慮，優(yōu)化后的兩種方案的總運(yùn)輸里程分別為 1160 千米和 1312 千米，與優(yōu)化前的 1834 千米相比較，均減少了車(chē)輛行駛的里程數(shù)。本文將根據(jù)所需車(chē)輛數(shù)，行駛總里程，總油耗，人力資源和總費(fèi)用這些指標(biāo)，對(duì)三種優(yōu)化后的方案進(jìn)行評(píng)價(jià)分析，評(píng)價(jià)分析如表 9所示。此時(shí)形成了新的回路 }0,5,7,4,0{2 ?T 。2 ? 。從 0 出發(fā)，再找到剩余點(diǎn)中的最小子回路。?r ，kmL 21439。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 14 頁(yè) 共 20 頁(yè) 圖 5：節(jié)約算法優(yōu)化后的配送路線 改進(jìn)的最近插入法配送優(yōu)化 令 T={0},N={0， 1， 2?? ,7}，比較表 42 中從 0 出發(fā)的所有路徑大小。},5,2{39。 IIBBkmLr ????? (I不為空集 )。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 13 頁(yè) 共 20 頁(yè) (7)對(duì)于 12 011 95465,87 7447 ??????? rrkmC kmkmCLL 5 0 02 7 38721 6 62964774 ?????????? ， 2121 ,1 IIBB ??? (I 不為空集 )。 51 ????? rr ,故不滿足條件 (4)余下各點(diǎn)的需求量均大于 5，因此回路 03160 不能再與其它點(diǎn)合并。},6,1,3{39。 (2)對(duì)于 33032514617939。 表 5：節(jié)約里程項(xiàng)目 0 畢節(jié)市 1 黔西縣 2 大方縣 3 金沙縣 4 赫章縣 5 納雍縣 6 織金縣 7 威寧縣 1 黔西縣 102 174 21 93 169 21 2 大方縣 76 6 72 78 3 3 金沙縣 4 63 69 41 4 赫章縣 64 5 87 5 納雍縣 143 100 6 織金縣 37 7 威寧縣 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 12 頁(yè) 共 20 頁(yè) 表 6：節(jié)約里程表從大到小排列 連接點(diǎn) 節(jié)約里程 連接點(diǎn) 節(jié)約里程 1—— 3 174 4—— 5 64 1—— 6 169 3—— 5 63 5—— 6 143 3—— 7 41 1—— 2 102 6—— 7 37 5—— 7 100 1—— 4 21 1—— 5 93 1—— 7 21 4—— 7 87 2—— 4 6 2—— 6 78 4—— 6 5 2—— 3 76 2—— 7 3 2—— 5 72 3—— 4 4 3—— 6 69 最后，按節(jié)約里程從大到小合并路徑 (1)對(duì)于 27 017 93614 3,17 4 3113 ??????? rrkmC kmkmCLL 5 0 03 2 21 7 421 3 321 1 51331 ?????????? ， 031 ??BB 故合并 1,3 兩點(diǎn)，則 31311311 ,1,32 239。 表 2： 現(xiàn)有配送任務(wù)表 分庫(kù) 黔西縣 大方縣 金沙縣 赫章縣 納雍縣 織金縣 威寧縣 日需求量（件 /d） 143 187 366 65 92 146 54 配送距離（ km） 115 43 133 96 102 129 166 由上表可知，公司每天均是全 車(chē)配送，司機(jī) 9 人次，所需工資 1080 元，運(yùn)輸總里程為 1834 千米，消耗的柴油 升，所需燃油費(fèi) 元，一共花費(fèi) 元。 (3)車(chē)輛的 容量限制不能超過(guò)。柴油現(xiàn)價(jià)格為 ，司機(jī)每天工資 120 元。 配送路線優(yōu)化研究 建立 VRP 模型 利用多回路運(yùn)輸問(wèn)題解決經(jīng)濟(jì)生活中出現(xiàn)的問(wèn)題，這在如今的世界中已成為一項(xiàng)重要的科學(xué)成果和生活成果。 ③在子回路中找到一條路徑（ i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點(diǎn) iv 插入到節(jié)點(diǎn) iv ， jv 之間，用兩條新的路徑 (i， k)，（ k， j）代替原來(lái)的路徑（ i， j），并將節(jié)點(diǎn) kv 加入到子回路中。有改進(jìn)的方法如下： ①找到 0ic 最小的節(jié)點(diǎn) iv ，形成一個(gè)子回路（ subtour）， ? ?00,kT v v v? 。 ③在子回路中找到一條路徑（ i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點(diǎn) iv 插入到節(jié)點(diǎn) iv ， jv 之間，用兩條新的路徑 (i， k)，（ k， j）代替原來(lái)的路徑（ i， j），并將節(jié)點(diǎn) kv 加入到子回路中。而最近插入法就是一種解決此問(wèn)題的啟發(fā)式算法。i i j jI I I I? ? ? ? ?。 第二步 ,進(jìn)行節(jié)約度的計(jì)算。 ij io oj jiC c c c? ? ? ? ① 調(diào)整過(guò)程如圖 4 所示。 節(jié)約算法基本原理及主要步驟 (1)節(jié)約算法（ Saving Algorithm）是用來(lái)解決運(yùn)輸車(chē)輛數(shù)目不確定的 VRP問(wèn)題，它是目前用來(lái)解決 VRP 模型最有名的啟發(fā)式算法。它涉及了多輛交通工具的服務(wù)對(duì)象的選擇和路徑 確定兩方面問(wèn)題。多回路運(yùn)輸問(wèn)題是目前很普遍的一種調(diào)配問(wèn)題，尤其對(duì)于有多數(shù)服務(wù)對(duì)象的實(shí)體，例如一個(gè)擁有多客戶的企業(yè)。由于 VRP 問(wèn)題是 NP 困難問(wèn)題，而尋找近似算法更適合于實(shí)際情況，因此啟發(fā)式算法就成了備受關(guān)注的解決方法。配送線路規(guī)劃是否合理，也將直接影響配送成本高低、工作效率快慢和服務(wù)質(zhì)量?jī)?yōu)劣。顯然，為了實(shí)現(xiàn)以上目標(biāo)，就要對(duì)配送過(guò)程進(jìn)行合理規(guī)劃，這一點(diǎn)可以通過(guò)改進(jìn)運(yùn)輸方式、進(jìn)行線路規(guī)劃等來(lái)實(shí)現(xiàn)。其配送模式如圖 3 所示．共需 7 輛貨車(chē) 8車(chē)次。需求量大的縣市日需求量達(dá)到了 300 多件，而需求量小的縣市僅為 50 多件。 20xx 年下半年 進(jìn)行整合 并入貴州中煙工業(yè)公司，作為工業(yè)公司的一個(gè)生產(chǎn)廠，年生產(chǎn)能力達(dá) 45 萬(wàn)箱。畢節(jié)卷煙廠過(guò)去曾得到過(guò)較快發(fā)展， 但是 由于各種內(nèi)外因素及市場(chǎng) 都 發(fā)生了變化， 到 “九五 ”后期，企業(yè)效益大幅下滑，很快 又 跌入低谷。有效地提高了工作效率、低了物流成本，提升了服務(wù)質(zhì)量和管理水平。這些網(wǎng)絡(luò)上節(jié)點(diǎn)的物流基本都是獨(dú)立多點(diǎn)對(duì)多點(diǎn)的關(guān)系，形成了繁雜的物流網(wǎng)絡(luò)，