畢業(yè)論文---配送線路優(yōu)化方案的研究與設計

1、<p>　　XX有限公司配送線路優(yōu)化方案的研究與設計</p><p>　　[摘要] 高效率合理的配送是物流系統(tǒng)順利運行的保證，配送線路安排的合理與否對配送速度、成本、效益影響很大。正確合理地安排車輛的配送線路，實現(xiàn)合理的線路運輸，可以有效地節(jié)約運輸時間，增加車輛利用率，從而降低運輸成本，提高企業(yè)經濟效益與客戶服務水平，使企業(yè)達到科學化的物流管理, 這也是企業(yè)提高自身競爭力的有效途徑之一。物流配送路徑優(yōu)化

2、問題具有很高的計算復雜性，屬于NP完全難問題，高效的精確算法存在的可能性不大，但可根據(jù)啟發(fā)算法求得近似最優(yōu)解。本文首先對物流配送進行概述，然后以婺源XX有限公司的配送方案為例，對XX有限公司的配送現(xiàn)狀進行分析，并運用節(jié)約算法、掃描算法以及改進后的最近插入法對XX有限公司的配送線路進行優(yōu)化，提出最優(yōu)配送方案。</p><p>　　[關鍵詞] 配送 車輛路徑問題 節(jié)約算法 掃描算法 改進的最近插入法</

3、p><p>　　Research and Designation of optimization of Baiyuan Wood Co., Ltd. distribution line</p><p>　　[Abstract] Reasonable and efficient distribution is the insurance of a smooth running logistics

4、 system; distribution line arrangement is reasonable or not has a great influence on the speed of delivery, costs and benefits. To arrange a reasonable and correct delivery line for vehicle and achieve a reasonable trans

5、port line can effectively increase the utilization of vehicles, save transportation time, thus reducing transportation costs, improving economic efficiency, enhancing customer service l</p><p>　　[Key words]

6、Distribution Vehicle routing problem Saving algorithm Sweep algorithm </p><p>　　Improved nearest insertion</p><p><b>　　目錄</b></p><p><b>　　引言4</b>&

7、lt;/p><p>　　第1章 物流配送概述3</p><p>　　1.1物流配送的概念3</p><p>　　1.2 物流配送的功能4</p><p>　　1.3 配送路線優(yōu)化的意義4</p><p>　　第2章 XX有限公司配送運作現(xiàn)狀5</p><p>　　2.1 公司簡介5<

8、;/p><p>　　2.2 公司配送現(xiàn)狀5</p><p>　　第3章 物流配送模型及方法描述8</p><p>　　3.1 多回路運輸—VRP模型8</p><p>　　3.2 節(jié)約算法8</p><p>　　3.2.1節(jié)約算法的基本原理8</p><p>　　3.2.2節(jié)約里程算法主要

9、步驟9</p><p>　　3.3 掃描算法10</p><p>　　3.3.1 掃描算法的基本原理10</p><p>　　3.3.2 掃描算法的主要步驟10</p><p>　　3.4改進后的最近插入法10</p><p>　　3.4.1 最近插入法10</p><p>　　3.

10、4.2 改進的最近插入法11</p><p>　　第4章 XX有限公司配送路線優(yōu)化研究12</p><p>　　4.1 建立VRP模型12</p><p>　　4.2XX公司的配送線路的分析與優(yōu)化12</p><p>　　4.2.1 原配送線路基本數(shù)據(jù)分析13</p><p>　　4.2.2 基于節(jié)約算法的企

11、業(yè)配送路線優(yōu)化13</p><p>　　4.2.3 基于掃描算法的企業(yè)配送路線優(yōu)化17</p><p>　　4.2.4 基于改進的最近插入法的企業(yè)配送路線優(yōu)化21</p><p>　　4.3 三種優(yōu)化方案比較分析22</p><p><b>　　結論25</b></p><p><

12、b>　　致謝語26</b></p><p><b>　　參考文獻27</b></p><p><b>　　引言</b></p><p>　　隨著社會主義市場經濟的不斷發(fā)展，作為“第三利潤源泉”的物流對經濟活動的影響日益明顯，引起了人們越來越多的重視，成為當前“最重要的競爭領域”。配送是現(xiàn)代物流的一個重

13、要環(huán)節(jié)，隨著物流的全球化、信息化及一體化,配送在整個物流系統(tǒng)中的作用變得越來越重要。配送是連接生產與消費之間的一種中介服務。它是指按客戶(包括零售商店、用戶等)的訂貨要求(包括貨物種類、數(shù)量和時間等方面的要求)，在物流中心(包括配送中心、倉庫、車站、港口等)進行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。</p><p>　　配送不是單純的運輸或送貨，而是運輸與其他活動（集貨，分貨，配貨）的組合，是“

