中煙工業(yè)畢節(jié)卷煙廠配送路線優(yōu)化畢業(yè)

1、Good is good, but better carries it.精益求精，善益求善。中煙工業(yè)畢節(jié)卷煙廠配送路線優(yōu)化畢業(yè)配送是物流活動中直接與消費者相連的重要的環(huán)節(jié)，在物流的各項成本中，配送成本占了相 當(dāng)高的比例本 科 畢 業(yè) 論 文貴州中煙工業(yè)畢節(jié)卷煙廠配送路線優(yōu)化The Optimization of Distribution Route in Bijie Tobacco Factory ,Guizhou學(xué) 院： 商學(xué)院 專業(yè)班級： 物流管理 學(xué)生姓名： XXX 學(xué) 號： 000000000 指導(dǎo)教師： XXX（教授） 2013年 6 月畢業(yè)論文中文摘要貴州中煙工業(yè)畢節(jié)卷煙廠配送路線

2、優(yōu)化摘 要：在當(dāng)今社會，面對日益競爭激烈的市場環(huán)境，各個企業(yè)都在試圖增加自己的競爭優(yōu)勢。物流已經(jīng)作為第三利潤源逐漸被各企業(yè)所接受。對于大型國有壟斷企業(yè)來說，物流成本在企業(yè)總成本中占有重要地位。大部分國有企業(yè)也覺察到自身物流上的不足，并將目光逐漸定位在降低物流成本上。而在整個物流活動中，運輸是最重要一個環(huán)節(jié)，直接影響著企業(yè)的物流成本的高低。因此，對于物流運輸路線的優(yōu)化，可以有效的控制并降低物流費用，降低企業(yè)的成本，從而增加企業(yè)利潤。本文以貴州中煙工業(yè)畢節(jié)卷煙廠物流配送路線為研究對象，首先對其現(xiàn)有配送路線進(jìn)行詳細(xì)的研究與分析，找出其存在的問題，再根據(jù)企業(yè)自身狀況與畢節(jié)市所處的山區(qū)交通特點，從系統(tǒng)的

3、角度出發(fā)，應(yīng)用相關(guān)數(shù)學(xué)優(yōu)化模型，運用不同方法對其配送路線進(jìn)行了優(yōu)化，最后評價并選擇適合該廠對其下七家分庫配送的最優(yōu)方法，提高了公司的競爭力和物流意識，節(jié)約了物流成本，增加了企業(yè)收益。關(guān)鍵詞：配送；數(shù)學(xué)優(yōu)化；路線優(yōu)化畢業(yè)論文外文摘要The optimization of distribution route in Bijie Tobacco Factory ,GuizhouAbstract: In today's society, facing the increasingly competitive market environment, all companies are tryin

4、g to increase their competitive advantage. Logistics has been gradually accepted by each enterprise as a third profit source. Especially for production and processing enterprises, the logistics cost plays an important role in the total cost of enterprise. Most of the enterprises would have been focu

5、s on reducing the logistics cost. distribution logistics is the last link in the logistics activity, directly connecting businesses with customers, directly affecting the corporate profits. A good distibution logistics route, not only can increase sales proceeds, but also can improve service level a

6、nd improve customer satisfaction to attract more customers. Therefore, improving and optimizing distribution logistics route can effectively restrict the logistics costs, reduce the cost of enterprise. Finally, it will increase the corporate profits.This paper takes Bijie Tobacco Facatory as a resea

7、rch object. First, researches and analysis the current distribution logistics system in detail, pointing out the problems of business distribution logistics route, and from the point of view of the system, it optimizes the distribution logistics route according to the condition and the characteristi

8、cs of the distribution logistics route of Bijie, with the related theory. Establishing a distribution logistics route must suitable for the development of the enterprise, improve the company's competitiveness and the awareness of the logistics, save the logistics cost and increase enterprise pro

9、fits.Keywords: distribution;mathematical optimization;route optimization目 錄1 引言01.1 研究背景01.2 本課題研究意義02 物流配送概述02.1 物流配送概念02.2 物流配送的功能12.3 配送路線優(yōu)化的意義13 貴州中煙公司畢節(jié)卷煙廠的配送的現(xiàn)狀23.1 煙草物流配送的特點23.2 國內(nèi)卷煙物流概述23.3 貴州中煙工業(yè)畢節(jié)卷煙廠物流配送的現(xiàn)狀43.3.1畢節(jié)卷煙廠概述43.3.2畢節(jié)卷煙廠配送現(xiàn)狀43.3.3 畢節(jié)卷煙廠物流配送存在的問題54 畢節(jié)卷煙廠配送路線優(yōu)化分析64.1 物流配送路線優(yōu)化模型及方法描

