閩港紙箱包裝有限公司配送路線優(yōu)化研究

1、1閩港紙箱包裝有限公司配送路線優(yōu)化研究閩港紙箱包裝有限公司配送路線優(yōu)化研究 摘要 物流配送是物流的核心環(huán)節(jié)之一，而合理的選址和配送車輛的路線優(yōu)化對于提高配送效率和質(zhì)量具有重要影響。正確合理地安排車輛的配送線路，可以有效地增加車輛的利用率，實現(xiàn)合理線路運輸，從而降低運輸成本，節(jié)約運輸時間，提高客戶服務水平，提高經(jīng)濟效益，達到科學化的物流管理。這也是企業(yè)提高自身競爭力的有效途徑之一。本文通過精確重心法對連云港市閩港紙箱有限公司的當前地址進行合理性的判斷，并在此基礎上通過對公司配送現(xiàn)狀分析，利用“C-W”節(jié)約算法和掃描算法以及兩種改進的最近插入法對該公司的配送路線進行優(yōu)化。四種方法得到的結果均優(yōu)于原

2、配送路線，都可達到降低運輸成本的目的，而利用節(jié)約算法得到的結果更優(yōu)。該選題對與閩港紙箱包裝有限公司相類似企業(yè)的物流配送路線規(guī)劃問題也具有一定的參考價值。 關鍵詞 車輛路徑問題 選址合理性判斷 節(jié)約算法 掃描算法 改進的最近插入法2S Study of Delivery Route Optimization about The LianyungangCity Carton Company Abstract Physical distribution is a core part of logistics, while reasonable location and route optimizat

3、ion have a great effect on improving the efficiency and quality of delivery. Proper and reasonable arrangement for the delivery vehicle lines, can effectively increase the utilization of vehicles and achieve reasonable line transport. As a result, it will reduce transport costs, save transportation

4、time, improve customer service levels, enhance economic efficiency and achieve scientific logistics management. This is also one of the effective way to improve competitiveness of enterprises. In this paper, the rationality of the current location of the Lianyungang City Carton company is judged by

5、centre-of-gravity method. On this basis, the companys delivery status is analyzed, and the companys distribution route is improved by use of CW saving algorithm, sweep algorithm and two nearest insertion. the results obtained from four methods are better than the original distribution routes and can

6、 achieve the purpose of reducing transport costs, while the result obtained from saving algorithm best. The topic has some reference value for those companies that have similar business problems in logistics and route planning. Key Words vehicle routing problem saving algorithm sweep algorithm impro

7、ved nearest insertion3目錄引言 .4第一章 物流配送概述 .51.1 物流配送的概念.51.2 物流配送的功能 .51.3 配送路線優(yōu)化的意義及原則 .6第二章 閩港紙箱包裝有限公司現(xiàn)狀 .72.1 公司簡介 .72.2 公司配送現(xiàn)狀 .7第三章 模型及方法描述 .93.1 精確重心法.93.1.1 精確重心法基本原理.93.1.2 精確重心法主要步驟 .103.2 多回路運輸VRP 模型.113.3 節(jié)約算法 .113.3.1 節(jié)約算法的基本原理.113.3.2 節(jié)約里程算法主要步驟.123.4 掃描算法 .133.4.1 掃描算法的基本原理 .133.4.2 掃描算法

8、的主要步驟 .133.5 改進后的最近插入法.133.5.1 最近插入法 .133.5.2 改進的最近插入法（一） .143.5.3 改進的最近插入法（二） .14第四章 基于精確重心法判斷閩港紙箱包裝有限公司選址合理性 .16第五章 閩港紙箱包裝有限公司配送路線優(yōu)化研究 .195.1 建立 VRP 模型 .195.2 優(yōu)化閩港紙箱有限公司的配送線路.195.2.1 基于節(jié)約算法的企業(yè)配送路線優(yōu)化 .205.2.2 基于掃描算法的企業(yè)配送路線優(yōu)化 .235.2.3 基于改進的最近插入法（一）的企業(yè)配送路線優(yōu)化 .265.2.4 基于改進的最近插入法（二）的企業(yè)配送路線優(yōu)化 .285.2.5 四

9、種優(yōu)化方案比較分析 .31結論.32致謝語 .33參考文獻 .34附錄.354引言引言隨著物流業(yè)向全球化、信息化及一體化發(fā)展,配送在整個物流系統(tǒng)中的作用變得越來越重要。配送是物資供應的一種重要形式， 是連接生產(chǎn)與消費之間的一種中介服務。配送一般定義為:將貨物從物流結點送到收貨人的過程。配送是在集貨、配貨的基礎上，完全按客戶要求，包括種類、品種搭配、數(shù)量、時間等方面的要求所進行的運送，是“配”和“送”的有機結合形式。對于配送問題的研究，一是“配”方面的研究，如配送中心選址問題，二是“送”方面的研究，如旅行商問題(TSP)、車輛路線優(yōu)化問題(VRP)。合理的選址是公司建立完善的物流配送體系的先期條

