【正文】 據(jù)用戶要求，對物品進(jìn)行揀選、加工、包裝、分割、組配等作業(yè)，并按時送達(dá)指定地點(diǎn)的物流活動。無論是對于完善物流系統(tǒng)，發(fā)展企業(yè)，還是改善整個經(jīng)濟(jì)社會效益，都具有重要的作用。上世紀(jì)五十年代以來，高水平的干線運(yùn)輸一直呼喚著支線運(yùn)輸和小搬運(yùn)配套，但隨著物流技術(shù)的不斷發(fā)展，小搬運(yùn)和支線運(yùn)輸在靈活性、服務(wù)性和適應(yīng)性上逐漸表現(xiàn)出欠缺，使得出現(xiàn)運(yùn)力不合理、運(yùn)輸成本過高等不良狀況。 (2)配送提高了終端物流的效益。 (3)配送通過集中庫存使企業(yè)實(shí)現(xiàn)低庫存或零庫存。 (4)配送簡化事物，也使客服更加便利。 (5)配送利于降低整個社會的物資總體庫存水平。同時，配送有利于靈活高度，有利于發(fā)揮物資的作用。 配送路線優(yōu)化的意義 配送路線是否合理在配送決策系統(tǒng)中占據(jù)著重要的地位，其直接影響著物流成本的高低。 通過科學(xué)合理的手段制定配送路線，在配送活動中是很重要的一個環(huán)節(jié)。 (2)可以加快物流速度，使貨物更準(zhǔn)時、快速地送到客戶的手中，從而提高淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 3 頁 共 20 頁 客戶滿意度。 對全社會來說，合理選擇運(yùn)輸路線還有利于節(jié)省運(yùn)輸車輛，降低車輛空載率，減少社會物流成本，對其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。 3 貴州中煙公司畢節(jié)卷煙廠的配送的現(xiàn)狀 煙草物流配送的特點(diǎn) 煙草物流是指卷煙和其下游零售商及最終消 費(fèi)者之間從供應(yīng)地向接收地的實(shí)體流動過程，包括了運(yùn)輸、儲存、裝卸、搬運(yùn)、分揀、配送、信息處理等基本活動。 由于我國卷煙行業(yè)的特點(diǎn)，卷煙生產(chǎn)、銷售、卷煙專賣品的進(jìn)出口實(shí)行國家專賣體制下的統(tǒng)一集中管理。各級卷煙公司又下設(shè)若干生產(chǎn)廠，并作為小區(qū)域的地方中心總庫，進(jìn)而又對其下的各個分庫進(jìn)行配送，由各分庫物流中轉(zhuǎn)中心承擔(dān)最終配送到客戶。 國內(nèi)卷煙物流概述 進(jìn)入二十一世紀(jì)以來，中國的煙草生產(chǎn)的增長速度一直保持在 3%6%之間波動，根據(jù)中國煙草年鑒的統(tǒng)計， 20xx 年中國煙草總產(chǎn)量已達(dá)到 億支，比上一年增長了 %。 表 1 20xx— 20xx 年度中國各類煙草總產(chǎn)量（單位：億支） 年份（年） 20xx 20xx 20xx 20xx 總產(chǎn)量（億支） 增長率（ %） 數(shù)據(jù)來源：《中國煙草年鑒》 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 4 頁 共 20 頁 圖 1： 20xx— 20xx 年度中國煙草總產(chǎn)量變化情況（單位：億支） 來源：《中國煙草統(tǒng)計年鑒》 中國卷煙行業(yè)是國 民經(jīng)濟(jì)的重要支柱產(chǎn)業(yè)。如今實(shí)行“一庫制”配送，使物流業(yè)務(wù)集中起來，并不斷進(jìn)行物流信息技術(shù)的推廣應(yīng)用，經(jīng)歷了從無到有，從不被重視到上升為行業(yè)核心地位的發(fā)展過程。在物流活動中，企業(yè)缺乏一體化和合理化管理的意識和能力，對各個環(huán)節(jié)的分工與合作，規(guī)范服務(wù)、無縫銜接等方面有待加強(qiáng)。工業(yè)生產(chǎn)發(fā)貨點(diǎn)近 100個，商業(yè)有 300多家地市級卷煙公司，近 500萬家卷煙零售客戶。這些網(wǎng)絡(luò)上節(jié)點(diǎn)的物流基本都是獨(dú)立多點(diǎn)對多點(diǎn)的關(guān)系，形成了繁雜的物流網(wǎng)絡(luò)，使得資源無法充分利用。 進(jìn)入二十一世紀(jì)以后，中國卷煙行業(yè)著手以建設(shè)物流信息化重點(diǎn)工程為起跑點(diǎn)，推廣應(yīng)用了商業(yè)企業(yè)卷煙物流配送中心數(shù)字倉儲管理系統(tǒng)和工商卷煙物流信息跟蹤系統(tǒng)等工程，極大地推動了卷煙行業(yè)信息化的建設(shè)和發(fā)展。有效地提高了工作效率、低了物流成本，提升了服務(wù)質(zhì)量和管理水平?，F(xiàn)全廠 占地面積 約 32 萬平方米，建筑面積 18 萬平方米。畢節(jié)卷煙廠過去曾得到過較快發(fā)展， 但是 由于各種內(nèi)外因素及市場 都 發(fā)生了變化， 到 “九五 ”后期，企業(yè)效益大幅下滑，很快 又 跌入低谷。 自 此 之 后，品牌集中度不斷提高，經(jīng)濟(jì) 效益 呈 明顯增長 的勢頭 ，各項(xiàng)生產(chǎn)經(jīng)營指標(biāo)不斷 更新 歷史最好水平，實(shí)現(xiàn) 畢節(jié)卷煙 新的歷史跨越，企業(yè) 亦顯示出較強(qiáng)勁的發(fā)展后勁和生命力。 20xx 年下半年 進(jìn)行整合 并入貴州中煙工業(yè)公司，作為工業(yè)公司的一個生產(chǎn)廠，年生產(chǎn)能力達(dá) 45 萬箱。如圖 2所示： 圖 2:畢節(jié)市及各縣地圖 來源：百度地圖 隨著社會經(jīng)濟(jì)水平的提高，以及各種交叉因素的影響，該市各地對香煙的需求量不斷增大。需求量大的縣市日需求量達(dá)到了 300 多件，而需求量小的縣市僅為 50 多件。現(xiàn)在該廠采用的是“點(diǎn)到點(diǎn)”的直接配送模式．共需 7 輛貨車運(yùn)行 8車次。其配送模式如圖 3 所示．共需 7 輛貨車 8車次。由于該廠每日都會配送大量的貨物，也就必定會產(chǎn)生巨大的資源浪費(fèi)。顯然，為了實(shí)現(xiàn)以上目標(biāo)，就要對配送過程進(jìn)行合理規(guī)劃，這一點(diǎn)可以通過改進(jìn)運(yùn)輸方式、進(jìn)行線路規(guī)劃等來實(shí)現(xiàn)。配送是物流活動的重要環(huán)節(jié)。配送線路規(guī)劃是否合理，也將直接影響配送成本高低、工作效率快慢和服務(wù)質(zhì)量優(yōu)劣。配送車輛調(diào)度問題（ VRP），最早是由 Dantzig 和 Ramser 于 1959 年首次提出的，自此很快引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、物流科學(xué)、計算機(jī)應(yīng)用等學(xué)科的專家與運(yùn)輸計劃的設(shè)計者和管理者的極大重視，成為運(yùn) 籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點(diǎn)問題。由于 VRP 問題是 NP 困難問題，而尋找近似算法更適合于實(shí)際情況，因此啟發(fā)式算法就成了備受關(guān)注的解決方法。 針對本文研究的問題，如何對配送線路進(jìn)行科學(xué)地優(yōu)化和整合，對配送車輛進(jìn)行合理的調(diào)度、對線路之間的工作量進(jìn)行科學(xué)的均衡，對配送車輛裝載率進(jìn)一步合理的提高，也是煙草配送線路優(yōu)化希望達(dá)到的目標(biāo)。多回路運(yùn)輸問題是目前很普遍的一種調(diào)配問題，尤其對于有多數(shù)服務(wù)對象的實(shí)體，例如一個擁有多客戶的企業(yè)。因此， VRP（ Vehicle Routing Problem）模型也應(yīng)運(yùn)而生，成了解決多回路問題的一個相當(dāng)成功的模型。它涉及了多輛交通工具的服務(wù)對象的選擇和路徑 確定兩方面問題。 ②模型目標(biāo) 確定所需的車輛數(shù) N，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使總費(fèi)用最小。 節(jié)約算法基本原理及主要步驟 (1)節(jié)約算法（ Saving Algorithm）是用來解決運(yùn)輸車輛數(shù)目不確定的 VRP問題，它是目前用來解決 VRP 模型最有名的啟發(fā)式算法。在上面的合并操作中，整個運(yùn)輸問題的總運(yùn)輸距離會發(fā)生變化，如果變化后總運(yùn)輸距離下降，則稱節(jié)約了運(yùn)輸距離。 ij io oj jiC c c c? ? ? ? ① 調(diào)整過程如圖 4 所示。 第一步 ,形成一個初始解。 第二步 ,進(jìn)行節(jié)約度的計算。 第三步，對回路進(jìn)行合并。i i j jI I I I? ? ? ? ?。 改進(jìn)后的最近插入法 (1)TSP 模型是單回路運(yùn)輸問題中的最為典型的一個模型， (全稱 :Traveling Salesman Problem1)，中文名稱做旅行商問題。而最近插入法就是一種解決此問題的啟發(fā)式算法。最近插入法由四步完成： ①找到 0ic 最小的節(jié)點(diǎn) iv ，形成一個子回路（ subtour）， ? ?00,kT v v v? 。 ③在子回路中找到一條路徑（ i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點(diǎn) iv 插入到節(jié)點(diǎn) iv ， jv 之間，用兩條新的路徑 (i， k)，（ k， j）代替原來的路徑（ i， j），并將節(jié)點(diǎn) kv 加入到子回路中。 這樣，子回路就演變?yōu)榱艘粋€ TSP 的解。有改進(jìn)的方法如下： ①找到 0ic 最小的節(jié)點(diǎn) iv ，形成一個子回路（ subtour）， ? ?00,kT v v v? 。若此時回路的總貨運(yùn)量未超過車的載重限制，則繼續(xù)步驟③。 ③在子回路中找到一條路徑（ i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點(diǎn) iv 插入到節(jié)點(diǎn) iv ， jv 之間，用兩條新的路徑 (i， k)，（ k， j）代替原來的路徑（ i， j），并將節(jié)點(diǎn) kv 加入到子回路中。否則轉(zhuǎn)步驟①，尋找新的一條回路。 配送路線優(yōu)化研究 建立 VRP 模型 利用多回路運(yùn)輸問題解決經(jīng)濟(jì)生活中出現(xiàn)的問題，這在如今的世界中已成為一項(xiàng)重要的科學(xué)成果和生活成果。 基本條件：畢節(jié)卷煙廠需給旗下的 7 個分庫送貨，代號依次為 1,2,3,…… 6,7,畢節(jié)卷煙廠現(xiàn)擁有 5T 貨車 4 輛， 2T貨車 3 輛， 5T貨車每輛可裝載 330 件， 2T車每輛可裝載 120 件，每件卷煙 15 千克，所以盡管裝滿也不會超載。柴油現(xiàn)價格為 ，司機(jī)每天工資 120 元。 限制條件： (1)出于人性化和對行車過程中的安全的考慮，當(dāng)運(yùn)輸里程超過 300 公里時，需配備兩名司機(jī)，為了防止緊急運(yùn)輸事件的發(fā)生，車輛必須當(dāng)天回到公司，去除由于裝卸貨物造成的額外運(yùn)輸距離等影響因素，各車最大運(yùn)輸距離為 500 公里。 (3)車輛的 容量限制不能超過。 5噸貨車運(yùn)輸單價比 2 噸的低，優(yōu)先使用 5噸車，若不超過 120 件，則使用 2噸貨車。 表 2： 現(xiàn)有配送任務(wù)表 分庫 黔西縣 大方縣 金沙縣 赫章縣 納雍縣 織金縣 威寧縣 日需求量（件 /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) 元。車輛調(diào)度采用以下方案：按需求量的多少選配車輛．如：金沙縣分庫的需求量為 366 件，可先采用 1 輛 5t 貨車進(jìn)行一次