10、述64.1.1 VRP模型64.1.2 節(jié)約算法基本原理及主要步驟74.1.3 改進(jìn)后的最近插入法84.2 配送路線優(yōu)化研究94.2.1 建立VRP模型94.2.2 原配送路線基本數(shù)據(jù)分析94.2.4 改進(jìn)的最近插入法配送優(yōu)化134.3 兩種優(yōu)化路線選擇與評價15結(jié) 論17參 考 文 獻(xiàn)18致 謝19251 引言1.1 研究背景今天，社會主義市場經(jīng)濟(jì)仍在不斷發(fā)展，物流受到了普遍重視，作為“第三利潤源泉”，對經(jīng)濟(jì)活動的影響也越來越明顯，成為當(dāng)前“最重要的競爭領(lǐng)域”。配送也在現(xiàn)代物流中承擔(dān)著重要環(huán)節(jié)，作為連接生產(chǎn)與消費之間的一種中介服務(wù)。配送總是根據(jù)客戶的訂貨要求(包括貨物種類、數(shù)量和時間等方面的

11、要求)，在物流中心(包括配送中心、倉庫、車站、港口等)進(jìn)行分貨、配貨工作，并及時地將配好的貨物送交到收貨人。隨著物流的全球化、信息化及一體化,配送在整個物流系統(tǒng)中的作用變得越來越重要。1.2 本課題研究意義煙草是一種特殊的商品。在我國，由于其高稅率性和對人體健康有一定的危害性，國家對其實行專賣專營。當(dāng)然，目前我國的煙草物流也是社會物流的重要的組成部分。一般所講的煙草物流廣義上是指在整個流通環(huán)節(jié)中，煙草及其相關(guān)制品及原輔料從生產(chǎn)、收購、儲存、運輸、加工到銷售服務(wù)整個過程中實物的運動以及由此而產(chǎn)生的所有附加經(jīng)濟(jì)增值活動。狹義上則是指煙草行業(yè)在工業(yè)企業(yè)、商業(yè)企業(yè)及相互之間發(fā)生的，基于其社會職能分工的

12、不同的煙草制品的移動活動，其目標(biāo)在于以更少的環(huán)節(jié)、最近的距離和最低的費用實現(xiàn)行業(yè)最大經(jīng)濟(jì)效益，從而促進(jìn)生產(chǎn)，滿足消費。配送在煙草物流的整個活動中的重要性，也表現(xiàn)在其直接與消費者相連的這一環(huán)節(jié)，在物流的各項成本中，占了相當(dāng)高比例的成本。因此,卷煙物流配送線路是否合理，也直接影響著配送的速度、成本和效益等。如何科學(xué)合理地確定配送活動中的配送線路是一項非常重要的工作。在容易遇到的山區(qū)交通瓶頸以及各種自然災(zāi)害影響的情況下，本文針對畢節(jié)市煙草公司各分庫的需求情況、道路交通網(wǎng)、企業(yè)車輛及運行限制等因素進(jìn)行了較充分的分析，建立VRP數(shù)學(xué)模型，利用節(jié)約里程算法和改進(jìn)的最近插入法對建立的模型進(jìn)行求解。最后對兩種

13、方法求得的結(jié)果進(jìn)行比較分析，以實現(xiàn)該廠合理的線路運輸，可以有效地節(jié)約運輸時間，增加車輛利用率，從而降低運輸成本，提高該廠的經(jīng)濟(jì)效益與客戶服務(wù)水平。2 物流配送概述2.1 物流配送概念與配送（distribution）一詞相關(guān)的最早的活動是“送貨上門”。其產(chǎn)生自上世紀(jì)中葉的生產(chǎn)企業(yè)或中轉(zhuǎn)倉庫，他們一般根據(jù)客戶的需求，將貨物準(zhǔn)確的運送到客戶手中，形成了配送的雛形“一般送貨”。隨著客戶對產(chǎn)品多樣化和差異化的要求，為了滿足客戶的需求，原始的一般送貨開始轉(zhuǎn)向分揀、配貨、送貨一體化。因此產(chǎn)生了配送。按照國家質(zhì)量技術(shù)監(jiān)督局發(fā)布的中華人民共和國國家標(biāo)準(zhǔn)“物流術(shù)語”（GB/T 183542001），配送是指在經(jīng)

14、濟(jì)合理區(qū)域范圍內(nèi)根據(jù)用戶要求，對物品進(jìn)行揀選、加工、包裝、分割、組配等作業(yè)，并按時送達(dá)指定地點的物流活動。2.2 物流配送的功能伴隨著生產(chǎn)的不斷發(fā)展，配送成為新型的物流手段而變得日趨成熟。無論是對于完善物流系統(tǒng)，發(fā)展企業(yè)，還是改善整個經(jīng)濟(jì)社會效益，都具有重要的作用。(1)配送使物流系統(tǒng)更加完善，同時也優(yōu)化了物流系統(tǒng)。上世紀(jì)五十年代以來，高水平的干線運輸一直呼喚著支線運輸和小搬運配套，但隨著物流技術(shù)的不斷發(fā)展，小搬運和支線運輸在靈活性、服務(wù)性和適應(yīng)性上逐漸表現(xiàn)出欠缺，使得出現(xiàn)運力不合理、運輸成本過高等不良狀況。配送的出現(xiàn)使干線支線運輸及小搬運統(tǒng)一，輸送過程得以優(yōu)化和完善。(2)配送提高了終端物流