10、件，同時合理的配送路徑對于提高配送效率和質(zhì)量，降低成本具有重要意義。在本文中主要對“送”進行研究。物流配送車輛的路線優(yōu)化，是物流配送優(yōu)化中的一個關鍵環(huán)節(jié)。因此設計合理、有效的車輛運輸路線方案，盡量減少配送里程數(shù)和配送時間不僅可以減少資源浪費，提高企業(yè)的經(jīng)濟效益和競爭力，而且可以更好地為客戶服務，加快對客戶需求的響應速度,提高服務質(zhì)量,增強客戶對物流環(huán)節(jié)的滿意度,維護企業(yè)良好的形象。優(yōu)化運輸物流,降低運輸成本,是企業(yè)提高其自身競爭力的有效途徑之一。大多數(shù)的物流配送運輸調(diào)度問題可以歸結為配送車輛的分配、行車路線的組織問題(V 即問題)，即根據(jù)不同要求-目標函數(shù)(例如運距最短、配送時間最短、運輸費用

11、最少等)，將配送運輸過程歸結為表述問題的數(shù)學模型。然后求得合理可行的優(yōu)化方案，在生產(chǎn)中付諸實施。VRP 問題或者稱作車輛路徑問題是組合優(yōu)化領域中著名的 NP 難題。近二十年來，無論在國內(nèi)還是國外，VRP 問題都是一個非常活躍的研究領域。本文將以連云港市閩港紙箱有限公司的當前選址問題和配送線路的優(yōu)化問題作為研究對象，通過精確重心法對目前公司地址進行合理性判斷，并且對各縣市需求量及運距進行分析計算，建立 VRP 數(shù)學模型，運用節(jié)約算法和掃描算法以及兩種改進的最近插入法對建立的模型進行求解。最后對四種方法求得的結論進行比較分析，從而為該公司提供合理的配送方案，以期降低物流運輸成本，提高該公司物流運作

12、效率和整5體競爭力，亦期望能對類似企業(yè)的發(fā)展提供借鑒作用。第一章第一章 物流配送概述物流配送概述1.1 物流配送的概念物流配送的概念2001 年 4 月，中國國家標準物流術語將配送定義為：“在經(jīng)濟合理區(qū)域范圍內(nèi)，根據(jù)用戶要求，對物品進行揀選、加工、包裝、分割、組配等作業(yè)，并按時送達指定地點的物流活動。11”配送是物流系統(tǒng)的核心環(huán)節(jié)之一，配送在英語中的原意是“delivery” 。是交貨送貨的意思。在日本工業(yè)標準 JIS 中，將配送定義為“將貨物從物流結點送交收貨人” ，強調(diào)了送貨的含義。可以說，物流配送是連接生產(chǎn)與消費之間的一種中介服務，是物資供應的一種重要形式。配送是“配”和“送”有機結合的

13、形式，它利用有效的分揀、配貨等理貨工作，使送貨達到一定的規(guī)模，以利用規(guī)模優(yōu)勢取得較低的送貨成本。221.2 物流配送的功能物流配送的功能發(fā)展配送，對于物流系統(tǒng)的完善、流通企業(yè)和生產(chǎn)企業(yè)的發(fā)展，以及整個經(jīng)濟社會效益的提高，無不具有重要的作用。（1）配送可以降低整個社會物資的庫存水平。發(fā)展配送，實行集中庫存，整個社會物資的庫存總量必然低于各企業(yè)分散的庫存總量。同時，配送有利于靈活高度，有利于發(fā)揮物資的作用。此外，集中庫存可以發(fā)揮規(guī)模經(jīng)濟優(yōu)勢，降低庫存成本。（2）配送有利于提高物流效率，降低物流費用。采用配送方式，批量進貨，集中發(fā)貨，以及將多個小批量集中一起大批量發(fā)貨，都能有效的節(jié)省運力，實現(xiàn)經(jīng)濟運

14、輸，降低成本，提高物流效益。6（3）對于生產(chǎn)企業(yè)來講，配送可以實現(xiàn)低庫存。實行高水平的定時配送方式之后，生產(chǎn)企業(yè)可以依靠配送中心準時配送或即時配送而不需保持自己的庫存，這就可實現(xiàn) 生產(chǎn)企業(yè)的“零庫存” ，節(jié)約儲備資金，降低生產(chǎn)成本。（4）配送可以成為流通社會化、物資產(chǎn)業(yè)化的戰(zhàn)略選擇。實行社會集中庫存、集中配送，能從根本上打破條塊分割的分散流通體制，實現(xiàn)流通社會化、物流產(chǎn)業(yè)化。111.3 配送路線優(yōu)化的意義及原則配送路線優(yōu)化的意義及原則通常認為，配送是近距離，小批量，品種比較復雜，按用戶需要搭配品種與數(shù)量的服務體系。從配送中心把貨物送到所需的各個用戶，有很多種不同的路線選擇方案。合理的選擇配送路

15、線，對企業(yè)和社會都具有很重要的意義。 對企業(yè)來說，(1)優(yōu)化配送路線，可以提高配送效率，對配送車輛做到物盡其用，盡可能的降低配送成本。(2)可以準時、快速地把貨物送到客戶的手中，能極大地提高客戶滿意度。(3)有利于企業(yè)提高效益。 對社會來說，它可以節(jié)省運輸車輛，緩解交通緊張狀況，減少噪聲、尾氣排放等運輸污染，為保護生態(tài)平衡、創(chuàng)造美好家園作出貢獻33。 進行配送路線優(yōu)化時，必須有明確的目標，遵循基本的原則。配送路線方案目標的選擇可以從以下幾個方面來考慮: (1)配送效益最高或配送成本最低。效益是企業(yè)追求的主要目標，可以簡化為用利潤來表示，或以利潤最大化作為目標;成本對企業(yè)效益有直接的影響，選擇成