14、配”與“送”的有機結合。因此對于配送問題的研究可分為對 “配”和“送”兩方面的研究?！芭洹敝饕獮榕渌椭行倪x址問題，“送”包括旅行商問題(TSP)、車輛路線優(yōu)化問題(VRP)。由于選址的外部因素（經濟，基礎設施，環(huán)境等）及內部因素（企業(yè)戰(zhàn)略，勞動力成本和素質等）的影響，單純考慮距離問題的選址是不合理的，因此在本文中不對“配”進行研究，主要對“送”進行研究。</p><p>　　配送路線的優(yōu)化，是配送優(yōu)化中的一個關鍵

15、環(huán)節(jié)。在配送過程中，配送線路合理與否對配送速度、成本、效益影響很大。設計合理、高效的配送路線方案，不僅可以減少配送時間，降低作業(yè)成本，提高企業(yè)的效益，而且可以更好地為客戶服務，提高客戶的滿意度，維護企業(yè)良好的形象。</p><p>　　配送線路優(yōu)化是指對一系列的發(fā)貨點和收貨點，組織適當?shù)男熊嚶肪€使車輛有序的通過它們，在滿足一定的約束條件下（貨物需求量與發(fā)送量，車輛容量限制，行駛里程限制），力爭實現(xiàn)一定的目標（行駛

16、里程最短，使用車輛盡可能少）。但配送作業(yè)情況復雜多變，不僅存在配送點多、貨物種類多、道路網(wǎng)復雜、路況多變等情況，而且運輸服務地區(qū)內需求網(wǎng)點分布也不均勻，使得線路優(yōu)化問題是一個無確定解多項式難題，需要啟發(fā)算法去求得近似最優(yōu)解。</p><p>　　本文將以XX有限公司當前的配送線路的優(yōu)化問題作為研究對象，對各縣市需求量及運距進行分析計算，建立VRP數(shù)學模型，運用節(jié)約算法和掃描算法以及改進的最近插入法對建立的模型進行

17、求解，對XX的配送路線進行優(yōu)化。最后對三種方法求得的結果進行比較分析，從而為該公司提供較合理的配送方案，以期減少配送里程，降低物流運輸成本，提高該公司物流運作效率，客戶服務質量和整體競爭力。</p><p>　　第1章 物流配送概述</p><p>　　1.1物流配送的概念</p><p>　　配送（distribution）起源于“送貨上門”。20世紀60年代初期

18、，生產企業(yè)或中轉倉庫根據(jù)客戶的需求，將貨物準確的運送到客戶手中，形成了配送的雛形——“普通送貨。隨著客戶對產品多樣化和差異化的要求，為了滿足客戶的需求，原始的普通送貨開始轉向分揀、配貨、送貨一體化。因此產生了配送。</p><p>　　按照國家質量技術監(jiān)督局發(fā)布的中華人民共和國國家標準“物流術語”（GB/T 18354—2001），配送是指在經濟合理區(qū)域范圍內根據(jù)用戶要求，對物品進行揀選、加工、包裝、分割、組配等

19、作業(yè)，并按時送達指定地點的物流活動[1]。</p><p>　　1.2 物流配送的功能</p><p>　　配送作為一種新型的物流手段，伴隨著生產的不斷發(fā)展而日趨成熟。發(fā)展配送，無論對于物流系統(tǒng)的完善，企業(yè)的發(fā)展，還是整個經濟社會效益的提高，都具有重要的作用。</p><p>　?。?）配送完善和優(yōu)化了物流系統(tǒng)。第二次世界大戰(zhàn)后，高水平的干線運輸呼喚支線運輸和小搬運

20、配套，但支線運輸和小搬運在適應性、靈活性、服務性上的欠缺，致使運力不合理、運輸成本過高。配送的出現(xiàn)使干線運輸、支線運輸及小搬運統(tǒng)一，輸送過程得以優(yōu)化和完善。</p><p>　?。?）配送提高了末端物流的效益。配送通過大批量進貨，集中發(fā)貨，以及將多個小批量集中一起大批量發(fā)貨，都能有效的節(jié)省運力，實現(xiàn)經濟運輸，降低成本，使末端的物流經濟效益得到提高。</p><p>　?。?）配送通過集中庫

21、存使企業(yè)實現(xiàn)低庫存或零庫存。采取準時制配送方式之后，生產企業(yè)完全可以依靠配送中心的準時配送而不需保持自己的庫存或保持少量安全庫存而不必留有經常庫存。</p><p>　?。?）配送簡化事物，方便客服。采用配送的方式，客戶只需向一處訂購，或一個進貨單位聯(lián)系就可以訂購到以往需要去許多地方才能頂?shù)降呢浳?，因此大大的減輕了客戶的工作量和負擔，也節(jié)省了事務的開支。</p><p>　?。?）配送可以

22、降低整個社會物資的庫存水平。發(fā)展配送，實行集中庫存，整個社會物資的庫存總量必然低于各企業(yè)分散的庫存總量。同時，配送有利于靈活高度，有利于發(fā)揮物資的作用。此外，集中庫存可以發(fā)揮規(guī)模經濟優(yōu)勢，降低庫存成本 [2]。</p><p>　　1.3 配送路線優(yōu)化的意義</p><p>　　配送合理化與否是配送決策系統(tǒng)的重要內容，配送線路的合理與否又是配送合理化的關鍵。選擇合的理配送路線，對企業(yè)和社會