15、的效益。在配送過程中，通過大批量進(jìn)貨，集中發(fā)貨，以及將多個小批量集中一起大批量發(fā)貨來有效的節(jié)省運力，以實現(xiàn)經(jīng)濟(jì)運輸，降低成本，使終端的物流經(jīng)濟(jì)效益得到提高。(3)配送通過集中庫存使企業(yè)實現(xiàn)低庫存或零庫存。生產(chǎn)企業(yè)完全可以在采取準(zhǔn)時制配送方式后依靠配送中心的準(zhǔn)時配送，而不需使自己的庫存保留有經(jīng)常庫存。(4)配送簡化事物，也使客服更加便利。采用配送的方式，客戶需要的貨物只要與一處或一個進(jìn)貨單位聯(lián)系就可以訂購到，相比以前需要向多處地方訂貨而言，其大大地減輕了訂貨的負(fù)擔(dān)，也節(jié)省了相關(guān)事務(wù)的開支。(5)配送利于降低整個社會的物資總體庫存水平。發(fā)展配送，實行集中庫存，整個社會物資的庫存總量也會低于各企業(yè)所

16、分散的庫存總量。同時，配送有利于靈活高度，有利于發(fā)揮物資的作用。此外，集中庫存可以發(fā)揮規(guī)模經(jīng)濟(jì)優(yōu)勢，降低庫存成本 。2.3 配送路線優(yōu)化的意義 配送路線是否合理在配送決策系統(tǒng)中占據(jù)著重要的地位，其直接影響著物流成本的高低。因此選擇合的理配送路線，對企業(yè)和社會都具有很重要的意義。通過科學(xué)合理的手段制定配送路線，在配送活動中是很重要的一個環(huán)節(jié)。合理的選擇配送路線的意義主要體現(xiàn)在以下幾點：(1)優(yōu)化配送路線，可以減少配送時間和配送里程，提高配送效率，增加車輛利用率，降低配送成本。(2)可以加快物流速度，使貨物更準(zhǔn)時、快速地送到客戶的手中，從而提高客戶滿意度。(3)使配送作業(yè)安排合理化，提高企業(yè)作業(yè)效

17、率，有利于企業(yè)提高競爭力與效益。 對全社會來說，合理選擇運輸路線還有利于節(jié)省運輸車輛，降低車輛空載率，減少社會物流成本，對其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。與此同時，其對緩解交通緊張狀況，減少噪聲、尾氣排放等運輸污染也有不容忽視的作用。3 貴州中煙公司畢節(jié)卷煙廠的配送的現(xiàn)狀3.1 煙草物流配送的特點煙草物流是指卷煙和其下游零售商及最終消費者之間從供應(yīng)地向接收地的實體流動過程，包括了運輸、儲存、裝卸、搬運、分揀、配送、信息處理等基本活動。煙草行業(yè)商業(yè)流通物流系統(tǒng)涉及348家中國地市級煙草流通網(wǎng)點，483萬戶卷煙零售客戶（2008年數(shù)據(jù)）。由于我國卷煙行業(yè)的特點，卷煙生產(chǎn)、銷售、卷煙專賣品的進(jìn)出

18、口實行國家專賣體制下的統(tǒng)一集中管理。卷煙生產(chǎn)由各省級中煙工業(yè)公司負(fù)責(zé)，而卷煙銷售則由各省卷煙公司負(fù)責(zé)。各級卷煙公司又下設(shè)若干生產(chǎn)廠，并作為小區(qū)域的地方中心總庫，進(jìn)而又對其下的各個分庫進(jìn)行配送，由各分庫物流中轉(zhuǎn)中心承擔(dān)最終配送到客戶。從卷煙工業(yè)企業(yè)出廠后經(jīng)過運輸、倉儲、分揀、配送到零售戶手中的流轉(zhuǎn)過程，各地市級卷煙公司下屬的配送中心(分中心)和中轉(zhuǎn)站是最末端的運作主體。3.2 國內(nèi)卷煙物流概述 進(jìn)入二十一世紀(jì)以來，中國的煙草生產(chǎn)的增長速度一直保持在3%-6%之間波動，根據(jù)中國煙草年鑒的統(tǒng)計，2008年中國煙草總產(chǎn)量已達(dá)到22198.76億支，比上一年增長了3.67%。煙草總產(chǎn)量的穩(wěn)定增長表明中國

19、煙草行業(yè)物流量近年來也呈現(xiàn)增長的態(tài)勢（參見表1、圖1）。表1 20052008年度中國各類煙草總產(chǎn)量（單位：億支） 年份（年） 2005200620072008總產(chǎn)量（億支） 19639.0020218.6021413.8422198.76增長率（%） 4.823.005.913.67數(shù)據(jù)來源：中國煙草年鑒圖1：20052008年度中國煙草總產(chǎn)量變化情況（單位：億支）來源：中國煙草統(tǒng)計年鑒中國卷煙行業(yè)是國民經(jīng)濟(jì)的重要支柱產(chǎn)業(yè)。中國卷煙物流發(fā)展的初期，組織化程度不高，物流業(yè)務(wù)分散在各個部門，管理模式粗放。如今實行“一庫制”配送，使物流業(yè)務(wù)集中起來，并不斷進(jìn)行物流信息技術(shù)的推廣應(yīng)用，經(jīng)歷了從無到有