16、本最低化作為目標值與前者有著直接的聯(lián)系。當有關數(shù)據(jù)容易得到和容易計算時，就可以用利潤最大化或成本最低作為目標值。(2)配送里程最短。如果配送成本與配送里程相關性較強，而和其他因素相關性較弱時，配送里程最短的實質(zhì)就是配送成本最低。則可考慮用配送里程最短作為目標值，這樣就可以大大簡化線路選擇和車輛調(diào)度方法。當配送成本不能通過里程來反映時，如道路收費、道路交通條件嚴重的影響成本，單以最短路程作為目標就不適合44。(3)配送服務水準最優(yōu)。如準時配送要求成為第一位時，或需要犧牲成本來確保服務水準時，則應該在成本不失控的情況下，以服務水準為首選目標。這種成本的損失可能從其它方面彌補回來，如優(yōu)質(zhì)服務可以采取

17、較高的價格策略。7(4)配送勞動的消耗最小。即以物化勞動和活勞動消耗最小為目標，在許多情況下，如勞動力緊張、燃料緊張、車輛及設備較為緊張的情況下，限制了配送作業(yè)的選擇范圍，就可以考慮以配送所需的勞動力、車輛或其它有關資源作為目標值55。第二章第二章 閩港紙箱包裝有限公司現(xiàn)狀閩港紙箱包裝有限公司現(xiàn)狀2.1 公司簡介公司簡介連云港市閩港紙箱包裝有限公司初建于 1996 年，占地面積 20 多畝，座落于江蘇連云港市海州西門工業(yè)區(qū)，毗鄰主干道路，公司現(xiàn)有員工 50 余人，注冊資金 150 萬元，年產(chǎn)值 2000 萬元。公司以生產(chǎn)各種紙箱及各種規(guī)格紙板為主，是集設計、制作、印刷一體化的綜合型包裝生產(chǎn)企業(yè)

18、。公司具有國家商檢局頒發(fā)的進出口包裝許可證 。為適應企業(yè)發(fā)展的需要，在包裝業(yè)市場上贏得競爭，公司引進了具有國內(nèi)先進水平的包裝檢測設備，以滿足不同客戶的需求。 2.2 公司配送現(xiàn)狀公司配送現(xiàn)狀公司的客戶主要位于其所在地的周邊縣市，如圖 1 所示，共有 10 個縣市，如贛榆縣，新沂市，灌云縣等。其中，大客戶的月需求量一般約為 3 萬平方米，小客戶一般約為 5 千平方米，一般的客戶約為 1 萬平方米。公司與其客戶建立了長期合作關系（一般為一年以上） ，通過簽訂合同，在每月約定時間交貨。公司現(xiàn)擁有兩部 5 噸的貨車，一部 2 噸的貨車，其余由物流公司提供配送服務。公司采用的是“點到點”直接配送模式。公

19、司原有的配送模式如圖 2 所示，共需10 輛車，該模式的弊端在于：配送路線的選擇不合理,沒有得到優(yōu)化；另外，剩余貨運量進行直送時不能充分利用車輛配載容積，從而造成資源浪費，影響公司盈利。8（圖片來源：http:/ 圖 2-1 閩港紙箱包裝有限公司配送網(wǎng)絡圖3204657119810 圖 2-2 公司原有配送路線各地區(qū)的月需求量如表 1 所示。 表 2-1 各地區(qū)月貨運量 （平方米/月）客戶1 贛榆縣2 新沂市3 東?？h4 灌云縣5 灌南縣6 響水縣7 濱?？h8 郯城縣9 臨沭縣10 沭陽縣9貨運量30800145001635082502710018600520017000755012000注：

20、數(shù)據(jù)來源于閩港紙箱包裝有限公司內(nèi)部資料第三章第三章 模型及方法描述模型及方法描述3.1 精確重心法精確重心法為了判斷公司的選址是否合理，現(xiàn)將理想選址點的待選區(qū)域假設為一個平面，可能的選址位置的數(shù)量是無限的，即選址模型是連續(xù)的。而連續(xù)選址有兩種模型，分別是交叉中值模型和精確重心法。由于交叉中值模型適用于小范圍的城市內(nèi)的選址問題，精確重心法適用于平面上大范圍的選址，故選用精確重心法判斷該公司的選址合理性。3.1.1 精確重心法基本原理精確重心法在評價的過程中使用的是歐幾米德距離，即直線距離。它的目標是尋求加權的直線距離總和最小7。在使用了歐幾米德距離后，目標函數(shù)如式（1）所示。 1n222ii=1

21、min Z = wisisxxyy（1）這是一個雙變量系統(tǒng)，分別對和進行求偏微分，并且令其為零，這樣就可以得到sxsy兩個微分等式。應用這兩個等式分別對和進行求解，即可以求出一對隱含有最優(yōu)sxsy解的等式，如式（2） ， （3）所示。 sx11niiiisniiisw xdwd10（2） sy11niiiisniiisw ydwd（3） 這里， 。 isd1222isisxxyy（4） 該方程組由于不能求解，因此可通過迭代的方法求解，這需要提供一組初始值和。sxsy然后利用，再用它去求出，迭代公式如式（5） 、 （6）(1)s(j-1)is(j-1) y ds jx和求出 sj ysjx 和所

