【正文】 .................... 7 配送路線優(yōu)化研究 .............................................. 10 兩種優(yōu)化路線選擇與評(píng)價(jià) ........................................ 16 結(jié) 論 ............................................................. 18 參考文獻(xiàn) ........................................................... 19 致 謝 ............................................................. 20 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 1 頁(yè) 共 20 頁(yè) 1 引言 研究背景 今天，社會(huì)主義市場(chǎng)經(jīng)濟(jì)仍在不斷發(fā)展，物流受到了普遍重視，作為“第三利潤(rùn)源泉”，對(duì)經(jīng)濟(jì)活動(dòng)的影響也越來(lái)越明顯，成為當(dāng)前“最重要的競(jìng)爭(zhēng)領(lǐng)域”。 本課題研究意義 煙草是一種特殊的商品。狹義上則是指煙草行業(yè)在工業(yè)企業(yè)、商業(yè)企業(yè)及相互之間發(fā)生的，基于其社會(huì)職能分工的不同的煙草制品的移動(dòng)活動(dòng)，其目標(biāo)在于以更少的環(huán)節(jié)、最近的距離和最低的費(fèi)用實(shí)現(xiàn)行業(yè)最大經(jīng)濟(jì)效益，從而促進(jìn)生產(chǎn)，滿足消費(fèi)。在容易遇到的山區(qū)交通瓶頸以及各種自然災(zāi)害影響的情況下， 本文針對(duì)畢節(jié)市煙草公司各分庫(kù)的需求情況、道路交通網(wǎng)、企業(yè)車輛及運(yùn)行限制等因素進(jìn)行了較充分的分析， 建立 VRP 數(shù)學(xué)模型， 利用節(jié)約里程算法 和改進(jìn)的最近插入法對(duì)建立的模型進(jìn)行求解 。隨著客戶對(duì)產(chǎn)品多樣化和淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 2 頁(yè) 共 20 頁(yè) 差異化的要求，為了滿足客戶的需求，原始的一般送貨開(kāi)始轉(zhuǎn)向分揀、配貨、送貨一體化。無(wú)論是對(duì)于完善物流系統(tǒng)，發(fā)展企業(yè)，還是改善整個(gè)經(jīng)濟(jì)社會(huì)效益，都具有重要的作用。 (2)配送提高了終端物流的效益。 (4)配送簡(jiǎn)化事物，也使客服更加便利。同時(shí)，配送有利于靈活高度，有利于發(fā)揮物資的作用。 通過(guò)科學(xué)合理的手段制定配送路線，在配送活動(dòng)中是很重要的一個(gè)環(huán)節(jié)。 對(duì)全社會(huì)來(lái)說(shuō)，合理選擇運(yùn)輸路線還有利于節(jié)省運(yùn)輸車輛，降低車輛空載率，減少社會(huì)物流成本，對(duì)其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。 由于我國(guó)卷煙行業(yè)的特點(diǎn)，卷煙生產(chǎn)、銷售、卷煙專賣品的進(jìn)出口實(shí)行國(guó)家專賣體制下的統(tǒng)一集中管理。 國(guó)內(nèi)卷煙物流概述 進(jìn)入二十一世紀(jì)以來(lái)，中國(guó)的煙草生產(chǎn)的增長(zhǎng)速度一直保持在 3%6%之間波動(dòng)，根據(jù)中國(guó)煙草年鑒的統(tǒng)計(jì)， 20xx 年中國(guó)煙草總產(chǎn)量已達(dá)到 億支，比上一年增長(zhǎng)了 %。如今實(shí)行“一庫(kù)制”配送，使物流業(yè)務(wù)集中起來(lái)，并不斷進(jìn)行物流信息技術(shù)的推廣應(yīng)用，經(jīng)歷了從無(wú)到有，從不被重視到上升為行業(yè)核心地位的發(fā)展過(guò)程。工業(yè)生產(chǎn)發(fā)貨點(diǎn)近 100個(gè)，商業(yè)有 300多家地市級(jí)卷煙公司，近 500萬(wàn)家卷煙零售客戶。 進(jìn)入二十一世紀(jì)以后，中國(guó)卷煙行業(yè)著手以建設(shè)物流信息化重點(diǎn)工程為起跑點(diǎn)，推廣應(yīng)用了商業(yè)企業(yè)卷煙物流配送中心數(shù)字倉(cāng)儲(chǔ)管理系統(tǒng)和工商卷煙物流信息跟蹤系統(tǒng)等工程，極大地推動(dòng)了卷煙行業(yè)信息化的建設(shè)和發(fā)展?，F(xiàn)全廠 占地面積 約 32 萬(wàn)平方米，建筑面積 18 萬(wàn)平方米。 自 此 之 后，品牌集中度不斷提高，經(jīng)濟(jì) 效益 呈 明顯增長(zhǎng) 的勢(shì)頭 ，各項(xiàng)生產(chǎn)經(jīng)營(yíng)指標(biāo)不斷 更新 歷史最好水平，實(shí)現(xiàn) 畢節(jié)卷煙 新的歷史跨越，企業(yè) 亦顯示出較強(qiáng)勁的發(fā)展后勁和生命力。如圖 2所示： 圖 2:畢節(jié)市及各縣地圖 來(lái)源：百度地圖 隨著社會(huì)經(jīng)濟(jì)水平的提高，以及各種交叉因素的影響，該市各地對(duì)香煙的需求量不斷增大?，F(xiàn)在該廠采用的是“點(diǎn)到點(diǎn)”的直接配送模式．共需 7 輛貨車運(yùn)行 8車次。由于該廠每日都會(huì)配送大量的貨物，也就必定會(huì)產(chǎn)生巨大的資源浪費(fèi)。配送是物流活動(dòng)的重要環(huán)節(jié)。配送車輛調(diào)度問(wèn)題（ VRP），最早是由 Dantzig 和 Ramser 于 1959 年首次提出的，自此很快引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科的專家與運(yùn)輸計(jì)劃的設(shè)計(jì)者和管理者的極大重視，成為運(yùn) 籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點(diǎn)問(wèn)題。 針對(duì)本文研究的問(wèn)題，如何對(duì)配送線路進(jìn)行科學(xué)地優(yōu)化和整合，對(duì)配送車輛進(jìn)行合理的調(diào)度、對(duì)線路之間的工作量進(jìn)行科學(xué)的均衡，對(duì)配送車輛裝載率進(jìn)一步合理的提高，也是煙草配送線路優(yōu)化希望達(dá)到的目標(biāo)。因此， VRP（ Vehicle Routing Problem）模型也應(yīng)運(yùn)而生，成了解決多回路問(wèn)題的一個(gè)相當(dāng)成功的模型。 ②模型目標(biāo) 確定所需的車輛數(shù) N，并指派這些車輛到一個(gè)回路中，同時(shí)包括回路內(nèi)的路徑安排和調(diào)度，使總費(fèi)用最小。在上面的合并操作中，整個(gè)運(yùn)輸問(wèn)題的總運(yùn)輸距離會(huì)發(fā)生變化，如果變化后總運(yùn)輸距離下降，則稱節(jié)約了運(yùn)輸距離。 第一步 ,形成一個(gè)初始解。 第三步，對(duì)回路進(jìn)行合并。 改進(jìn)后的最近插入法 (1)TSP 模型是單回路運(yùn)輸問(wèn)題中的最為典型的一個(gè)模型， (全稱 :Traveling Salesman Problem1)，中文名稱做旅行商問(wèn)題。最近插入法由四步完成： ①找到 0ic 最小的節(jié)點(diǎn) iv ，形成一個(gè)子回路（ subtour）， ? ?00,kT v v v? 。 這樣，子回路就演變?yōu)榱艘粋€(gè) TSP 的解。若此時(shí)回路的總貨運(yùn)量未超過(guò)車的載重限制，則繼續(xù)步驟③。否則轉(zhuǎn)步驟①，尋找新的一條回路。 基本條件：畢節(jié)卷煙廠需給旗下的 7 個(gè)分庫(kù)送貨，代號(hào)依次為 1,2,3,…… 6,7,畢節(jié)卷煙廠現(xiàn)擁有 5T 貨車 4 輛， 2T貨車 3 輛， 5T貨車每輛可裝載 330 件， 2T車每輛可裝載 120 件，每件卷煙 15 千克，所以盡管裝滿也不會(huì)超載。 限制條件： (1)出于人性化和對(duì)行車過(guò)程中的安全的考慮，當(dāng)運(yùn)輸里程超過(guò) 300 公里時(shí)，需配備兩名司機(jī)，為了防止緊急運(yùn)輸事件的發(fā)生，車輛必須當(dāng)天回到公司，去除由于裝卸貨物造成的額外運(yùn)輸距離等影響因素，各車最大運(yùn)輸距離為 500 公里。 5噸貨車運(yùn)輸單價(jià)比 2 噸的低，優(yōu)先使用 5噸車，若不超過(guò) 120 件，則使用 2噸貨車。車輛調(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)化。},3,1{39。 1661 ????????? ， 0,1 61 ?? BB 故 1,6 兩點(diǎn)可合并，則 kmLrIII 41139。 1612 1 ????? , 6161 ,1 IIBB ??? (I 不為空集 )。 (5)對(duì)于 kmC 14312 ?? ，因?yàn)?1以處在 03160回路中，故不滿足條件。 74 ??? III 2121 ,1,27339。 (8)對(duì)于 33 027 99218 7,72 5225 ??????? rrkmC kmkmCLL 5 0 02 1 87221 0 22432552 ?????????? ， 2121 ,1 IIBB ??? (I 不為空集 ) 故合并 2,5 兩點(diǎn)，則 212152 ,1,21 839。因此 0250 形成一回路。 然后在剩余顧客點(diǎn)（ 1， 3， 4， 5， 6， 7）中尋找到 0和 2中某一點(diǎn)的最小距離 ， kmciiNic i 56}271,|m in { 210 ?????? 且， 因?yàn)?32914218712 ???? rr ，所以在子回路 }0,2,0{1?T 中插入點(diǎn) 1。因?yàn)樵谑Ｓ嗟狞c(diǎn)中找不到能夠滿足本回路的條件的點(diǎn)，因此本回路已完成。 在剩余的點(diǎn)（ 3,5,6,7）中繼續(xù)找到 0和 4 中某一點(diǎn)的最小距離， kmciiNic i 166}4,2,171,|m i n{ 070 ?????? 且,此時(shí)形成新子回路 }0,7,4,0{2 ?T , 11939。?r ， kmL 37739。 利用改進(jìn)的最近插入法得到優(yōu)化結(jié)果如表 8 所示，優(yōu)化線路結(jié)果如圖 6所示。使畢節(jié)卷煙廠的車輛安排使用上具有更大彈性。因此，淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 17 頁(yè) 共 20 頁(yè) 從運(yùn)輸里程的角度考慮，優(yōu)化后的方案仍以 節(jié)約算法最優(yōu)。 從該廠人力資源消耗角度來(lái)考慮，優(yōu)化后的方案所需司機(jī)依次為 5， 6 人次，減少人力的消耗為 4， 3 人次。 結(jié)合車次需求數(shù)，總運(yùn)輸里程，燃油消耗，人力資源消耗，支出的總費(fèi)用五個(gè)角度一齊分析，節(jié)約算法均為最優(yōu)的優(yōu)化方案。因此，畢節(jié)卷煙 廠還應(yīng)該根據(jù)實(shí)際情況合理選擇配送方案。對(duì)于解決有關(guān)問(wèn)題，這類算法雖然能夠比較快的得出解決方法，但其優(yōu)劣往往也是取決于算法設(shè)計(jì)者的真實(shí)經(jīng)驗(yàn)到的事實(shí)以及處理樣本體積的大小。如果能有效地在企業(yè)的車輛調(diào)度和人員安排中運(yùn)用科學(xué)的優(yōu)化模型和算法，就會(huì)使得物流中心運(yùn)作更高效，成本得到控制，企業(yè)的效益也會(huì)大大的提高。在此，謹(jǐn)向趙老師表示真誠(chéng)的感謝和崇高的敬意 ! 其次 ，還要感謝淮海工學(xué)院所有給過(guò)學(xué)生們微薄關(guān)心和教育的老師們，并感謝學(xué)校圖書館在求學(xué)期間的相伴和對(duì)論文的幫