20、，從不被重視到上升為行業(yè)核心地位的發(fā)展過程。當(dāng)前我國卷煙行業(yè)的物流模式和管理水平比起國外先進(jìn)的管理來說還不夠發(fā)達(dá)。在物流活動中，企業(yè)缺乏一體化和合理化管理的意識和能力，對各個環(huán)節(jié)的分工與合作，規(guī)范服務(wù)、無縫銜接等方面有待加強。 就目前狀況而言，中國卷煙工業(yè)系統(tǒng)和商業(yè)系統(tǒng)物流獨立運作，有各自的物流網(wǎng)絡(luò)和節(jié)點。工業(yè)生產(chǎn)發(fā)貨點近100個，商業(yè)有300多家地市級卷煙公司，近500萬家卷煙零售客戶。此外原材料及輔料發(fā)貨點也有上百個，工商企業(yè)各自分設(shè)物流系統(tǒng)，并沒有形成協(xié)作關(guān)系。這些網(wǎng)絡(luò)上節(jié)點的物流基本都是獨立多點對多點的關(guān)系，形成了繁雜的物流網(wǎng)絡(luò)，使得資源無法充分利用。再者，我國卷煙物流目前又正處于建設(shè)

21、的發(fā)展階段，一方面，發(fā)達(dá)的物流在行業(yè)發(fā)展中的作用已經(jīng)得到企業(yè)的充分認(rèn)識，各地紛紛建設(shè)功能完善的物流中心，培養(yǎng)物流人才，一些配套的規(guī)定也都陸續(xù)開展；另一方面，物流的管理水平也亟待提高，軟件建設(shè)還有很多需要發(fā)展，其中物流成本的控制是一個重要的方面。進(jìn)入二十一世紀(jì)以后，中國卷煙行業(yè)著手以建設(shè)物流信息化重點工程為起跑點，推廣應(yīng)用了商業(yè)企業(yè)卷煙物流配送中心數(shù)字倉儲管理系統(tǒng)和工商卷煙物流信息跟蹤系統(tǒng)等工程，極大地推動了卷煙行業(yè)信息化的建設(shè)和發(fā)展。同時，各企業(yè)根據(jù)自身發(fā)展實際和業(yè)務(wù)需要，建立了立體倉庫、自動化分揀線、電子標(biāo)簽托盤等物流設(shè)施與設(shè)備。有效地提高了工作效率、低了物流成本，提升了服務(wù)質(zhì)量和管理水平。

22、3.3 貴州中煙工業(yè)畢節(jié)卷煙廠物流配送的現(xiàn)狀3.3.1畢節(jié)卷煙廠概述始建于1974年，1982年經(jīng)國家批準(zhǔn)進(jìn)行易地改建和擴(kuò)建?，F(xiàn)全廠占地面積約32萬平方米，建筑面積18萬平方米。企業(yè)設(shè)備裝備有3000kg/h虹霓制 絲線、570kg/h干冰膨脹煙絲生產(chǎn)線，PASSIM、PROTOS、GDX1、GDX2、B1、ZB45等高速卷接包設(shè)備及公共配套工程和理化檢測設(shè)備。畢節(jié)卷煙廠過去曾得到過較快發(fā)展，但是由于各種內(nèi)外因素及市場都發(fā)生了變化，到“九五”后期，企業(yè)效益大幅下滑，很快又跌入低谷。進(jìn)入二十一世紀(jì)以后，經(jīng)全廠干部職工大膽開拓創(chuàng)新，內(nèi)抓管理，外拓市場，適時調(diào)整戰(zhàn)略思路，進(jìn)行了畢節(jié)卷煙廠艱難的“第二

23、次創(chuàng)業(yè)”。自此之后，品牌集中度不斷提高，經(jīng)濟(jì)效益呈明顯增長的勢頭，各項生產(chǎn)經(jīng)營指標(biāo)不斷更新歷史最好水平，實現(xiàn)畢節(jié)卷煙新的歷史跨越，企業(yè)亦顯示出較強勁的發(fā)展后勁和生命力。2004年8月“馳”牌被國家煙草專賣局定為全國100個重點卷煙牌號之列。2005年下半年進(jìn)行整合并入貴州中煙工業(yè)公司，作為工業(yè)公司的一個生產(chǎn)廠，年生產(chǎn)能力達(dá)45萬箱。3.3.2畢節(jié)卷煙廠配送現(xiàn)狀畢節(jié)卷煙廠位于畢節(jié)市七星關(guān)區(qū)，旗下設(shè)有7個分庫該廠總部設(shè)有一個總配送中心在七星關(guān)區(qū)，由該總庫向旗下的七個分庫進(jìn)行配送，再由七個分庫的配送中心將卷煙送往各地的零售商。如圖2所示：圖2:畢節(jié)市及各縣地圖 來源：百度地圖隨著社會經(jīng)濟(jì)水平的提高，