22、示。 1(1)1(1)niiiis jsjniiis jw xdxwd（5） 1(1)1(1)niiiis jsjniiis jw ydywd（6）若該迭代過程具有收斂性，那么經(jīng)過無限次的迭代后，可以得到一個最優(yōu)解。* yssx 和但是在實際中，可迭代的次數(shù)是有限的，所以在迭代過程中需確定一個中止準則：（1）根據(jù)經(jīng)驗和以前的實驗結果設置迭代次數(shù) N；（2）將每一次得到的迭代結果與前一次的相比，當結果變化小于某一閾值、時，迭代結束。 （3）求得最優(yōu)解，limsitxlimsity使 Z 最小。3.1.2 精確重心法主要步驟 輸入：n客戶數(shù)，各客戶點的坐標,各客戶點對應的權重；( ,)iix yi

23、w輸出：設施坐標 Z總運費6。(,)ssxy11具體步驟如下：（1）選取初始迭代點 A（） ，如，計算 A 點到各00,ssxy11nsoiixxn011nsiiyyn客戶點的直線距離：=。0s0 Zisd和s0Z01niisiwd（2）令，計算和。1(1)1(1)niiiis jsjniiis jw xdxwd1(1)1(1)niiiis jsjniiis jw ydywdisjdsjZ（3）若，運費已無法減小，輸出最優(yōu)解：，(1)s jsjZZ(1)ss jxx(1)ss jyy。否則，轉(zhuǎn)（2） 。(1)s jZZ3.2 多回路運輸多回路運輸VRP 模型模型多回路運輸問題是現(xiàn)實中很普遍的一

24、種調(diào)配問題，特別對于有大量服務對象的實體。解決此類調(diào)配問題時，核心問題是如何對車輛進行調(diào)度。因此，VRP（Vehicle Routing Problem）模型也應運而生，成了解決多回路問題的一個相當成功的模型。該問題研究目標是：對一系列顧客需求點設計適當?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下，達到一定的優(yōu)化目標。它涉及了多輛交通工具的服務對象的選擇和路徑（服務順序）確定兩方面問題7。一個典型的 VRP 模型可以如下表述：（1）基本條件 現(xiàn)有 m 輛相同的車輛停在一個共同的源點，它需給 n 個客戶提0v供貨物，顧客為。12n,vvv、 ，（2）模型目標 確定所需的車輛數(shù) N，并指派

25、這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使總費用最小。（3）限制條件：N 不大于 m；每一個訂單都要完成；每輛車完成任務后都要回到源點；車輛的容量限制不能超過；特殊問題還需考慮時窗限制；運輸規(guī)章限制。0v123.3 節(jié)約算法節(jié)約算法節(jié)約算法是用來解決運輸車輛數(shù)目不確定的 VRP 問題，它是目前用來解決 VRP模型最有名的啟發(fā)式算法。故首先選用該法對公司的配送路線進行優(yōu)化。3.3.1 節(jié)約算法的基本原理節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（0， ，i，0）和（0，j， ，0）合并成一個回路（0， ，i，j，0） 。在上面的合并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如

26、果變化后總運輸距離下降，則稱節(jié)約了運輸距離7。相應的變化值，叫做節(jié)約距離，如式（7）所示。ijC， （7）ijioojjiCccc調(diào)整過程如圖 3 所示。j i02調(diào)整前0ij調(diào)整后 圖 3-1 節(jié)約算法的圖像描述3.3.2 節(jié)約里程算法主要步驟已知條件:需求點集=1,2, n,各點需求量,各點間最短距離;車輛集合RNiRijc=1,2,m,各車輛最大載重量6。TNiW第一步,將按從大到小排序,使得;。TNiW1W2WnW第二步,對于所有的客戶對(i, j),采用式（7）計算節(jié)約里程的值,其中, ijC13i=1,2,n; j=1,2,n,將大于零的從大到小排列形成隊列。ijC第三步,求初始可

27、行解。確定各車輛配送點集令=j, j=1,2,n (先采12,mI IIjI取單點配送)。第四步,合并配送路徑。直到節(jié)約里程的隊列空為止,重復下列步驟:按照節(jié)約里程ijC隊列從大到小的順序,分析客戶 i 和 j 之間合并的可能性(是否滿足裝載限制條件、ijC不在同一路徑內(nèi)以及合并次數(shù)不超過 2),將 i, j 連接起來,即可令。;iijjIIII 如果不是這樣,則從節(jié)約里程隊列中去除當前的節(jié)約里程，分析下一個客戶對。3.4 掃描算法掃描算法掃描算法也是用于求解車輛數(shù)目不限制的 VRP 問題，與節(jié)約算法不同的是，它屬于亞啟發(fā)式算法，而節(jié)約算法屬于構造算法。故選用該法對公司的配送路線進行優(yōu)化。3.