23、都具有很重要的意義。</p><p>　　對企業(yè)來說，(1)優(yōu)化配送路線，可以減少配送時間和配送里程，提高配送效率，增加車輛利用率，降低配送成本。(2)可以加快物流速度，能準時、快速地把貨物送到客戶的手中，提高客戶滿意度。(3)使配送作業(yè)安排合理化，提高企業(yè)作業(yè)效率，有利于企業(yè)提高競爭力與效益[3]。</p><p>　　對社會來說，它可以節(jié)省運輸車輛，減少車輛空載率，降低了社會物流成本，

24、對其他企業(yè)尤其是生產企業(yè)具有重要意義。與此同時，還能緩解交通緊張狀況，減少噪聲、尾氣排放等運輸污染，對民生和環(huán)境也有不容忽視的作用 [4]。</p><p>　　第2章 XX有限公司配送運作現(xiàn)狀</p><p><b>　　2.1 公司簡介</b></p><p>　　XX有限公司地處江西婺源,公司以生產細木工板為主要產品，技術力量雄厚，工藝設

25、備先進研發(fā)能力強。產品經國家人造板質量監(jiān)督核準中心和省、市質量監(jiān)督檢測，GB/T5849-1999、GB18580-2001標準 的E1級質量和環(huán)保標準。公司現(xiàn)有員工370余人，日均產量達2500張/天，年產量60-80萬張，產值達7000余萬元。 </p><p>　　2.2 公司配送現(xiàn)狀</p><p>　　公司的客戶可分為需求量穩(wěn)定的大客戶和需求量隨機的小客戶。大客戶的需求具有時間和

26、地點上的不確定性，需求量大的特點，一般采用租車進行點到點運輸服務或客戶自配卡車。小客戶地點確定，主要位于其所在地的周邊縣市，如圖1所示，共有9個縣市，如景德鎮(zhèn)，黃山市，開化縣等，但需求較小，公司為推廣產品，采用每周專車送貨上門服務。公司現(xiàn)擁有兩輛11噸的貨車，一輛7噸的貨車，若車輛使用欠缺時，可租賃車輛。</p><p>　　目前，對小客戶公司采用的配送線路如圖2所示，該配送線路的弊端在于：配送路線的選擇不合理，

27、優(yōu)化不徹底，導致運距過長，消耗作業(yè)時間偏多，不能充分利用車輛配載容積，浪費較多人力和物力資源，影響公司盈利。</p><p>　　各縣市每星期需求細木工板的基本數(shù)據(jù)如表1所示。</p><p>　　表2-1 各地區(qū)月貨運量 </p><p>　　數(shù)據(jù)來源：于XX有限公司內部資料</p><p>　　圖2-1

28、XX有限公司配送網(wǎng)絡圖1</p><p>　　圖2-2 公司原有配送路線</p><p>　　第3章 物流配送模型及方法描述</p><p>　　3.1 多回路運輸—VRP模型</p><p>　　多回路運輸問題是現(xiàn)實中很普遍的一種調配問題，特別對于有大量服務對象的實體，例如擁有一個上千客戶的企業(yè)。此類調配的核心問題是如何對車輛進行調度。因此

29、，VRP（Vehicle Routing Problem）模型也應運而生，成了解決多回路問題的一個相當成功的模型[5]。</p><p>　　該問題研究目標是：對一系列顧客需求點設計適當?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等），達到一定的優(yōu)化目標（如里程最短，費用最小，時間盡量少等）。它涉及了多輛交通工具的服務對象的選擇和路徑確定兩方面問題[6]。

30、</p><p>　　一個典型的VRP模型可以如下表述：</p><p>　?。?）基本條件 現(xiàn)有m輛相同的車輛停在一個共同的源點，它需給n個客戶提供貨物，顧客為。</p><p>　?。?）模型目標 確定所需的車輛數(shù)N，并指派這些車輛到一個回路中，同時包括回路內的路徑安排和調度，使總費用最小。</p><p>　?。?）限制條件：N不大于m

31、；每一個訂單都要完成；每輛車完成任務后都要回到源點；車輛的容量限制不能超過；特殊問題還需考慮時窗限制；運輸規(guī)章限制[7]。</p><p><b>　　3.2 節(jié)約算法</b></p><p>　　節(jié)約算法（Saving Algorithm）是用來解決運輸車輛數(shù)目不確定的VRP問題，它是目前用來解決VRP模型最有名的啟發(fā)式算法。</p><p>

32、;　　3.2.1節(jié)約算法的基本原理</p><p>　　節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（0，… ，i，0）和（0，j，… ，0）合并成一個回路（0，… ，i，j，…，0）。在上面的合并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如果變化后總運輸距離下降，則稱節(jié)約了運輸距離[6]。相應的變化值，叫做節(jié)約距離，如式（1）所示。</p><p><b>　?。?）<