24、以及各種交叉因素的影響，該市各地對香煙的需求量不斷增大。現(xiàn)今該廠實行每日定點定量配送。需求量大的縣市日需求量達(dá)到了300多件，而需求量小的縣市僅為50多件。該廠現(xiàn)擁有4輛5t的配送貨車，3輛2t的貨車，5t貨車可裝卷煙330件，2t貨車可裝卷煙120件，每件卷煙約15kg，所以當(dāng)貨車裝滿時仍然不會超重。現(xiàn)在該廠采用的是“點到點”的直接配送模式共需7輛貨車運行8車次。3.3.3 畢節(jié)卷煙廠物流配送存在的問題現(xiàn)在該廠采用的是“點到點”的直接配送模式。其配送模式如圖3所示共需7輛貨車8車次。在對該廠個配送路線進(jìn)行數(shù)據(jù)綜合分析之后發(fā)現(xiàn)，該廠的運輸過程所產(chǎn)生的成本費用占據(jù)了配送過程中的百分之七十以上。由

25、于該廠每日都會配送大量的貨物，也就必定會產(chǎn)生巨大的資源浪費。經(jīng)綜合分析發(fā)現(xiàn)該廠所采用的配送模式的主要缺陷在于： (1)配送線路選擇不夠合理，沒有得到優(yōu)化，導(dǎo)致配送成本過大；(2)采用這種配送方式使得剩余貨運量在進(jìn)行直接配送時出現(xiàn)貨車裝不滿，造成資源浪費，導(dǎo)致配送成本進(jìn)一步加大，嚴(yán)重影響該廠的效益40321657圖3：畢節(jié)卷煙廠現(xiàn)在配送路線圖 由以上數(shù)據(jù)可以分析得出畢節(jié)卷煙廠物流配送中運輸運輸路線的不合理，因此合理安排運輸路線可以極大的提高其車輛的使用率和節(jié)約成本。顯然，為了實現(xiàn)以上目標(biāo)，就要對配送過程進(jìn)行合理規(guī)劃，這一點可以通過改進(jìn)運輸方式、進(jìn)行線路規(guī)劃等來實現(xiàn)。4 畢節(jié)卷煙廠配送路線優(yōu)化分析

26、4.1 物流配送路線優(yōu)化模型及方法描述4.1.1 VRP模型(1)模型提出。配送是物流活動的重要環(huán)節(jié)。從煙草企業(yè)的角度上看，煙草配送直接關(guān)系到企業(yè)經(jīng)濟(jì)效益的好壞和核心競爭力的強弱。配送線路規(guī)劃是否合理，也將直接影響配送成本高低、工作效率快慢和服務(wù)質(zhì)量優(yōu)劣。 物流配送線路優(yōu)化問題，主要是以線路最優(yōu)化為目標(biāo)的車輛調(diào)度問題，即 VRP問題，該類問題的實質(zhì)是在確定的需求下，如何對一個確定的客戶集合安排車輛、行駛路線和時間，使得總的行使里程數(shù)最小，總費用最少。配送車輛調(diào)度問題（VRP），最早是由 Dantzig和 Ramser 于1959 年首次提出的，自此很快引起運籌學(xué)、應(yīng)用數(shù)學(xué)、物流科學(xué)、計算機應(yīng)用

27、等學(xué)科的專家與運輸計劃的設(shè)計者和管理者的極大重視，成為運籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點問題。線路優(yōu)化問題的常用算法，基本上分為精確算法和啟發(fā)式算法兩大類。由于 VRP 問題是 NP 困難問題，而尋找近似算法更適合于實際情況，因此啟發(fā)式算法就成了備受關(guān)注的解決方法。目前，絕大部分這方面的研究成果也都對啟發(fā)式算法的設(shè)計或改進(jìn)做了新的開拓。 針對本文研究的問題，如何對配送線路進(jìn)行科學(xué)地優(yōu)化和整合，對配送車輛進(jìn)行合理的調(diào)度、對線路之間的工作量進(jìn)行科學(xué)的均衡，對配送車輛裝載率進(jìn)一步合理的提高，也是煙草配送線路優(yōu)化希望達(dá)到的目標(biāo)。(2)多回路運輸VRP模型。多回路運輸問題是目前很普遍的一種調(diào)配問題，尤

28、其對于有多數(shù)服務(wù)對象的實體，例如一個擁有多客戶的企業(yè)。此類調(diào)配的核心問題是如何對車輛進(jìn)行調(diào)度。因此，VRP（Vehicle Routing Problem）模型也應(yīng)運而生，成了解決多回路問題的一個相當(dāng)成功的模型。該問題研究目標(biāo)是：對一系列顧客需求點設(shè)計適當(dāng)?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等），達(dá)到一定的優(yōu)化目標(biāo)（如里程最短，費用最小，時間盡量少等）。它涉及了多輛交通工具的服務(wù)對象的選擇和路徑確定兩方面問題。一個典型的VRP模型可以如下表述：基本條件 現(xiàn)有m輛相同的車輛停在一個共同的源點，它需給n個客戶提供貨物，顧客為。模型目