28、4.1 掃描算法的基本原理掃描算法是一種“先分組后路線”的算法。所謂分組，即指派給每輛車一組點。一種簡單的分組方法是將以配送中心為原點的坐標平面劃分為多個扇形區(qū)域，并初步將每個扇形區(qū)域的點分派給一輛車，然后擴充路線。如果在進行了一次“分組-路線”的路線構造后，還存在未分配點，則再進行“分組-路線”程序。如此反復，直到所有的點均已分配為止8。3.4.2 掃描算法的主要步驟（1）以起始點 0 點作為極坐標系的原點，建立極坐標系。（2）分組 從最小角度的顧客開始建立一個組，按逆時針方向，將顧客逐個加入到組中，直到顧客的需求總量超出了負載的限制。然后繼續(xù)建立一個新的組，繼續(xù)按逆時針方向，將客戶加入組中

29、。14（3）重復（2）中的過程，直到所有客戶都被分類為止。（4）路徑優(yōu)化 對各個組內(nèi)的單回路進行路徑優(yōu)化9。3.5 改進后的最近插入法改進后的最近插入法3.5.1 最近插入法 最近插入法是 Rosenkrantz 和 Stearns 等人在 1977 年提出的一種用于解決 TSP(旅行商)問題的算法。最近插入法由四步完成：（1）找到最小的節(jié)點，形成一個子回路（subtour） ，。0iciv00,iTv v v（2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。iv(3)在子回路中找到一條?。╝，b）,使得+-最小，然后將節(jié)點插入到節(jié)點aicibcabciv，之間，用兩條新的弧(a，i

30、)， （b，i）代替原來的?。╝，b） ，并將節(jié)點加入avbviv到子回路中。（4）重復步驟（2） 、 （3） ，直到所有的節(jié)點都加入到子回路中。這樣，子回路就演變?yōu)榱艘粋€ TSP 的解。由于最近插入法解決的是單回路運輸問題，故筆者在此方法基礎上進行改進和修正，使其能解決多回路運輸 VRP 問題。有兩種改進的思路如下：3.5.2 改進的最近插入法（一）（1）找到最小的節(jié)點，形成一個子回路（subtour） ，。0iciv00,iTv v v（2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。若此時回路的iv總貨運量未超過車的載重限制，則繼續(xù)步驟（3） 。否則，轉(zhuǎn)（1）尋找新的一條回路。

31、（3）在子回路中找到一條弧（a，b）,使得+-最小，然后將節(jié)點插入到節(jié)aicibcabciv點，之間，用兩條新的弧(a，i)， （b，i）代替原來的?。╝，b） ，并將節(jié)點加avbviv入到子回路中。若此時該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟（4） 。否則轉(zhuǎn)步驟（1） ，尋找新的一條回路。15（4）重復步驟（2）和（3） ，直到每一個節(jié)點都被歸入某一個子回路中。3.5.3 改進的最近插入法（二）（1）找到最小的節(jié)點，形成一個子回路（subtour） ，。0iciv00,iTv v v（2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。若此時回路的iv總貨運量和總路程均未超過

32、限制，則轉(zhuǎn)步驟（3） 。否則，轉(zhuǎn)步驟（4）（3）在子回路中找到一條?。╝，b）,使得+-最小，然后將節(jié)點插入到節(jié)aicibcabciv點，之間，用兩條新的弧(a，i)， （b，i）代替原來的?。╝，b） ，并將節(jié)點加avbviv入到子回路中。（4）在余下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點（除去之前不滿iv足插入條件的節(jié)點） ，若此時回路的總貨運量和總路程均未超過限制，則轉(zhuǎn)步驟（3） 。 否則。一直重復步驟（4） ，直到所有的節(jié)點都被嘗試。這樣得到了子回路 1。（5）找到最小的節(jié)點（排除已在子回路 1 中的節(jié)點） ，形成一個新的子回路0iciv（subtour） ，。然后重復步驟（2

33、） ， （3） （4） 。00,iTv v v 如是一直循環(huán)重復步驟，直到每一個節(jié)點都被歸入某一個子回路中。16第四章第四章 基于精確重心法判斷閩港紙箱包裝有限公司選址合理性基于精確重心法判斷閩港紙箱包裝有限公司選址合理性首先建立坐標系：現(xiàn)以宿遷市為坐標原點，建立坐標系，如圖 4 所示。4.8, 5.80.5, 2.62.8, 3.75.5, 2.2 6, 0.87.2, 1.58.5, 0.10.5, 4.62.6, 6.62.9, 1.1012345670123456789Y 軸8 2 9 3 3 1 4 10 6 5 75.3, 4.20 圖 4-1 需求點坐標圖（圖中 0 點為連云港（

34、5.3，4.2） ，每單位 18km）然后，選取初始迭代點并進行第一次迭代：X 軸17 ，計算并以各縣市的貨運量為權重，計算過0011114.1,2.9nnsisiiixxyynn(1)is jd程如表 2 所示。 表 4-1 精確重心法計算一需求點（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6. 6.6，2. 9，1. 1權重iw30800145001635082502710018600520017000755012000距離0isd2.9833.6121.5261

35、.5652.8323.4015.2153.9813.992 2.1630iiswd10325.184014.4010714.295271.579569.215468.98997.124270.281891.285547.85代入相應數(shù)據(jù)求得，根據(jù)公式（5） ， （6）代入數(shù)據(jù)得10001472930.15SiisiZwd。114.1,3.0ssxy接著，計算1SZ：計算過程如表 3 所示。表 4-2 精確重心法計算二需求點（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6