33、;/b></p><p>　　調整過程如圖3所示[8]。</p><p>　　調整前 調整后</p><p>　　圖3-1 節(jié)約算法的圖像描述</p><p>　　3.2.2節(jié)約里程算法主要步驟</p><p>　　已知條件:需求點集={1

34、,2,…, n},各點需求量,各點間最短距離。</p><p>　　第一步,形成一個初始解。確定各車輛配送點集令, =1,2,…,n (先采取單點配送)。</p><p>　　第二步,進行節(jié)約度的計算。計算所有點對的節(jié)約度 ，然后對計算結果進行升序排列。</p><p>　　第三步，進行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始，直到節(jié)約里程的隊列空為止,

35、重復下列步驟:按照節(jié)約里程隊列從大到小的順序,分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內以及合并次數(shù)不超過2),將i, j連接起來,即可令。如果不是這樣,則從節(jié)約里程隊列中去除當前的節(jié)約里程，分析下一個客戶對[9]。</p><p><b>　　3.3 掃描算法</b></p><p>　　掃描算法（Sweep Algorithm）也是用于求

36、解車輛數(shù)目不限制的VRP問題，與節(jié)約算法不同的是，它屬于亞啟發(fā)式算法，而節(jié)約算法屬于構造算法。</p><p>　　3.3.1 掃描算法的基本原理</p><p>　　掃描算法是一種“先分組后路線”的算法。所謂分組，即指派給每輛車一組點。一種簡單的分組方法是將以配送中心為原點的坐標平面劃分為多個扇形區(qū)域，并初步將每個扇形區(qū)域的點分派給一輛車，然后擴充路線。如果在進行了一次“分組-路線”的路

37、線構造后，還存在未分配點，則再進行“分組-路線”程序。如此反復，直到所有的點均已分配為止[10]。</p><p>　　3.3.2 掃描算法的主要步驟</p><p>　　（1）以起始點0點作為極坐標系的原點，并一連通圖中的任意一顧客點和原點的連線定義為角度零，建立極坐標系。然后對所有的顧客所在的位置，進行極坐標變換。</p><p>　?。?）分組 從最小角度的顧

38、客開始建立一個組，按逆時針方向，將顧客逐個加入到組中，直到顧客的需求總量超出了負載的限制。然后繼續(xù)建立一個新的組，繼續(xù)按逆時針方向，將客戶加入組中。</p><p>　?。?）重復（2）中的過程，直到所有客戶都被分類為止。</p><p>　?。?）路徑優(yōu)化 對各個組內的單回路進行路徑優(yōu)化[11]。</p><p>　　3.4改進后的最近插入法</p>

39、<p>　　TSP模型是單回路運輸問題的最為典型的一個模型，它的全稱是Traveling Salesman Problem1，中文叫做旅行商問題。它是一個典型的NP-Hard問題，對于大規(guī)模的線路優(yōu)化問題，無法獲得最優(yōu)解。最近插入法就是一種解決此問題的啟發(fā)式算法。</p><p>　　3.4.1 最近插入法</p><p>　　最近插入法是Rosenkrantz和Stearns

40、等人在1977年提出的一種用于解決TSP(旅行商)問題的算法。最近插入法由四步完成：</p><p>　?。?）找到最小的節(jié)點，形成一個子回路（subtour），。</p><p>　?。?）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。</p><p>　?。?)在子回路中找到一條?。╥，j）,使得+-最小，然后將節(jié)點插入到節(jié)點，之間，用兩條新的弧(i，k

41、)，（k，j）代替原來的弧（i，j），并將節(jié)點加入到子回路中。</p><p>　?。?）重復步驟（2）、（3），直到所有的節(jié)點都加入到子回路中。</p><p>　　這樣，子回路就演變?yōu)榱艘粋€TSP的解[12]。</p><p>　　由于最近插入法解決的是單回路運輸問題，故筆者在此方法基礎上進行改進和修正，使其能解決多回路運輸VRP問題。有改進的方法如下：<

42、/p><p>　　3.4.2 改進的最近插入法</p><p>　?。?）找到最小的節(jié)點，形成一個子回路（subtour），。</p><p>　　（2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。若此時回路的總貨運量未超過車的載重限制，則繼續(xù)步驟（3）。否則，轉（1）尋找新的一條回路。</p><p>　?。?）)在子回路中找到一條弧

43、（i，j）,使得+-最小，然后將節(jié)點插入到節(jié)點，之間，用兩條新的弧(i，k)，（k，j）代替原來的?。╥，j），并將節(jié)點加入到子回路中。若此時該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟（4）。否則轉步驟（1），尋找新的一條回路。</p><p>　?。?）重復步驟（2）和（3），直到每一個節(jié)點都被歸入某一個子回路中。</p><p>　　第4章 XX有限公司配送路線優(yōu)化研究</