29、標(biāo) 確定所需的車輛數(shù)N，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使總費用最小。限制條件：N不大于m；每一個訂單都要完成；每輛車完成任務(wù)后都要回到源點；車輛的容量限制不能超過；特殊問題還需考慮時窗限制；運輸規(guī)章限制。4.1.2 節(jié)約算法基本原理及主要步驟(1)節(jié)約算法（Saving Algorithm）是用來解決運輸車輛數(shù)目不確定的VRP問題，它是目前用來解決VRP模型最有名的啟發(fā)式算法。(2)節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（0， ，i，0）和（0，j， ，0）合并成一個回路（0， ，i，j，0）。在上面的合并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如果變

30、化后總運輸距離下降，則稱節(jié)約了運輸距離。相應(yīng)的變化值，叫做節(jié)約距離，如式所示。 調(diào)整過程如圖4所示。jji 00i 調(diào)整前 調(diào)整后 圖4：節(jié)約算法的圖像描述已知條件:需求點集=1,2, n,各點需求量,各點間最短距離。第一步,形成一個初始解。確定各車輛配送點集令, =1,2,n (先采取單點配送)。第二步,進(jìn)行節(jié)約度的計算。計算所有點對的節(jié)約度，然后對計算結(jié)果進(jìn)行升序排列。第三步，對回路進(jìn)行合并。從節(jié)約值中的最大的值開始，直到節(jié)約里程的隊列空為止,重復(fù)下列步驟:按照節(jié)約里程隊列從大到小的順序,分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過2),將i, j

31、連接起來,即可令。如果不是這樣,則從節(jié)約里程隊列中去除當(dāng)前的節(jié)約里程，分析下一個客戶對。4.1.3 改進(jìn)后的最近插入法(1)TSP模型是單回路運輸問題中的最為典型的一個模型，(全稱:Traveling Salesman Problem1)，中文名稱做旅行商問題。它是一個典型的NP難題，在大規(guī)模的線路優(yōu)化問題中無法利用它求得最優(yōu)解。而最近插入法就是一種解決此問題的啟發(fā)式算法。 最近插入法是Rosenkrantz和Stearns等人在1977年提出的一種用于解決TSP(旅行商)問題的算法。最近插入法由四步完成：找到最小的節(jié)點，形成一個子回路（subtour），。在剩下的節(jié)點中，尋找一個離子回路中某

32、一節(jié)點最近的節(jié)點。在子回路中找到一條路徑（i，j）,使得+-最小，然后將節(jié)點插入到節(jié)點，之間，用兩條新的路徑(i，k)，（k，j）代替原來的路徑（i，j），并將節(jié)點加入到子回路中。重復(fù)步驟、，直到所有的節(jié)點都加入到子回路中。這樣，子回路就演變?yōu)榱艘粋€TSP的解。(2)由于最近插入法解決的是同一回路運輸問題，因此，本文在此方法基礎(chǔ)上對其進(jìn)行改進(jìn)和修正，以便能解決多回路運輸VRP問題。有改進(jìn)的方法如下：找到最小的節(jié)點，形成一個子回路（subtour），。在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。若此時回路的總貨運量未超過車的載重限制，則繼續(xù)步驟。否則，轉(zhuǎn)尋找新的一條回路。在子回路中找到

33、一條路徑（i，j）,使得+-最小，然后將節(jié)點插入到節(jié)點，之間，用兩條新的路徑(i，k)，（k，j）代替原來的路徑（i，j），并將節(jié)點加入到子回路中。若此時該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟。否則轉(zhuǎn)步驟，尋找新的一條回路。重復(fù)步驟和，直到每一個節(jié)點都被歸入某一個子回路中。4.2 配送路線優(yōu)化研究4.2.1 建立VRP模型利用多回路運輸問題解決經(jīng)濟(jì)生活中出現(xiàn)的問題，這在如今的世界中已成為一項重要的科學(xué)成果和生活成果。此類調(diào)配問題的核心問題仍是車輛調(diào)度，因而，據(jù)此對貴州中煙工業(yè)畢節(jié)卷煙廠的配送系統(tǒng)建立VRP模型。基本條件：畢節(jié)卷煙廠需給旗下的7個分庫送貨，代號依次為1,2,3,6,7,

34、畢節(jié)卷煙廠現(xiàn)擁有5T貨車4輛，2T貨車3輛，5T貨車每輛可裝載330件，2T車每輛可裝載120件，每件卷煙15千克，所以盡管裝滿也不會超載。2T貨車每百公里耗油8L，5T車每百公里耗油12L。柴油現(xiàn)價格為6.99.元每升，司機每天工資120元。模型目標(biāo)：確定所需要的車輛的數(shù)目N、車輛類型、司機數(shù)量以及各車行駛的路線，并將這些車輛指派到一個回路中，同時包括回路內(nèi)的路線安排和調(diào)度，使得運輸總費用最小。限制條件：(1)出于人性化和對行車過程中的安全的考慮，當(dāng)運輸里程超過300公里時，需配備兩名司機，為了防止緊急運輸事件的發(fā)生，車輛必須當(dāng)天回到公司，去除由于裝卸貨物造成的額外運輸距離等影響因素，各車最