36、. 6.6，2. 9，1. 1權重iw30800145001635082502710018600520017000755012000距離0isd2.8863.6221.4761.6122.9073.4445.273.943.92.24718代入相應數(shù)據(jù)求得， 。所以進行第二次迭代。101101383592.67SiissiZwdZ然后，進行第二次迭代表 4-3 精確重心法計算三需求點（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6. 6.6，2. 9，1. 1權重iw3

37、0800145001635082502710018600520017000755012000距離0isd2.8863.6221.4761.6122.9073.4445.273.943.92.2470iiswd10672.214003.3111077.245117.879322.335400.70986.724314.721935.905340.45根據(jù)公式（5） ， （6）代入數(shù)據(jù)得， 。224.2,3.1ssxy接著，計算2SZ：計算過程如表 4 所示。 表 4-4 精確重心法計算四需求點（i）12345678910位置,iix y4.8 5.8，0.5 2.6，2.8 3.7，5.5 2.

38、2，6 0.8，7.2 1.5，8.5 0.1，4.60. 5，2.6. 6.6，2. 9，1. 1權重iw30800145001635082502710018600520017000755012000距離0isd2.7663.7341.5231.5812.9213.45.2433.9923.8482.38519代入相應數(shù)據(jù)求得， 。所以迭代結束。102211472479.2SiissiZwdZ最后，輸出結果：=5.0，=2.4 ，即理想位置點坐標為（4.1，3.0） ，。1ssxx1ssyy383592.67Z 而公司的實際位置坐標為（5.3，4.2） ，這表明當前公司選址不是合理的，這將影

39、響到公司的配送效率。但是，考慮到重遷需要投入大量的人力物力。而公司目前的狀況還不具備相應的能力。這意味著公司配送路線的優(yōu)化變得尤為迫切。第五章第五章 閩港紙箱包裝有限公司配送路線優(yōu)化研究閩港紙箱包裝有限公司配送路線優(yōu)化研究5.1 建立建立 VRP 模型模型多回路運輸問題時現(xiàn)實生活中十分普遍的一種調(diào)配問題。解決此類調(diào)配問題時，核心問題是如何對車輛進行調(diào)度1。因此 VRP 模型也應運而生，成了解決多回路問題的一個相當成功的模型。據(jù)此對閩港紙箱包裝公司的配送系統(tǒng)建立 VRP 模型?；緱l件：閩港紙箱有限公司需給 10 個客戶送貨，客戶依次為 1，2，,10，現(xiàn)有 1 輛 2 噸（長 4.5m,寬 2

40、m,高 3.8m）的貨車，2 輛 5 噸(長 7.2m,寬 2.2m,高 4m)的貨車,其余由物流公司提供貨車。故車輛數(shù)沒有限制。模型目標：確定所需要的車輛的數(shù)目 N、車輛類型以及各車行走的路徑，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使得運輸總費用最小。限制條件：（1）基于人性化的考慮，司機每天工作不超過 6 小時（配送車輛的車速一般控制在50 公里/小時。 ）由于在本模型中考慮時間窗的限制會加大解題的難度，因此對配送時間的限制轉(zhuǎn)換為在規(guī)定時間內(nèi)對行駛里程的限制，即各車最大運輸距離為 300 公里。（2） 每輛車完成任務之后都要回到源點 0 處。（3） 車輛的容量限制不能

41、超過。由于用一輛 5 噸貨車的運量約為 2 噸貨車的 2 倍，20并且在運輸路徑、物流成本方面也會有很大的節(jié)約，因此先選用 5 噸的貨車限制容量。5 噸的貨車最多可裝 6500 平方米的紙箱，2 噸的最多可裝 3500 平方米。5.2 優(yōu)化閩港紙箱有限公司的配送線路優(yōu)化閩港紙箱有限公司的配送線路已知閩港公司為 0 點，分別向 10 個客戶配送紙箱，其擁有兩輛 5 噸的車和一輛 2噸的車， 5 噸卡車最大容量為 6500 平方米紙箱，2 噸卡車最大載量為 3500 箱平方米紙箱，設各點間的距離為 C，C= 1,10 ，節(jié)約距離為。每輛車的載ijc, i jijc重量為 ，各點需求量為（ =1，1

42、0） ，每輛車的行駛里程為（ =1，10） ，iriRiiLi且公里，連云港為 0 點，客戶點 1，2，10300iL 各縣市的紙箱貨運量和配送距離如表 4 所示。表 5-1 運輸任務表客戶1 贛榆縣2 新沂市3 東?？h4 灌云縣5 灌南縣6 響水縣7 濱?？h8 郯城縣9 臨沭縣10 沭陽縣貨運量（/2m月）30800145001635082502710018600520017000755012000配送距離（km）29.485.947.23155.751.782.881.565.268.9車輛調(diào)度采用以下方案：按需求量的多少選配車輛。如，贛榆縣需求量為 30800平方米，先選用最大車型進行直

43、送（26000 平方米采用 4 輛 5 噸貨車運送） ，剩余貨運量（4800 平方米）利用節(jié)約原理進行配送，其他縣市的貨運量均按此方法進行整理，整理后如表 5 所示。 表 5-2 整理后的運輸任務表客戶1 贛榆縣2 新沂市3 東?？h4 灌云縣5 灌南縣6 響水縣7 濱海縣8 郯城縣9 臨沭縣10 沭陽縣剩余貨運量（/月）2m480015003350175011005600170040001050550021配送距離（km）29.485.947.23155.751.782.881.565.2 基于節(jié)約算法的企業(yè)配送路線優(yōu)化 在表 3 中，對有剩余貨運量的 10 個縣市采用節(jié)約法

