【文章內(nèi)容簡介】 總配送中心在七星關(guān)區(qū)，由該總庫向旗下的七個分庫進行配送，再由七個分庫的配送中心將卷煙送往各地的零售商。如圖 2所示： 圖 2:畢節(jié)市及各縣地圖 來源：百度地圖 隨著社會經(jīng)濟水平的提高，以及各種交叉因素的影響，該市各地對香煙的需求量不斷增大?，F(xiàn)今該廠實行每日定點定量配送。需求量大的縣市日需求量達到了 300 多件，而需求量小的縣市僅為 50 多件。該廠現(xiàn)擁有 4輛 5t 的配送貨車，3 輛 2t的貨車， 5t 貨車可裝卷煙 330 件， 2t 貨車可裝卷煙 120 件，每件卷煙約淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 6 頁 共 20 頁 15kg，所以當貨車裝滿時仍然不會超重?，F(xiàn)在該廠采用的是“點到點”的直接配送模式．共需 7 輛貨車運行 8車次。 畢節(jié)卷煙廠物流配送存在的 問題 現(xiàn)在該廠采用的是“點到點”的直接配送模式。其配送模式如圖 3 所示．共需 7 輛貨車 8車次。 在對該廠個配送路線進行數(shù)據(jù)綜合分析之后發(fā)現(xiàn)，該廠的運輸過程所產(chǎn)生的成本費用占據(jù)了配送過程中的百分之七十以上。由于該廠每日都會配送大量的貨物，也就必定會產(chǎn)生巨大的資源浪費。經(jīng)綜合分析發(fā)現(xiàn)該廠所采用的配送模式的主要缺陷在于： (1)配送線路選擇不夠合理，沒有得到優(yōu)化，導(dǎo)致配送成本過大； (2)采用這種配送方式使得剩余貨運量在進行直接配送時出現(xiàn)貨車裝不滿，造成資源浪費，導(dǎo)致配送成本進一步加大，嚴重影響該廠的效益． 圖 3：畢節(jié)卷煙廠現(xiàn)在配送路線圖 由以上數(shù)據(jù)可以分析得出畢節(jié)卷煙廠物流配送中運輸運輸路線的不合理，因此合理安排運輸路線可以極大的提高其車輛的使用率和節(jié)約成本。顯然，為了實現(xiàn)以上目標，就要對配送過程進行合理規(guī)劃，這一點可以通過改進運輸方式、進行線路規(guī)劃等來實現(xiàn)。 4 0 3 2 1 6 5 7 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 7 頁 共 20 頁 4 畢節(jié)卷煙廠配送路線優(yōu)化分析 物流配送路線優(yōu)化模型及方法描述 VRP 模型 (1)模型提出。配送是物流活動的重要環(huán)節(jié)。從煙草企業(yè)的角度上看，煙草配送直接關(guān)系到企業(yè)經(jīng)濟效 益的好壞和核心競爭力的強弱。配送線路規(guī)劃是否合理，也將直接影響配送成本高低、工作效率快慢和服務(wù)質(zhì)量優(yōu)劣。 物流配送線路優(yōu)化問題，主要是以線路最優(yōu)化為目標的車輛調(diào)度問題，即 VRP 問題，該類問題的實質(zhì)是在確定的需求下，如何對一個確定的客戶集合安排車輛、行駛路線和時間，使得總的行使里程數(shù)最小，總費用最少。配送車輛調(diào)度問題（ VRP），最早是由 Dantzig 和 Ramser 于 1959 年首次提出的，自此很快引起運籌學(xué)、應(yīng)用數(shù)學(xué)、物流科學(xué)、計算機應(yīng)用等學(xué)科的專家與運輸計劃的設(shè)計者和管理者的極大重視，成為運 籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點問題。線路優(yōu)化問題的常用算法，基本上分為精確算法和啟發(fā)式算法兩大類。由于 VRP 問題是 NP 困難問題，而尋找近似算法更適合于實際情況，因此啟發(fā)式算法就成了備受關(guān)注的解決方法。目前，絕大部分這方面的研究成果也都對啟發(fā)式算法的設(shè)計或改進做了新的開拓。 針對本文研究的問題，如何對配送線路進行科學(xué)地優(yōu)化和整合，對配送車輛進行合理的調(diào)度、對線路之間的工作量進行科學(xué)的均衡，對配送車輛裝載率進一步合理的提高，也是煙草配送線路優(yōu)化希望達到的目標。 (2)多回路運輸 —— VRP 模型 。多回路運輸問題是目前很普遍的一種調(diào)配問題，尤其對于有多數(shù)服務(wù)對象的實體，例如一個擁有多客戶的企業(yè)。此類調(diào)配的核心問題是如何對車輛進行調(diào)度。因此， VRP（ Vehicle Routing Problem）模型也應(yīng)運而生，成了解決多回路問題的一個相當成功的模型。 該問題研究目標是：對一系列顧客需求點設(shè)計適當?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等），達到一定的優(yōu)化目標（如里程最短，費用最小，時間盡量少等）。它涉及了多輛交通工具的服務(wù)對象的選擇和路徑 確定兩方面問題。 一個典型的 VRP 模型可以如下表述： ①基本條件 現(xiàn)有 m 輛相同的車輛停在一個共同的源點 0v ，它需給 n個客戶提供貨物，顧客為 1 2 n,v v v、 … ， 。 ②模型目標 確定所需的車輛數(shù) N，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使總費用最小。 ③限制條件： N 不大于 m；每一個訂單都要完成；每輛車完成任務(wù)后都要回淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 8 頁 共 20 頁 到源點 0v ；車輛的容量限制不能超過；特殊問題還需 考慮時窗限制；運輸規(guī)章限制。 節(jié)約算法基本原理及主要步驟 (1)節(jié)約算法（ Saving Algorithm）是用來解決運輸車輛數(shù)目不確定的 VRP問題，它是目前用來解決 VRP 模型最有名的啟發(fā)式算法。 (2)節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（ 0，? ， i， 0）和（ 0， j，? ， 0）合并成一個回路（ 0，? ， i， j，?， 0）。在上面的合并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如果變化后總運輸距離下降，則稱節(jié)約了運輸距離。相應(yīng)的變化值，叫做節(jié)約距離 ijC? ，如式①所示。 ij io oj jiC c c c? ? ? ? ① 調(diào)整過程如圖 4 所示。 調(diào)整前 調(diào)整后 圖 4：節(jié)約算法的圖像描述 已知條件 :需求點集 RN ={1,2,? , n},各點需求量 iR ,各點間最短距離 ijc 。 第一步 ,形成一個初始解。確定各車輛配送點集 12, , , mI I I??? 令 ??jIj? , j =1,2,? ,n (先采取單點配送 )。 第二步 ,進行節(jié)約度的計算。計算所有點對的節(jié)約度 ijC? ，然后對計算結(jié)果進行升序排列。 第三步，對回路進行合并。從節(jié)約值中的最大的值開始，直到節(jié)約里程0 j i 0 j i 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 9 頁 共 20 頁 的隊列空為止 ,重復(fù)下列步驟 :按照節(jié)約里程 隊列從大到小的順序 ,分析客戶 i 和 j 之間合并的可能性 (是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過 2),將 i, j 連接起來 ,即可令 。i i j jI I I I? ? ? ? ?。如果不是這樣 ,則從節(jié)約里程隊列中去除當前的節(jié)約里程，分析下一個客戶對。 改進后的最近插入法 (1)TSP 模型是單回路運輸問題中的最為典型的一個模型， (全稱 :Traveling Salesman Problem1)，中文名稱做旅行商問題。它是一個典型的 NP 難題，在大規(guī)模的線路優(yōu)化問題中無法利用它求得最優(yōu)解。而最近插入法就是一種解決此問題的啟發(fā)式算法。 最近插入法是 Rosenkrantz 和 Stearns 等人在 1977 年提出的一種用于解決TSP(旅行商 )問題的算法。最近插入法由四步完成： ①找到 0ic 最小的節(jié)點 iv ，形成一個子回路（ subtour）， ? ?00,kT v v v? 。 ②在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點 kv 。 ③在子回路中找到一條路徑（ i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點 iv 插入到節(jié)點 iv ， jv 之間，用兩條新的路徑 (i， k)，（ k， j）代替原來的路徑（ i， j），并將節(jié)點 kv 加入到子回路中。 ④重復(fù)步驟②、③，直到所有的節(jié)點都加入到子回路中。 這樣，子回路就演變?yōu)榱艘粋€ TSP 的解。 (2)由于最近插入法解決的是同一回路運輸問題，因此，本文在此方法基礎(chǔ)上對其進行改進和修正，以便能解決多回路運輸 VRP 問題。有改進的方法如下： ①找到 0ic 最小的節(jié)點 iv ，形成一個子回路（ subtour）， ? ?00,kT v v v? 。 ②在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點 kv 。若此時回路的總貨運量未超過車的載重限制，則繼續(xù)步驟③。否則，轉(zhuǎn)①尋找新的一條回路。 ③在子回路中找到一條路徑（ i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點 iv 插入到節(jié)點 iv ， jv 之間，用兩條新的路徑 (i， k)，（ k， j）代替原來的路徑（ i， j），并將節(jié)點 kv 加入到子回路中。若此時該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟④。否則轉(zhuǎn)步驟①，尋找新的一條回路。 淮海工學(xué)院二〇一三屆本科畢業(yè)論文 第 10 頁 共 20 頁 ④重復(fù)步驟①和③，直到每一個節(jié)點都被歸入某一個子回路中 。 配送路線優(yōu)化研究 建立 VRP 模型 利用多回路運輸問題解決經(jīng)濟生活中出現(xiàn)的問題，這在如今的世界中已成為一項重要的科學(xué)成果和生活成果。此類調(diào)配問題的核心問題仍是車輛調(diào)度，因而，據(jù)此對貴州中煙工業(yè)畢節(jié)卷煙廠的配送系統(tǒng)建立 VRP 模型。 基本條件：畢節(jié)卷煙廠需給旗下的 7 個分庫送貨，代號依次為 1,2,3,…… 6,7,畢節(jié)卷煙廠現(xiàn)擁有 5T 貨車 4 輛， 2T貨車 3 輛， 5T貨