35、大運輸距離為500公里。(2) 每輛車完成任務(wù)之后都要回到源點0處。(3)車輛的容量限制不能超過。2噸的貨車最多可裝120件，5噸的最多可裝330件。5噸貨車運輸單價比2噸的低，優(yōu)先使用5噸車，若不超過120件，則使用2噸貨車。4.2.2 原配送路線基本數(shù)據(jù)分析目前，畢節(jié)卷煙廠各配送線路里程，配送任務(wù)的基本情況如表2所示。表2：現(xiàn)有配送任務(wù)表分庫黔西縣大方縣金沙縣赫章縣納雍縣織金縣威寧縣日需求量（件/d）143187366659214654配送距離（km）1154313396102129166由上表可知，公司每天均是全車配送，司機9人次，所需工資1080元，運輸總里程為1834千米，消耗的柴油

36、180.32升，所需燃油費1260.44元，一共花費2340.44元。4.2.3 基于節(jié)約算法的配送優(yōu)化 已知市煙草公司為0點，分別向7個分公司配送卷煙，其擁有4輛5t的貨車和3輛2 t的貨車，5t貨車最大載重量為330件，2 t貨車最大載重量為120件，設(shè)各點間的距離為c ，每輛車的載重量為r ，各點需求量為R ( i= 1 ， ，7) ，每輛車的行駛里程為( i =1， ，7)，且最大行駛距離500km，七星關(guān)區(qū)為0點，客戶點 1 ， 2 ， ，7 。車輛調(diào)度采用以下方案：按需求量的多少選配車輛如：金沙縣分庫的需求量為366件，可先采用1輛5t貨車進(jìn)行一次直接配送，剩余36件使用節(jié)約算法的

37、原理進(jìn)行配送，其他各縣市的貨運量均按該方法進(jìn)行整理，整理后 如表3所示表3：整理后的配送任務(wù)表:分庫黔西縣大方縣金沙縣赫章縣納雍縣織金縣威寧縣日需求量（件/d）14218736659214654配送距離（km）1154313396102129166再使用節(jié)約算法進(jìn)行路線優(yōu)化。首先確定各縣市之間的最短距離，如表4所示：表4：各縣市里程表縣市畢節(jié)市黔西縣大方縣金沙縣赫章縣納雍縣織金縣威寧縣畢節(jié)市01154313396102129166黔西縣0567419012475260大方縣01001337394206金沙縣0233172193258赫章縣013422075納雍縣088168織金縣0258威寧縣

38、0數(shù)據(jù)來源：百度地圖根據(jù)最短距離表，計算出用戶間的節(jié)約里程，并由大到小排列，編制節(jié)約里程c 順序表，如表5和表6所示。表5：節(jié)約里程項目0畢節(jié)市1黔西縣2大方縣3金沙縣4赫章縣5納雍縣6織金縣7威寧縣1黔西縣1021742193169212大方縣766727833金沙縣-46369414赫章縣645875納雍縣1431006織金縣377威寧縣表6：節(jié)約里程表從大到小排列連接點節(jié)約里程連接點節(jié)約里程13174456416169356356143374112102673757100142115931721478724626784652376273257234-43669最后，按節(jié)約里程從大到小合并

39、路徑(1)對于，故合并1,3兩點，則(I不為空集)。(2)對于，故1,6兩點可合并，則,(I不為空集)。(3)對于，因,故不滿足條件(4)余下各點的需求量均大于5，因此回路0-3-1-6-0不能再與其它點合并。以下討論與剩下的點相關(guān)的。(5)對于，因為1以處在0-3-1-6-0回路中，故不滿足條件。(6)對于，(I不為空集)。(7)對于，(I不為空集)。由于優(yōu)于,故合并4,7兩點，則(I不為空集)。因此0-4-7-0形成一回路。(8)對于，(I不為空集)故合并2,5兩點，則(I不為空集)。因此0-2-5-0形成一回路。至此，合并結(jié)束最后得到的優(yōu)化結(jié)果如表7，優(yōu)化路線如圖5所示：表7：節(jié)約法優(yōu)化

40、結(jié)果路線運距運貨量車型司機數(shù)0-3-1-6-0411km3255噸貨車20-4-7-0273km1192噸貨車10-2-5-0218km2795噸貨車10-3-0258km3305噸貨車1 由圖表可知，經(jīng)過節(jié)約算法進(jìn)行優(yōu)化后，該廠每天需5噸貨車3輛和2噸貨車1輛進(jìn)行配送，司機5人次，所需工資600元，運輸總里程為1160千米，消耗的柴油128.28升，所需燃油費896.68元，一共花費1496.68元。03124756圖5：節(jié)約算法優(yōu)化后的配送路線4.2.4 改進(jìn)的最近插入法配送優(yōu)化令T=0,N=0，1，2,7，比較表4-2 中從0出發(fā)的所有路徑大小。因為，所以就有顧客點0，2構(gòu)成一個子回路，