44、進行配送路線的優(yōu)化。首先，確定各城市間的最短距離。因為距離對稱，所以=，縣市間最短距離表ijcjic6 所示。表 5-3 各縣市間最短距離表 （單位：千米）縣市0 連云港1 贛榆縣2 新沂市3 東?？h4 灌云縣5 灌南縣6 響水縣7 濱?？h8 郯城縣9 臨沭縣10 沭陽縣0 連云港029.485.947.23155.751.782.881.565.268.91 贛榆087486083.978.5108.977.65087.62 新沂04181.596.2113.1140.22967.443.33 東海046.468.381112.541.146.843.64 灌云024.130.861.289

45、90.350.45 灌南023.945.2108.111456.36 響水029.6122.211677.67 濱海0150.914798.88 郯城043.166.29 臨沭09010 沭陽0 其次，求節(jié)約里程。根據(jù)最短距離表，根據(jù)式（7）計算出用戶間的節(jié)約里程,并由大到小排列，編制節(jié)約里程順序表，如表 7 所示。ijc表 5-4 節(jié)約里程順序表 （單位：千米）連接點節(jié)約里程連接點節(jié)約里程連接點節(jié)約里程連接點節(jié)約里程連接點節(jié)約里程222-8138.42-983.72-545.41-328.61-1010.72-10111.55-683.51-944.62-728.55-96.94-5110.

46、83-1072.59-1044.11-228.34-95.96-7104.95-1068.36-10432-624.51-73.38-9103.63-965.62-435.44-823.51-62.65-793.37-1052.93-534.63-617.91-51.22-392.14-752.61-833.33-717.57-913-887.64-651.93-431.87-813.46-90.98-1084.24-1049.55-829.16-8111-40.4再次，求初始解，令=i（ =1，10），最短路徑iIi=2（ =1，10），且公里，載重量，且，對 10 個iL0ici300iL

47、 iirR26500irm客戶點進行標記，且 2。12100BBBBi然后，按節(jié)約里程從大到小合并路徑對于28138.4:ckm28282,8,1500400055006500,II rr 28282885.9*281.5*2 138.4196.4300,02LLckmkm BB 。128128282,82,8 ,5500,1,IIIrBBII 故合并兩點，令。 對于不滿足合并條2,10111.5:ckm1101102,10,55005500110006500,IIrr件。 對于不滿足合并條件。67104.9:ckm67676,7,5600 170073006500IIrr， 對于不滿足合并條

48、件。891919103.6:8,9,5500 105065506500,ckmII rr 對于5793.3:ckm57575,7,1100 170028006500,IIrr 575755.7*282.8*293.3183.7300,LLckmkm5702,BB故合并5，7兩點。257257575,7 ,2800,1,IIIrBBII 令。 對于不滿足合并條件。2392.1:ckm13132,3,5500335088506500,II rr 對于3887.6:ckm31133,8,5500335088506500,IIrr不滿足合并條件。23 對于8,1011011084.2:8,10,110

49、006500,ckmIIrr不滿足合并條件。 對于不滿足合并條件。2983.7:ckm1192,9,I II195500 105065506500,rr 對于不滿足合并條件。562683.5:5,6,ckmII262800560084006500,rr 對于不滿足合并條件。3,1072.5,ckm3103103,10,3350550088506500,IIrr 對于不滿足合并條件。5,1068.3:ckm2102105,10,2800550083006500,IIrr 對于3965.6:ckm39393,9,3350 105044006500,II rr3902,BB 393947.2*265

50、.2*265.6159.2300,LLckmkm故合并3,9兩點。339339395,7 ,4400,1,IIIrBBII 令。 對于4562.6:ckm42424,5,1750280045506500,IIrr450,1,BB 2445183.731*262.6183.1300,LLckmkm故合并4，5兩點。22425754,5,7 ,4550,2,1,IIIrBBI 令。 分析余下的各組，均不能滿足合并條件。詳見附錄一。最后，得到優(yōu)化結果如表 8 所示，優(yōu)化線路結果如圖 5 所示。 表 5-5 節(jié)約法優(yōu)化結果路線運程（km）剩余配貨量（）2m需車型及數(shù)量010 58.848005t 車一

51、輛0930159.244005t 車一輛0820196.455005t 車一輛04570183.145505t 車一輛0100137.855005t 車一輛060132.256005t 車一輛總運輸里程為所有路徑之和，求得為 838.7km。243204657119810 圖 5-1 節(jié)約算法求解線路結果5.2.2 基于掃描算法的企業(yè)配送路線優(yōu)化對有剩余貨運量的 10 個縣市采用掃描算法進行配送線路的優(yōu)化。首先建立極坐標系：以閩港紙箱包裝有限公司所在地連云港市作為原點建立極坐標系，各點的剩余需求量及極坐標的角坐標值如表 9 所示。坐標系如圖 6 所示。 表 5-6 需求表和極坐標的角坐標值客戶