44、p><p>　　4.1 建立VRP模型</p><p>　　多回路運輸問題時現(xiàn)實生活中十分常見的一種調配問題。此類調配問題的核心問題是車輛調度。因此VRP模型也應運而生，成了解決多回路問題的一個相當成功的模型。據(jù)此對XX有限公司的配送系統(tǒng)建立VRP模型。</p><p>　　基本條件：XX公司需給9個客戶送貨，客戶依次為1，2，…,9，現(xiàn)有1輛7噸（長7.8m,寬2.2

45、m,高3.6m）的貨車（每百公里油耗21L），2輛11噸(長9.5m,寬2.3m,高3.6m)的貨車(每百公里油耗27L)，柴油每升7.07元，司機每天工資100元。</p><p>　　模型目標：確定所需要的車輛的數(shù)目N、車輛類型、司機數(shù)量以及各車行走的路徑，并指派這些車輛到一個回路中，同時包括回路內的路徑安排和調度，使得運輸總費用最小。</p><p><b>　　限制條件：

46、</b></p><p>　　（1）基于人性化與安全的考慮，當運輸里程超過350公里時，需配備兩名司機，為防止突發(fā)運輸事件，車輛必須當天回到公司，減去去由于裝卸貨等影響因素，各車最大運輸距離為600公里。</p><p>　?。?） 每輛車完成任務之后都要回到源點0處。</p><p>　?。?） 車輛的容量限制不能超過。7噸的貨車最多可裝300張細木工

47、板，11噸的最多可裝500張細木工板。11噸貨車運輸單價比7噸的低，優(yōu)先使用11噸車，若不超過300張細木工板，則使用7噸貨車。</p><p>　　4.2XX公司的配送線路的分析與優(yōu)化</p><p>　　已知XX公司為0點，分別向9個小客戶點配送細木工板，其擁有一輛7噸的車和兩輛11噸的車， 7噸卡車最大容量為300張細木工板，11噸卡車最大載量為500張。設各點間的距離為，節(jié)約距離為

48、。每輛車的載貨量為，各點需求量為，每輛車的行駛里程為，且公里，婺源為0點，客戶點1，2，…，9。</p><p>　　各縣市的細木工板運量和配送距離如表2所示。</p><p>　　表4-1 運輸任務表</p><p>　　4.2.1 原配送線路基本數(shù)據(jù)分析</p><p>　　目前，XX有限公司對小客戶公司采用的配送模式如圖2所示。各配送線

49、路低得里程，所需司機數(shù)量及工資的基本情況如表3所示。</p><p>　　表4-2 配送信息表</p><p>　　由上表可知，公司每周需7噸貨車5車次配送，司機6人次，所需工資600元，運輸總里程為1270.2千米，消耗的柴油266.75升，所需燃油費1885.87元，一共花費2485.87元。</p><p>　　4.2.2 基于節(jié)約算法的企業(yè)配送路線優(yōu)化<

50、;/p><p>　　首先，確定各縣市間的最短距離，縣市間最距離表4所示。</p><p>　　表4-3 各縣市間最短距離表 （單位：千米）</p><p><b>　　數(shù)據(jù)來源：谷歌地圖</b></p><p>　　然后，形成一初始解，，令，，最短路徑（=1，…，9），且公里，載貨量，且，對9個客戶

51、點進行標記，且。</p><p>　　其次，求節(jié)約里程。根據(jù)最短距離表，根據(jù)式（1）計算出用戶間的節(jié)約里程,并由大到小排列，編制節(jié)約里程順序表，如表5所示。</p><p>　　表4-4 節(jié)約里程順序表 （單位：千米）</p><p>　　最后，按節(jié)約里程從大到小合并路徑</p><p><b>　?。?）對于&

52、lt;/b></p><p><b>　　。</b></p><p>　　故合并3，4兩點，則。</p><p><b>　?。?）對于</b></p><p><b>　　。</b></p><p>　　故合并4，6兩點，則</p>

53、<p>　　（3）對于因為3與6處在同一回路中，故不滿足合并條件。</p><p>　?。?）對于故不滿足合并條件。</p><p><b>　?。?）對于</b></p><p><b>　　。</b></p><p>　　故合并6，7兩點，則</p><p>

54、<b>　　。</b></p><p>　?。?）余下各點的貨運量均大于30，故回路0-3-4-6-7-0不能再與其他點合并。接下來的討論將跳過與點3，4，6，7相關的。</p><p><b>　?。?）對于</b></p><p><b>　　。</b></p><p>　

55、　故合并1，2兩點，則。</p><p><b>　?。?）對于</b></p><p><b>　　。</b></p><p>　　故合并2，5兩點，則</p><p><b>　?。?）對于</b></p><p><b>　　。</

56、b></p><p>　　故合并8，9兩點，則。</p><p>　?。?0），故線路0-1-2-5-0與線路0-8-9-0不能合并。</p><p><b>　　至此，合并結束。</b></p><p>　　最后得到的最優(yōu)結果如表6所示，優(yōu)化線路圖如圖4所示。</p><p>　　表4-5

