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