【文章內(nèi)容簡(jiǎn)介】 解。 (2)由于最近插入法解決的是同一回路運(yùn)輸問(wèn)題，因此，本文在此方法基礎(chǔ)上對(duì)其進(jìn)行改進(jìn)和修正，以便能解決多回路運(yùn)輸 VRP 問(wèn)題。有改進(jìn)的方法如下： ①找到 0ic 最小的節(jié)點(diǎn) iv ，形成一個(gè)子回路（ subtour）， ? ?00,kT v v v? 。 ②在剩下的節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn) kv 。若此時(shí)回路的總貨運(yùn)量未超過(guò)車的載重限制，則繼續(xù)步驟③。否則，轉(zhuǎn)①尋找新的一條回路。 ③在子回路中找到一條路徑（ 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 加入到子回路中。若此時(shí)該回路的總路程為未超過(guò)車輛的行程限制，則繼續(xù)步驟④。否則轉(zhuǎn)步驟①，尋找新的一條回路。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 10 頁(yè) 共 20 頁(yè) ④重復(fù)步驟①和③， 直到每一個(gè)節(jié)點(diǎn)都被歸入某一個(gè)子回路中。 配送路線優(yōu)化研究 建立 VRP 模型 利用多回路運(yùn)輸問(wèn)題解決經(jīng)濟(jì)生活中出現(xiàn)的問(wèn)題，這在如今的世界中已成為一項(xiàng)重要的科學(xué)成果和生活成果。此類調(diào)配問(wèn)題的核心問(wèn)題仍是車輛調(diào)度，因而，據(jù)此對(duì)貴州中煙工業(yè)畢節(jié)卷煙廠的配送系統(tǒng)建立 VRP 模型。 基本條件：畢節(jié)卷煙廠需給旗下的 7 個(gè)分庫(kù)送貨，代號(hào)依次為 1,2,3,…… 6,7,畢節(jié)卷煙廠現(xiàn)擁有 5T 貨車 4 輛， 2T 貨車 3 輛， 5T 貨車每輛可裝載 330 件， 2T車每輛可裝載 120 件，每件卷煙 15 千克，所以盡管裝滿也不會(huì)超載。 2T 貨車每百公里耗油 8L， 5T 車每百公里耗油 12L。柴油現(xiàn)價(jià)格為 ，司機(jī)每天工資 120 元。 模型目標(biāo)：確定所需要的車輛的數(shù)目 N、車輛類型、司機(jī)數(shù)量以及各車行駛的路線，并將這些車輛指派到一個(gè)回路中，同時(shí)包括回路內(nèi)的路線安排和調(diào)度，使得運(yùn)輸總費(fèi)用最小。 限制條件： (1)出于人性化和對(duì)行車過(guò)程中的安全的考慮，當(dāng)運(yùn)輸里程超過(guò) 300 公里時(shí)，需配備兩名司機(jī)，為了防止緊急運(yùn)輸事件的發(fā)生，車輛必須當(dāng)天回到公司，去除由于裝卸貨物造成的額外運(yùn)輸距離等影響因素，各車最大運(yùn)輸距離為 500 公里。 (2) 每輛車完成任務(wù) 之后都要回到源點(diǎn) 0 處。 (3)車輛的容量限制不能超過(guò)。 2 噸的貨車最多可裝 120 件， 5噸的最多可裝330 件。 5噸貨車運(yùn)輸單價(jià)比 2噸的低，優(yōu)先使用 5 噸車，若不超過(guò) 120 件，則使用 2噸貨車。 原配送路線基本數(shù)據(jù)分析 目前，畢節(jié)卷煙廠各配送線路里程，配送任務(wù)的基本情況如表 2 所示。 表 2： 現(xiàn)有配送任務(wù)表 分庫(kù) 黔西縣 大方縣 金沙縣 赫章縣 納雍縣 織金縣 威寧縣 日需求量（件 /d） 143 187 366 65 92 146 54 配送距離（ km） 115 43 133 96 102 129 166 由上表可知，公司每天均是全車配送，司機(jī) 9 人次，所需工資 1080 元，運(yùn)輸總里程為 1834 千米，消耗的柴油 升，所需燃油費(fèi) 元，一共花費(fèi) 元。 基于節(jié)約算法的配送優(yōu)化 已知市煙草公司為 0 點(diǎn)，分別向 7 個(gè)分公司配送卷煙，其擁有 4 輛 5t 的貨車和 3 輛 2 t 的貨車， 5t 貨車最大載重量為 330 件， 2 t 貨車最大載重量為 120 件，淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 11 頁(yè) 共 20 頁(yè) 設(shè)各點(diǎn)間的距離為 c ，每輛車的載重量為 r ，各點(diǎn)需求量為 R ( i= 1 ， ? ，7) ，每輛車的行駛里程為 ( i =1，? ， 7)，且最大行駛距離≤ 500km，七星關(guān)區(qū)為 0 點(diǎn)，客戶點(diǎn) 1 ， 2 ， ? ， 7 。車輛調(diào)度采用以下方案：按需求量的多少選配車輛．如：金沙縣分庫(kù)的需求量為 366 件，可先采用 1 輛 5t 貨車進(jìn)行一次直接配送，剩余 36 件使用節(jié)約算法的原理進(jìn)行配送，其他各縣市的貨運(yùn)量均按該方法進(jìn)行整理，整理后 如表 3 所示 表 3：整理后的配送任務(wù)表 : 分庫(kù) 黔西縣 大方縣 金沙縣 赫章縣 納雍縣 織金縣 威寧縣 日需求量（件/d） 142 187 36 65 92 146 54 配送距離（ km） 115 43 133 96 102 129 166 再使用節(jié)約算法進(jìn)行路線優(yōu)化。首先確定各縣市之間的最短距離，如表 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 所示。 表 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ì)于 2 7 01 7 9361 4 3,1 7 4 3113 ??????? rrkmC kmkmCLL 5 0 03 2 21 7 421 3 321 1 51331 ?????????? ， 03??BB 故合并 1,3 兩點(diǎn)，則 31311311 ,1,32239。,17939。},3,1{39。 1 IIBBkmLrIII ???????? (I 不為空集 )。 (2)對(duì)于 33032514617939。,169 1116 ??????? rrkmC kmkmCLL 500411169212932239。 1661 ????????? ， 0,1 61 ?? BB 故 1,6 兩點(diǎn)可合并，則 kmLrIII 4 1 139。,3 2 539。},6,1,3{39。39。 1612 1 ????? , 6161 ,1 IIBB ??? (I 不為空集 )。 (3)對(duì)于 kmC 14356 ?? ，因 3 3 04 1 7923 2 539。 51 ????? rr ,故不滿足條件 (4)余下各點(diǎn)的需求量均大于 5，因此回路 03160 不能再與其它點(diǎn)合并。以下討論與剩下的點(diǎn)相關(guān)的 ijC? 。 (5)對(duì)于 kmC 14312 ?? ，因?yàn)?1以處在 03160回路中，故不滿足條件。 (6)對(duì)于 3 3 01 4 65492,1 0 0 7557 ??????? rrkmC kmkmCLL 500436100216621025775 ?????????? ， 2121 ,1 IIBB ??? (I 不為空集 )。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 13 頁(yè) 共 20 頁(yè) (7)對(duì)于 1 2 01 1 95465,87 7447 ??????? rrkmC kmkmCLL 5 0 02 7 38721 6 62964774 ?????????? ， 2121 ,1 IIBB ??? (I 不為空集 )。由于 47C? 優(yōu)于 57C? ,故合并 4,7兩點(diǎn)，則 },7,4{39。 74 ??? III 2121 ,1,27339。,11939。 IIBBkmLr ????? (I 不為空集 )。因此 0470 形成一回路。 (8)對(duì)于 3 3 02 7 9921 8 7,72 5225 ??????? rrkmC kmkmCLL 5 0 02 1 87221 0 22432552 ?????????? ， 2121 ,1 IIBB ??? (I 不為空集 ) 故合并 2,5 兩點(diǎn)，則 212152 ,1,21839。,27939。},5,2{39。 IIBBkmLrIII ???????? (I 不為空集 )。因此 0250形成一回路。 至此，合并結(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) 元。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 14 頁(yè) 共 20 頁(yè) 圖 5：節(jié)約算法優(yōu)化后的配送路線 改進(jìn)的最近插入法配送優(yōu)化 令 T={0},N={0， 1， 2?? ,7}，比較表 42 中從 0出發(fā)的所有路徑大小。因?yàn)?kmciNic i 43}71,|m i n { 020 ????? ， 1872?r ，所以就有顧客點(diǎn) 0， 2 構(gòu)成一個(gè)子回路， }0,2,0{1?T ，此時(shí) kmL 861? 。 然后在剩余顧客點(diǎn)（ 1， 3， 4， 5， 6， 7）中尋找到 0和 2中某一點(diǎn)的最小距離， kmciiNic i 56}271,|m i n { 210 ?????? 且， 因?yàn)?3 2 91 4 21 8 712 ???? rr ，所以在子回路 }0,2,0{1?T 中插入點(diǎn) 1。由于對(duì)稱性，無(wú)論將 1插入到 0和 2之間往返路徑中，結(jié)果都是一樣的，這樣，構(gòu)成了一個(gè)新的子回路 }0,2,1,0{1?T ， 32939。?r ，kmL 21439。1? 。因?yàn)樵谑Ｓ嗟狞c(diǎn)中找不到能夠滿足本回路的條件的點(diǎn)，因此本回路已完成。以下繼續(xù)找出一個(gè)最小回路進(jìn)行新回路求解。從 0出發(fā)，再找到剩余點(diǎn)中的最小子回路。因?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? 。 在剩余的點(diǎn)（ 3,5,6,7）中繼續(xù)找到 0 和 4 中某一點(diǎn)的最小距離， kmciiNic i 1 6 6}4,2,171,|m i n { 070 ?????? 且,此時(shí)形成新子回路 }0,7,4,0{2 ?T , 11939。?r , kmL 27339。2 ? 。 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。?r ， kmL 37739。2 ? 。此時(shí)形成了新的回路 }0,5,7,4,0{2 ?T 。 再次對(duì)剩余的顧客點(diǎn)按照上訴方法 進(jìn)行優(yōu)化，可構(gòu)成另子回路 }0,6,3,0{3 ?T 。 利用改進(jìn)的最近插入法得到優(yōu)化結(jié)果如表 8所示，優(yōu)化線路結(jié)果如圖 6所示。 表 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)劣性。本文將根據(jù)所需車輛數(shù)，行駛總里程，總油耗，人力資源和總費(fèi)用這些指標(biāo)，對(duì)三種 優(yōu)化后的方