57、節(jié)約法優(yōu)化結果</p><p>　　由上表可知，公司每周需11噸貨車2車次和7噸貨車1車次配送，司機4人次，所需工資400元，運輸總里程為940.3千米，消耗的柴油239.56升，所需燃油費1686.60元，一共花費2086.60元。</p><p>　　圖4-1 節(jié)約算法求解線路結果</p><p>　　4.2.3 基于掃描算法的企業(yè)配送路線優(yōu)化</p>

58、;<p>　　對XX周邊的9個縣市采用掃描算法進行配送線路的優(yōu)化。</p><p>　　首先建立極坐標系：以XX有限公司所在地婺源縣作為原點，并以點1景德鎮(zhèn)與原點的連線為零角度建立極坐標系，各點的貨運量及極坐標的角坐標值如表7所示。坐標系如圖5所示。</p><p>　　表4-6 運量和極坐標的角坐標值</p><p>　　圖4-2 掃描算法的掃描過程

59、</p><p>　　然后分組：從角度為零向逆時針方向進行掃描，如圖所示。第一個被分組的是客戶1，=180；繼續(xù)轉動，下個被分組的是客戶2，=180+120=300；繼續(xù)轉動，下個被分組的是客戶3，300+120=420；繼續(xù)轉動，下個被分組的是客戶4，=420+60=480；繼續(xù)轉動，下個被分組的是客戶6，=480+80=560>500，由于超過了限制，按分組規(guī)則，需要一個新的組，這樣在第一組里只有客戶1

60、，2，3，4，=480。</p><p>　　進行第二組掃描，最先掃描到的是客戶5，=80；繼續(xù)轉動，下個被分組的是客戶6，=80+220=300；繼續(xù)轉動，下個被分組的是客戶7，=300+70=370；繼續(xù)轉動，下個被分組的是客戶8，=370+90=460；繼續(xù)轉動，下個被分組的是客戶9，=460+200=660>500，超過限制，所以需要一個新的組，這樣在第二組中只有客戶5，6，7，8，=460。<

61、;/p><p>　　在第三組中只剩一個客戶9，故顧客9單獨在一組，=200。</p><p>　　這時，可以得到如圖6所示的分組結果。</p><p>　　圖4-3 掃描算法求解結果</p><p>　　最后對各子回路內的線路優(yōu)化：對上面的3個組，都已經是一個單回路運輸問題，對每個組進行線路優(yōu)化。供應點0是任何一個組的TSP問題的起點和終點，用最

62、近插入法分別對三個客戶組進行求解。</p><p>　　對第一組進行求解。比較表4-2 中從0出發(fā)的所有路徑大小，</p><p>　　這樣，就有顧客點0，1構成一個子回路，。</p><p>　　然后考慮剩下顧客點2，3，4到0和1中某一點的最小距離：</p><p>　　由于對稱性，無論將2插入到0和1之間往返路徑中，結果都是一樣的，這樣

63、，構成了一個新的子回路。</p><p>　　接下來考慮剩下的顧客點3，4到0，1，2中某一點的最小距離</p><p>　　顧客點3有3個位置可以插入，現(xiàn)在分析將點3加入到哪里合適。</p><p>　　插入到（0，1）之間，。</p><p>　　插入到（1，2）之間，。</p><p>　　插入到（2，0）之間，

64、。</p><p>　　比較可知，插入到（2，0）之間增量最小，所以將顧客點3加入到（2，0）間，結果為</p><p>　　重復上面的步驟，將顧客點4加入到子回路中，就可得到一個用最近插入法求得的可行解，，總行駛距離為：。</p><p>　　對第二組進行求解，可得，總行駛距離為：。對第三組進行求解，可得，總行駛距離為：。</p><p>

65、　　最后得到的最優(yōu)結果如表8所示，優(yōu)化線路圖如圖7所示。</p><p>　　表4-7掃描算法優(yōu)化結果</p><p>　　由上表可知，公司每周需11噸貨車2車次和7噸貨車1車次配送，司機5人次，所需工資500元，運輸總里程為934.1千米，消耗的柴油242.31升，所需燃油費1713.11元，一共花費2213.11 元。</p><p>　　圖4-4 掃描算法求解

66、線路結果</p><p>　　4.2.4 基于改進的最近插入法的企業(yè)配送路線優(yōu)化</p><p>　　令T={0},N={0，1，2……,10}，比較表4-2 中從0出發(fā)的所有路徑大小。因為，所以就有顧客點0，1構成一個子回路，，此時，。</p><p>　　然后在剩余顧客點（1，2，3，4，6，7，8，9）中尋找到0和5中某一點的最小距離，，,因為，所以在子回路插