41、此時。然后在剩余顧客點（1，3，4，5，6，7）中尋找到0和2中某一點的最小距離，因為，所以在子回路中插入點1。由于對稱性，無論將1插入到0和2之間往返路徑中，結(jié)果都是一樣的，這樣，構(gòu)成了一個新的子回路，。因為在剩余的點中找不到能夠滿足本回路的條件的點，因此本回路已完成。以下繼續(xù)找出一個最小回路進(jìn)行新回路求解。從0出發(fā)，再找到剩余點中的最小子回路。因為，此時，所以就有點0,4構(gòu)成一個子回路,此時。在剩余的點（3,5,6,7）中繼續(xù)找到0和4中某一點的最小距離，,此時形成新子回路,。再繼續(xù)尋找新的點，此時，。此時形成了新的回路。再次對剩余的顧客點按照上訴方法進(jìn)行優(yōu)化，可構(gòu)成另子回路。利用改進(jìn)的最

42、近插入法得到優(yōu)化結(jié)果如表8所示，優(yōu)化線路結(jié)果如圖6所示。表8：改進(jìn)后的最近插入法優(yōu)化結(jié)果路線運距運貨量車型司機數(shù)0-1-2-0214km3295噸貨車10-4-7-5-0377km2115噸貨車20-3-6-0455km1825噸貨車20-3-0266km3305噸貨車1由圖表可知，經(jīng)過改進(jìn)后的最近插入法進(jìn)行優(yōu)化后，該廠每天需5噸貨車4輛進(jìn)行配送，司機6人次，所需工資720元，運輸總里程為1312千米，消耗的柴油157.44升，所需燃油費1100.51元，一共花費1820.51元.03216475圖6：改進(jìn)的最近插入法求解線路結(jié)果4.3 兩種優(yōu)化路線選擇與評價由上文可知，在運用節(jié)約算法和改進(jìn)后

43、的最近插入法分別對配送線路進(jìn)行優(yōu)化后，可得到三種不同的優(yōu)化方案，因此還需要通過一系列指標(biāo)來評價方案的優(yōu)劣性。本文將根據(jù)所需車輛數(shù)，行駛總里程，總油耗，人力資源和總費用這些指標(biāo)，對三種優(yōu)化后的方案進(jìn)行評價分析，評價分析如表9所示。 從表9的對比中可知，從車輛需求數(shù)的角度來看，兩種優(yōu)化后的方案與優(yōu)化前方案相比較都節(jié)約了3/7的車輛需求，但采用節(jié)約算法優(yōu)化后的方案需求車輛較占優(yōu)勢。使畢節(jié)卷煙廠的車輛安排使用上具有更大彈性。因此，在用車角度上考慮，節(jié)約算法優(yōu)化后的方案比較節(jié)省成本。表9：優(yōu)化結(jié)果對比表狀態(tài)優(yōu)化前優(yōu)化后節(jié)約算法改進(jìn)后的最近插入法各車型車次(次)2t4105t434總運輸里程(km)183

44、411601312節(jié)約里程數(shù)（km）674522油耗（L）180.32128.28157.44節(jié)約油耗（L）27.1922.88司機（次）956節(jié)約人力（次）43總費用（元）2340.441496.681820.51節(jié)約費用（元）843.76519.93從總運輸里程角度考慮，優(yōu)化后的兩種方案的總運輸里程分別為1160千米和1312千米，與優(yōu)化前的1834千米相比較，均減少了車輛行駛的里程數(shù)。優(yōu)化后的方案能減少了公司車輛的損耗和資源的浪費，給該廠帶去更多的效益。因此，從運輸里程的角度考慮，優(yōu)化后的方案仍以節(jié)約算法最優(yōu)。從燃油消耗的角度考慮，優(yōu)化后的兩種方案的消耗分別為128.28升和157.44

45、升，與優(yōu)化前的180.32升相比較，兩種優(yōu)化方案也都降低了油耗量，但仍以節(jié)約算法優(yōu)化后的方案消耗更少的油。配送線路優(yōu)化后，不僅能減少畢節(jié)卷煙廠配送過程中燃油費用的支出，還能降低社會資源的浪費。因此，從燃油消耗的角度上考慮，節(jié)約算法也是最優(yōu)。從該廠人力資源消耗角度來考慮，優(yōu)化后的方案所需司機依次為5，6人次，減少人力的消耗為4，3人次。兩種優(yōu)化后的方案均能使公司在人員安排上將更具有彈性，還能降低公司費用的支出。因此，從該廠人力資源消耗的角度考慮，節(jié)約算法和改進(jìn)后的最近插入法都使人力資源得到了優(yōu)化。從支出的總費用角度來考慮，優(yōu)化后的方案的費用支出依次1496.68元和1820.51元，與原方案的為2340.44元相比較，節(jié)約算法最優(yōu)。結(jié)合車次需求數(shù)，總運輸里程，燃油消耗，人力資源消耗，支出的總費用五個角度一齊分析，節(jié)約算法均為最優(yōu)的優(yōu)化方案。但是，本文的配送距離略有超出配送最佳范圍，模型存在著一定的缺陷。在計算過程中也將一些因素理想化了，與實際情況不完全相符。例如，并未考慮具體的道路信息，運輸規(guī)章等。因此，畢節(jié)卷煙廠還應(yīng)該根據(jù)實際情況合理選擇配送方案。 結(jié) 論本文針對畢節(jié)卷煙廠7個縣市配送狀況進(jìn)