52、1 贛榆縣2 新沂市3 東?？h4 灌云縣5 灌南縣6 響水縣7 濱?？h8 郯城縣9 臨沭縣10 沭陽縣剩余貨運量（/月）2m4800150033501750110056001700400010505500角坐標/( )106197190276282306310178145232 25 1320465710 89 圖 5-2 掃描算法的掃描過程然后分組：從角度為零向逆時針方向進行掃描，如圖所示。第一個被分組的是客戶 1，=4800；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶1Load2m9，=4800+1050=5850；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶1Load2m8，=5850+4000=98506500，由

53、于超過了限制，按分組規(guī)則，需要一個新1Load2m2m的組，這樣在第一組里只有客戶 1 和 9，=5850。在第二組中有客戶1Load2m8，=4000；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶2Load2m3，=4000+3350=73506500，超過限制，所以需要一個新的組，這樣在第2Load2m2m二組中只有客戶 8，=4000。在第三組中有客戶 3，load=3350，繼續(xù)轉(zhuǎn)2Load2m32m動；下個被分組的是客戶 2，=3350+150048506500，超過限制，故需要一個新3Load2m2m的組，這樣在第三組中只有客戶 2 和 3，=4850。 。繼續(xù)上面步驟，直到所有3Load2m的客

54、戶都被分配完畢。這樣可以得到如圖 7 所示的分組結果。26 132046579 8 10 圖 5-3 掃描算法求解結果最后對各子回路內(nèi)的線路優(yōu)化：對上面的 7 個組，都已經(jīng)是一個單回路運輸問題，對每個組進行線路優(yōu)化。供應點 0 是任何一個組的 TSP 問題的起點和終點。從圖 7 中可以看到，每個組最多只有 2 個客戶，由對稱性可知各小組的線路都是唯一的，故掃描優(yōu)化結果如表 10 所示?？傔\輸里程為所有路徑之和，求得 999.3km,共需 7 輛車，其中 5 噸 5 輛、2 噸 2 輛。優(yōu)化線路結果如圖 8 所示。 表 5-7 掃描算法優(yōu)化結果路線運程（km）剩余配貨量（）2m需車型及數(shù)量（輛）

55、0190 144.658505t 車一輛08016340005t 車一輛0320174.148505t 車一輛0100137.855005t 車一輛0450110.828502t 車一輛060103.456005t 車一輛070165.617002t 車一輛273204657119810 圖 5-4 掃描算法求解線路結果5.2.3 基于改進的最近插入法（一）的企業(yè)配送路線優(yōu)化（1） ，001min/,110294kmiciNic 1010,Tv v v214800rm158.8lkm（2），。01044min,/,110131,1750iicciNiicr 且1465506500rr 不滿足插

56、入條件。 （3），004min/,110,131kmiciNiic 241750rm 2040,Tv v v （4），04455min,/,1101,424.1,1100iicciNiicr 且 ，2451750 110028506500rrr20450,Tv v v v2110.8lkm （5），04556min,/,1101,4,523.9iiiccciNiic 且265600rm ，不滿足插入條件。625600285084506500rr （6），003min/,110,1,4,547.2kmiciNiic 233350rm ，3030,Tv v v32*47.294.4lkm23335

57、0rm28 （7）0338min,/,1101,3,4,541.1iicciNiic 且 ，不滿足插入條件。383350400073506500rr（8），006min/,110,1,3,4,551.7kmiciNiic 265600rm ，4060,Tv v v42*51.7103.4lkm245600rm（9）0669min,/,1101,3,4,5,629.6iicciNiickm 且 ，不滿足插入條件。495600 170073006500rr（10），009min/,110,1,3,4,5,665.2kmiciNiic 5090,Tv v v（11）0992min,/,1101,3,

58、4,5,6,967.4iicciNiickm 且 ，291500 105025506500rr50290,Tv v v v5218.5lkm 252550rm（12），09228min,/,7,8,1029iiiccciN ickm ，不滿足插入條件。582550400065506500rr（13），00,10min/,7,8,1068.9iciN ickm60100,Tv vv（14），0108,10min,/,7,866.2iicciN ickm ,不滿足插入條件。685500400095006500rr（15）00,8min/,7,881.5iciN ickm ，7080,Tv v v2

59、74000rm（16），080,7min,/,782.8iicciN ickm774000 170057006500rr，不滿足插入條件。70780,Tv v v v782.8 150.981.5315.2300lkmkm708077,4000,2*81.5163Tv v vrlkm 807088,1700,2*82.8165.6Tv v vrlkm利用改進的最近插入法（一）得到優(yōu)化結果如表 8 所示，優(yōu)化線路結果如圖 5 所示。29表 5-8 改進后的最近插入法（一）結果路線運程（km）剩余配貨量（）2m需車型及數(shù)量010 58.848005t 車一輛0450110.828502t 車一輛0

60、3094.433502t 車一輛060103.456005t 車一輛0290218.525502t 車一輛0100137.855005t 車一輛08016340005t 車一輛070165.617002t 車一輛總運輸里程為所有路徑之和，求得為 1052.3。km3204657119810圖 5-5 改進后的最近插入法（一）求解線路結果5.2.4 基于改進的最近插入法（二）的企業(yè)配送路線優(yōu)化（1） ，001min/,110294kmiciNic 1010,Tv v v214800rm158.8lkm（2），01044min,/,110131,1750iicciNiicr 且1465506500