67、入點1。由于對稱性，無論將1插入到0和5之間往返路徑中，結果都是一樣的，這樣，構成了一個新的子回路，，。</p><p>　　再次尋找剩余顧客點到0，1， 5中某一點的最小距離：可知最小距離為</p><p>　　此時, ，因為，所以在子回路插入點2。</p><p>　　將點2分別插入（0，1），（1，5），（5，0）中，比較得：插入到（1，5）中增量最小，。&l

68、t;/p><p>　　此時構成了一個新的子回路，，。</p><p>　　再次對剩余的顧客點按照上訴方法進行優(yōu)化，可構成另子回路和子回路</p><p>　　利用改進的最近插入法得到優(yōu)化結果如表9所示，優(yōu)化線路結果如圖8所示。</p><p>　　表4-8 改進的最近插入法優(yōu)化結果</p><p>　　由上表可知，公司每周

69、需11噸貨車3車次和，司機4人次，所需工資400元，運輸總里程為963.6千米，消耗的柴油260.17升，所需燃油費1839.42元，一共花費2239.42元。</p><p>　　圖4-5 改進的最近插入法求解線路結果</p><p>　　4.3 三種優(yōu)化方案比較分析</p><p>　　由上文可知，通過節(jié)約算法，掃描算法和改進后的最近插入法分別對配送線路進行優(yōu)化

70、，可得到三種不同的優(yōu)化方案，因此我們需要通過一系列指標來評價方案的優(yōu)劣性。本文將以所需車輛數(shù)，行駛總里程，總油耗，人力資源和總費用這些指標，對三種優(yōu)化后的方案進行評價分析，如表10所示。</p><p>　　表4-9優(yōu)化結果對比表</p><p>　　從上表的對比中可知，從車次需求數(shù)的角度來看，優(yōu)化后的三種方案需求車次數(shù)相同，但優(yōu)化后的方案與優(yōu)化前方案相比較節(jié)約了2/5的車次需求。優(yōu)化后的

71、方案需要使用更少的車次，減少了XX用車緊張進而租車情況的出現(xiàn)，使XX車輛安排使用上具有更大彈性。因此，在用車角度上考慮，優(yōu)化后的方案均比優(yōu)化前的方案合理，優(yōu)化后的三種方案等價。</p><p>　　從總運輸里程角度考慮，優(yōu)化后的三種方案的總運輸里程分別為940.3千米，934.1千米，963.6千米，與原方案的1303.4千米相比較，均減少了車輛行駛的里程數(shù)。優(yōu)化后的方案能減少了公司車輛的損耗和資源的浪費，給XX

72、帶去更多的效益。因此，從運輸里程的角度考慮，優(yōu)化后的方案掃描算法最優(yōu)，節(jié)約算法次之，改進后的最近插入法再次之。</p><p>　　從燃油消耗的角度考慮，優(yōu)化后的三種方案的消耗分別為239.56升，242.31升，260.17升，與原方案的266.75升相比較，三種優(yōu)化方案均降低了油耗量，改進后的插入法優(yōu)化后的方案消耗更多的油耗。配送線路優(yōu)化后，不僅能減少XX公司燃油費用的支出，還能降低社會資源的浪費。因此，從燃

73、油消耗的角度上考慮，節(jié)約算法最優(yōu)，掃描算法次之。</p><p>　　從公司人力資源消耗角度來考慮，優(yōu)化后的方案所需司機依次為4，5，4人次，減少人力的消耗為2，1，2人次。三種優(yōu)化后的方案均能使公司在人員安排上將更具有彈性，還能降低公司費用的支出。因此，從XX人力資源消耗的角度考慮，節(jié)約算法和改進后的最近插入法最優(yōu)，掃描算法次之。</p><p>　　從支出的總費用角度來考慮，優(yōu)化后的方

74、案的費用支出依次2086.60元，2313.11元，2239.42元，與原方案的為2485.87元相比較，改進后的插入法優(yōu)化后的方案花費更多的費用支出。因此，從支出總費用的角度考慮，節(jié)約算法最優(yōu)，改進后的最近插入法次之。</p><p>　　結合車次需求數(shù)，總運輸里程，燃油消耗，人力資源消耗，支出的總費用五個角度一齊分析，節(jié)約算法最優(yōu)。但是，本文的配送距離略有超出配送最佳范圍，模型存在著一定的缺陷。在計算過程中也

75、將一些因素理想化了，與實際情況不完全相符。例如，并未考慮具體的道路信息，運輸規(guī)章等。因此，XX應該根據(jù)實際情況合理選擇配送方案。</p><p><b>　　結論</b></p><p>　　XX為了推廣品牌，擴大市場，對小客服實施了進行送貨上門服務。但隨之而來的就是配送成本的問題，公司為保持正常的盈利，降低配送成本則勢在必行，這就意味著公司要對原配送路線進行優(yōu)化。&

76、lt;/p><p>　　本文針對XX有限公司9個縣市配送狀況進行了線路規(guī)劃，應用了節(jié)約算法、掃描算法及改進的最近插入法三種方法進行了計算分析，經過比較3種結果，選擇出了一個最優(yōu)方案，經過效益分析，證明經過優(yōu)化后的配送里程數(shù)縮短了329.9km，節(jié)約燃油27.17升，從而降低了每天的運輸費用大概375元，除此以外，每周減少發(fā)車次數(shù)2次，司機2人次，輛閑置下來的貨車和司機還可以應對一些緊急情況，提高了公司的服務質量。&l

77、t;/p><p>　　求解車輛路徑問題的方法非常豐富，本文采用了3種方法雖然都能夠得到可行的配送運輸路徑方案，但是只能是可行解而不是精確解。節(jié)約算法，掃描算法和改進后的最近插入法都是解決VRP模型的算法。這類算法雖然能夠比較快的解決有關問題，但其優(yōu)劣往往取決于算法設計者的實際經驗以及處理樣本空間的大小。在實際求解過程中，應根據(jù)各類算法的使用范圍，并針對配送優(yōu)化問題的具體情況，尋找最適合的求解方法，找到最優(yōu)配送路路線。

78、</p><p>　　對于大部分企業(yè)來說，配送成本最低和滿足客戶對時間的高要求是配送中急需解決的問題，這都需要研究物流配送路徑優(yōu)化模型和算法來解決。從配送中心到客戶位置的物流在配送領域是一個負載的調度問題。如果能通過比較科學的物流配送路徑優(yōu)化模型和算法，來實現(xiàn)企業(yè)的人工調度和車輛安排，使得物流中心本身運作效率更高，成本控制得當，企業(yè)的效益也會不斷提升。</p><p>　　在物流快速發(fā)展的

79、大背景下，XX有限公司要充分運用物流理論，與實踐相結合，同時考慮到時代賦予產品特殊的意義，積極拓展自己的經營方式，與第三方物流公司保持積極地合作，給企業(yè)注入新的血液和活力。</p><p><b>　　致謝語</b></p><p>　　值此拙作完成之際，我首先要衷心地感謝XXX指導老師，他為本人從事這一方向的研究給予了充分的鼓勵和悉心的指導。師從XXX老師，我不僅在

80、學術研究和科研方面得到了諄諄教誨，導師嚴謹細致的治學態(tài)度、寬厚正直的待人之道更是我學之不盡的人生財富。在此，謹向XX老師表示最真誠的感謝和崇高的敬意!</p><p>　　最后，還要感謝xx大學所有關心和教育過學生的老師們，感謝xx大學圖書館對于論文的幫助，以及XX有限公司提供寶貴的資料。同時，感謝評閱本文的各位專家，敬請?zhí)岢鰧氋F的意見，并予以指正。</p><p>　　衷心地感謝在我完成

81、論文的過程中給與幫助和支持的所有老師、同學和朋友！</p><p><b>　　參考文獻</b></p><p>　　[1] 高曉亮,伊俊敏,甘衛(wèi)華.倉儲與配送管理[M].清華大學出版社,2006.</p><p>　　[2] 孔少徹,梁彤錚.商品物流配送優(yōu)化策略探討[J].市場論壇,2009(7):94-95. </p><

82、;p>　　[3] Elliot Rabinovich, Manus Rungtusanatham and Timothy M. Laseter. Physical distribution service performance and Internet retailer margins: The drop-shipping context[J].Journal of Operations Management,2008(6):7

83、67-780.</p><p>　　[4] 蔡臨寧.物流系統(tǒng)規(guī)劃—建模實例分析[M].北京:機械工業(yè)出版社,2003.孔少徹,梁彤錚.商品物流配送優(yōu)化策略探討[J].市場論壇,2009(7):94-95.</p><p>　　[5] 孫焰.現(xiàn)代物流管理技術[M].上海:同濟大學出版社,2004.</p><p>　　[6] Gianpaolo Ghiani. Gil

84、bert Laporte. Roberto Musmanno. Introduction to Logistics Systems Planning and Control [M]. T&T Productions Ltd, London,2004(1):3-15.</p><p>　　[7] 王鑫.物流配送中車輛優(yōu)化調度問題的研究與實踐[D].沈陽:沈陽航空工業(yè)學院計算機應用技術,2006.</p

85、><p>　　[8] 徐劍,牟燕妮等.物流配送車輛調度優(yōu)化方法比較研究[J].物流科技,2006(2):46-49.</p><p>　　[9] 許星,物流配送路徑優(yōu)化問題的研究[D].浙江:浙江大學計算機科學與技術學院計算機應用技術,2006.</p><p>　　[10] 韓世蓮,物流配送線路多目標優(yōu)化方法研究[D].江蘇:東南大學載運工具運用工程,2006.<

86、;/p><p>　　[11] Henning Rekersbrink, Thomas Makuschewitz, Bernd Scholz-Reiter. A distributed routing concept for vehicle routing problems[J]. Logistics Research,2009,(1):45-52.</p><p>　　[12] 李金蘋.現(xiàn)代物