畢業(yè)論文-配送線路優(yōu)化

1、 百源木業(yè)有限公司配送線路優(yōu)化方案的研究與設計摘要 高效率合理的配送是物流系統(tǒng)順利運行的保證，配送線路安排的合理與否對配送速度、成本、效益影響很大。正確合理地安排車輛的配送線路，實現(xiàn)合理的線路運輸，可以有效地節(jié)約運輸時間，增加車輛利用率，從而降低運輸成本，提高企業(yè)經(jīng)濟效益與客戶服務水平，使企業(yè)達到科學化的物流管理, 這也是企業(yè)提高自身競爭力的有效途徑之一。物流配送路徑優(yōu)化問題具有很高的計算復雜性，屬于NP完全難問題，高效的精確算法存在的可能性不大，但可根據(jù)啟發(fā)算法求得近似最優(yōu)解。本文首先對物流配送進行概述，然后以婺源百源木業(yè)有限公司的配送方案為例，對百源木業(yè)有限公司的配送現(xiàn)狀進行分析，并運用節(jié)

2、約算法、掃描算法以及改進后的最近插入法對百源木業(yè)有限公司的配送線路進行優(yōu)化，提出最優(yōu)配送方案。關鍵詞 配送 車輛路徑問題 節(jié)約算法 掃描算法 改進的最近插入法Research and Designation of optimization of Baiyuan Wood Co., Ltd. distribution lineAbstract Reasonable and efficient distribution is the insurance of a smooth running logistics system; distribution line arrangement is re

3、asonable 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 transport line can effectively increase the utilization of vehicles, save transportation time, thus reducing transportation costs

4、, improving economic efficiency, enhancing customer service levels and enable enterprises to achieve scientific logistics management, which is one of the effective way for an enterprise to improve its competitiveness. The optimization of logistics distribution routing which has high computational co

5、mplexity is a NP-hard problem, that is why efficient exact algorithm is unlikely to exist. In the beginning of this paper is an overview of logistics and distribution, and then take Wuyuan Baiyuan Wood Co., Ltd. distribution as an example to analysis of the status of its distribution, and use saving

6、 algorithm, scanning algorithm and the improved method has recently inserted to optimize the distribution lines for Wuyuan Baiyuan Wood Co., and at last, propose the best distribution scheme.Key words Distribution Vehicle routing problem Saving algorithm Sweep algorithm Improved nearest insertion目錄

7、TOC o 1-3 h z u HYPERLINK l _Toc295330123 引言 PAGEREF _Toc295330123 h 4 HYPERLINK l _Toc295330124 第1章 物流配送概述 PAGEREF _Toc295330124 h 3 HYPERLINK l _Toc295330125 1.1物流配送的概念 PAGEREF _Toc295330125 h 3 HYPERLINK l _Toc295330126 1.2 物流配送的功能 PAGEREF _Toc295330126 h 4 HYPERLINK l _Toc295330127 1.3 配送路線優(yōu)化的意義

8、 PAGEREF _Toc295330127 h 4 HYPERLINK l _Toc295330128 第2章 百源木業(yè)有限公司配送運作現(xiàn)狀 PAGEREF _Toc295330128 h 5 HYPERLINK l _Toc295330129 2.1 公司簡介 PAGEREF _Toc295330129 h 5 HYPERLINK l _Toc295330130 2.2 公司配送現(xiàn)狀 PAGEREF _Toc295330130 h 5 HYPERLINK l _Toc295330131 第3章 物流配送模型及方法描述 PAGEREF _Toc295330131 h 8 HYPERLINK

9、l _Toc295330132 3.1 多回路運輸VRP模型 PAGEREF _Toc295330132 h 8 HYPERLINK l _Toc295330133 3.2 節(jié)約算法 PAGEREF _Toc295330133 h 8 HYPERLINK l _Toc295330134 3.2.1節(jié)約算法的基本原理 PAGEREF _Toc295330134 h 8 HYPERLINK l _Toc295330135 3.2.2節(jié)約里程算法主要步驟 PAGEREF _Toc295330135 h 9 HYPERLINK l _Toc295330136 3.3 掃描算法 PAGEREF _Toc

10、295330136 h 10 HYPERLINK l _Toc295330137 3.3.1 掃描算法的基本原理 PAGEREF _Toc295330137 h 10 HYPERLINK l _Toc295330138 3.3.2 掃描算法的主要步驟 PAGEREF _Toc295330138 h 10 HYPERLINK l _Toc295330139 3.4改進后的最近插入法 PAGEREF _Toc295330139 h 10 HYPERLINK l _Toc295330140 3.4.1 最近插入法 PAGEREF _Toc295330140 h 10 HYPERLINK l _Toc

11、295330141 3.4.2 改進的最近插入法 PAGEREF _Toc295330141 h 11 HYPERLINK l _Toc295330142 第4章 百源木業(yè)有限公司配送路線優(yōu)化研究 PAGEREF _Toc295330142 h 12 HYPERLINK l _Toc295330143 4.1 建立VRP模型 PAGEREF _Toc295330143 h 12 HYPERLINK l _Toc295330144 4.2百源木業(yè)公司的配送線路的分析與優(yōu)化 PAGEREF _Toc295330144 h 12 HYPERLINK l _Toc295330145 4.2.1 原配送

12、線路基本數(shù)據(jù)分析 PAGEREF _Toc295330145 h 13 HYPERLINK l _Toc295330146 4.2.2 基于節(jié)約算法的企業(yè)配送路線優(yōu)化 PAGEREF _Toc295330146 h 13 HYPERLINK l _Toc295330147 4.2.3 基于掃描算法的企業(yè)配送路線優(yōu)化 PAGEREF _Toc295330147 h 17 HYPERLINK l _Toc295330148 4.2.4 基于改進的最近插入法的企業(yè)配送路線優(yōu)化 PAGEREF _Toc295330148 h 21 HYPERLINK l _Toc295330149 4.3 三種優(yōu)化方

13、案比較分析 PAGEREF _Toc295330149 h 22 HYPERLINK l _Toc295330150 結論 PAGEREF _Toc295330150 h 25 HYPERLINK l _Toc295330151 致謝語 PAGEREF _Toc295330151 h 26 HYPERLINK l _Toc295330152 參考文獻 PAGEREF _Toc295330152 h 27引言隨著社會主義市場經(jīng)濟的不斷發(fā)展，作為“第三利潤源泉”的物流對經(jīng)濟活動的影響日益明顯，引起了人們越來越多的重視，成為當前“最重要的競爭領域”。配送是現(xiàn)代物流的一個重要環(huán)節(jié)，隨著物流的全球化、信

14、息化及一體化,配送在整個物流系統(tǒng)中的作用變得越來越重要。配送是連接生產(chǎn)與消費之間的一種中介服務。它是指按客戶(包括零售商店、用戶等)的訂貨要求(包括貨物種類、數(shù)量和時間等方面的要求)，在物流中心(包括配送中心、倉庫、車站、港口等)進行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。配送不是單純的運輸或送貨，而是運輸與其他活動（集貨，分貨，配貨）的組合，是“配”與“送”的有機結合。因此對于配送問題的研究可分為對 “配”和“送”兩方面的研究。“配”主要為配送中心選址問題，“送”包括旅行商問題(TSP)、車輛路線優(yōu)化問題(VRP)。由于選址的外部因素（經(jīng)濟，基礎設施，環(huán)境等）及內(nèi)部因素（企業(yè)

15、戰(zhàn)略，勞動力成本和素質(zhì)等）的影響，單純考慮距離問題的選址是不合理的，因此在本文中不對“配”進行研究，主要對“送”進行研究。配送路線的優(yōu)化，是配送優(yōu)化中的一個關鍵環(huán)節(jié)。在配送過程中，配送線路合理與否對配送速度、成本、效益影響很大。設計合理、高效的配送路線方案，不僅可以減少配送時間，降低作業(yè)成本，提高企業(yè)的效益，而且可以更好地為客戶服務，提高客戶的滿意度，維護企業(yè)良好的形象。配送線路優(yōu)化是指對一系列的發(fā)貨點和收貨點，組織適當?shù)男熊嚶肪€使車輛有序的通過它們，在滿足一定的約束條件下（貨物需求量與發(fā)送量，車輛容量限制，行駛里程限制），力爭實現(xiàn)一定的目標（行駛里程最短，使用車輛盡可能少）。但配送作業(yè)情況復

16、雜多變，不僅存在配送點多、貨物種類多、道路網(wǎng)復雜、路況多變等情況，而且運輸服務地區(qū)內(nèi)需求網(wǎng)點分布也不均勻，使得線路優(yōu)化問題是一個無確定解多項式難題，需要啟發(fā)算法去求得近似最優(yōu)解。本文將以百源木業(yè)有限公司當前的配送線路的優(yōu)化問題作為研究對象，對各縣市需求量及運距進行分析計算，建立VRP數(shù)學模型，運用節(jié)約算法和掃描算法以及改進的最近插入法對建立的模型進行求解，對百源木業(yè)的配送路線進行優(yōu)化。最后對三種方法求得的結果進行比較分析，從而為該公司提供較合理的配送方案，以期減少配送里程，降低物流運輸成本，提高該公司物流運作效率，客戶服務質(zhì)量和整體競爭力。第1章 物流配送概述1.1物流配送的概念配送（dist

17、ribution）起源于“送貨上門”。20世紀60年代初期，生產(chǎn)企業(yè)或中轉(zhuǎn)倉庫根據(jù)客戶的需求，將貨物準確的運送到客戶手中，形成了配送的雛形“普通送貨。隨著客戶對產(chǎn)品多樣化和差異化的要求，為了滿足客戶的需求，原始的普通送貨開始轉(zhuǎn)向分揀、配貨、送貨一體化。因此產(chǎn)生了配送。按照國家質(zhì)量技術監(jiān)督局發(fā)布的中華人民共和國國家標準“物流術語”（GB/T 183542001），配送是指在經(jīng)濟合理區(qū)域范圍內(nèi)根據(jù)用戶要求，對物品進行揀選、加工、包裝、分割、組配等作業(yè)，并按時送達指定地點的物流活動1。1.2 物流配送的功能配送作為一種新型的物流手段，伴隨著生產(chǎn)的不斷發(fā)展而日趨成熟。發(fā)展配送，無論對于物流系統(tǒng)的完善，

18、企業(yè)的發(fā)展，還是整個經(jīng)濟社會效益的提高，都具有重要的作用。（1）配送完善和優(yōu)化了物流系統(tǒng)。第二次世界大戰(zhàn)后，高水平的干線運輸呼喚支線運輸和小搬運配套，但支線運輸和小搬運在適應性、靈活性、服務性上的欠缺，致使運力不合理、運輸成本過高。配送的出現(xiàn)使干線運輸、支線運輸及小搬運統(tǒng)一，輸送過程得以優(yōu)化和完善。（2）配送提高了末端物流的效益。配送通過大批量進貨，集中發(fā)貨，以及將多個小批量集中一起大批量發(fā)貨，都能有效的節(jié)省運力，實現(xiàn)經(jīng)濟運輸，降低成本，使末端的物流經(jīng)濟效益得到提高。（3）配送通過集中庫存使企業(yè)實現(xiàn)低庫存或零庫存。采取準時制配送方式之后，生產(chǎn)企業(yè)完全可以依靠配送中心的準時配送而不需保持自己的庫

19、存或保持少量安全庫存而不必留有經(jīng)常庫存。（4）配送簡化事物，方便客服。采用配送的方式，客戶只需向一處訂購，或一個進貨單位聯(lián)系就可以訂購到以往需要去許多地方才能頂?shù)降呢浳?，因此大大的減輕了客戶的工作量和負擔，也節(jié)省了事務的開支。（5）配送可以降低整個社會物資的庫存水平。發(fā)展配送，實行集中庫存，整個社會物資的庫存總量必然低于各企業(yè)分散的庫存總量。同時，配送有利于靈活高度，有利于發(fā)揮物資的作用。此外，集中庫存可以發(fā)揮規(guī)模經(jīng)濟優(yōu)勢，降低庫存成本 2。1.3 配送路線優(yōu)化的意義配送合理化與否是配送決策系統(tǒng)的重要內(nèi)容，配送線路的合理與否又是配送合理化的關鍵。選擇合的理配送路線，對企業(yè)和社會都具有很重要的意

20、義。 對企業(yè)來說，(1)優(yōu)化配送路線，可以減少配送時間和配送里程，提高配送效率，增加車輛利用率，降低配送成本。(2)可以加快物流速度，能準時、快速地把貨物送到客戶的手中，提高客戶滿意度。(3)使配送作業(yè)安排合理化，提高企業(yè)作業(yè)效率，有利于企業(yè)提高競爭力與效益3。 對社會來說，它可以節(jié)省運輸車輛，減少車輛空載率，降低了社會物流成本，對其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。與此同時，還能緩解交通緊張狀況，減少噪聲、尾氣排放等運輸污染，對民生和環(huán)境也有不容忽視的作用 4。 第2章 百源木業(yè)有限公司配送運作現(xiàn)狀2.1 公司簡介百源木業(yè)有限公司地處江西婺源,公司以生產(chǎn)細木工板為主要產(chǎn)品，技術力量雄厚，工藝

21、設備先進研發(fā)能力強。產(chǎn)品經(jīng)國家人造板質(zhì)量監(jiān)督核準中心和省、市質(zhì)量監(jiān)督檢測，GB/T5849-1999、GB18580-2001標準 的E1級質(zhì)量和環(huán)保標準。公司現(xiàn)有員工370余人，日均產(chǎn)量達2500張/天，年產(chǎn)量60-80萬張，產(chǎn)值達7000余萬元。 2.2 公司配送現(xiàn)狀公司的客戶可分為需求量穩(wěn)定的大客戶和需求量隨機的小客戶。大客戶的需求具有時間和地點上的不確定性，需求量大的特點，一般采用租車進行點到點運輸服務或客戶自配卡車。小客戶地點確定，主要位于其所在地的周邊縣市，如圖1所示，共有9個縣市，如景德鎮(zhèn)，黃山市，開化縣等，但需求較小，公司為推廣產(chǎn)品，采用每周專車送貨上門服務。公司現(xiàn)擁有兩輛11

22、噸的貨車，一輛7噸的貨車，若車輛使用欠缺時，可租賃車輛。目前，對小客戶公司采用的配送線路如圖2所示，該配送線路的弊端在于：配送路線的選擇不合理，優(yōu)化不徹底，導致運距過長，消耗作業(yè)時間偏多，不能充分利用車輛配載容積，浪費較多人力和物力資源，影響公司盈利。各縣市每星期需求細木工板的基本數(shù)據(jù)如表1所示。 表2-1 各地區(qū)月貨運量 客戶1景德鎮(zhèn)2樂平市3鷹潭市4貴溪市5德興市6上饒市7常山縣8開化縣9黃山市貨運量18012012060802207090200數(shù)據(jù)來源：于百源木業(yè)有限公司內(nèi)部資料圖2-1 百源木業(yè)有限公司配送網(wǎng)絡圖11. 圖片來源：1. 圖片來源：HYPERLINK /012345687

23、9 圖2-2 公司原有配送路線第3章 物流配送模型及方法描述3.1 多回路運輸VRP模型多回路運輸問題是現(xiàn)實中很普遍的一種調(diào)配問題，特別對于有大量服務對象的實體，例如擁有一個上千客戶的企業(yè)。此類調(diào)配的核心問題是如何對車輛進行調(diào)度。因此，VRP（Vehicle Routing Problem）模型也應運而生，成了解決多回路問題的一個相當成功的模型5。該問題研究目標是：對一系列顧客需求點設計適當?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等），達到一定的優(yōu)化目標（如里程最短，費用最小，時間盡量少等）。它涉及了多輛交通工具的服務對象的選擇和路

24、徑確定兩方面問題6。一個典型的VRP模型可以如下表述：（1）基本條件 現(xiàn)有m輛相同的車輛停在一個共同的源點，它需給n個客戶提供貨物，顧客為。（2）模型目標 確定所需的車輛數(shù)N，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使總費用最小。（3）限制條件：N不大于m；每一個訂單都要完成；每輛車完成任務后都要回到源點；車輛的容量限制不能超過；特殊問題還需考慮時窗限制；運輸規(guī)章限制7。3.2 節(jié)約算法節(jié)約算法（Saving Algorithm）是用來解決運輸車輛數(shù)目不確定的VRP問題，它是目前用來解決VRP模型最有名的啟發(fā)式算法。3.2.1節(jié)約算法的基本原理節(jié)約算法的核心思想是將運輸問題

25、中存在的兩個回路（0， ，i，0）和（0，j， ，0）合并成一個回路（0， ，i，j，0）。在上面的合并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如果變化后總運輸距離下降，則稱節(jié)約了運輸距離6。相應的變化值，叫做節(jié)約距離，如式（1）所示。 （1）調(diào)整過程如圖3所示8。jjjji 0i 00ii 調(diào)整前 調(diào)整后 圖3-1 節(jié)約算法的圖像描述3.2.2節(jié)約里程算法主要步驟已知條件:需求點集=1,2, n,各點需求量,各點間最短距離。第一步,形成一個初始解。確定各車輛配送點集令, =1,2,n (先采取單點配送)。第二步,進行節(jié)約度的計算。計算所有點對的節(jié)約度C第三步，進行回路的合并。從升序排列的

26、節(jié)約度序列中的最上面的值開始，直到節(jié)約里程Cij的隊列空為止,重復下列步驟:按照節(jié)約里程Cij隊列從大到小的順序,分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過2),將i, j連接起來,即可令3.3 掃描算法掃描算法（Sweep Algorithm）也是用于求解車輛數(shù)目不限制的VRP問題，與節(jié)約算法不同的是，它屬于亞啟發(fā)式算法，而節(jié)約算法屬于構造算法。3.3.1 掃描算法的基本原理掃描算法是一種“先分組后路線”的算法。所謂分組，即指派給每輛車一組點。一種簡單的分組方法是將以配送中心為原點的坐標平面劃分為多個扇形區(qū)域，并初步將每個扇形區(qū)域的點分派給一輛車，

27、然后擴充路線。如果在進行了一次“分組-路線”的路線構造后，還存在未分配點，則再進行“分組-路線”程序。如此反復，直到所有的點均已分配為止10。3.3.2 掃描算法的主要步驟（1）以起始點0點作為極坐標系的原點，并一連通圖中的任意一顧客點和原點的連線定義為角度零，建立極坐標系。然后對所有的顧客所在的位置，進行極坐標變換。（2）分組 從最小角度的顧客開始建立一個組，按逆時針方向，將顧客逐個加入到組中，直到顧客的需求總量超出了負載的限制。然后繼續(xù)建立一個新的組，繼續(xù)按逆時針方向，將客戶加入組中。（3）重復（2）中的過程，直到所有客戶都被分類為止。（4）路徑優(yōu)化 對各個組內(nèi)的單回路進行路徑優(yōu)化11。3

28、.4改進后的最近插入法TSP模型是單回路運輸問題的最為典型的一個模型，它的全稱是Traveling Salesman Problem1，中文叫做旅行商問題。它是一個典型的NP-Hard問題，對于大規(guī)模的線路優(yōu)化問題，無法獲得最優(yōu)解。最近插入法就是一種解決此問題的啟發(fā)式算法。3.4.1 最近插入法 最近插入法是Rosenkrantz和Stearns等人在1977年提出的一種用于解決TSP(旅行商)問題的算法。最近插入法由四步完成：（1）找到最小的節(jié)點，形成一個子回路（subtour），。（2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。（3)在子回路中找到一條?。╥，j）,使得+-最小

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

30、條?。╥，j）,使得+-最小，然后將節(jié)點插入到節(jié)點，之間，用兩條新的弧(i，k)，（k，j）代替原來的?。╥，j），并將節(jié)點加入到子回路中。若此時該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟（4）。否則轉(zhuǎn)步驟（1），尋找新的一條回路。（4）重復步驟（2）和（3），直到每一個節(jié)點都被歸入某一個子回路中。第4章 百源木業(yè)有限公司配送路線優(yōu)化研究4.1 建立VRP模型多回路運輸問題時現(xiàn)實生活中十分常見的一種調(diào)配問題。此類調(diào)配問題的核心問題是車輛調(diào)度。因此VRP模型也應運而生，成了解決多回路問題的一個相當成功的模型。據(jù)此對百源木業(yè)有限公司的配送系統(tǒng)建立VRP模型?；緱l件：百源木業(yè)公司需給9個客戶

31、送貨，客戶依次為1，2，,9，現(xiàn)有1輛7噸（長7.8m,寬2.2m,高3.6m）的貨車（每百公里油耗21L），2輛11噸(長9.5m,寬2.3m,高3.6m)的貨車(每百公里油耗27L)，柴油每升7.07元，司機每天工資100元。模型目標：確定所需要的車輛的數(shù)目N、車輛類型、司機數(shù)量以及各車行走的路徑，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使得運輸總費用最小。限制條件：（1）基于人性化與安全的考慮，當運輸里程超過350公里時，需配備兩名司機，為防止突發(fā)運輸事件，車輛必須當天回到公司，減去去由于裝卸貨等影響因素，各車最大運輸距離為600公里。（2） 每輛車完成任務之后都要回

32、到源點0處。（3） 車輛的容量限制不能超過。7噸的貨車最多可裝300張細木工板，11噸的最多可裝500張細木工板。11噸貨車運輸單價比7噸的低，優(yōu)先使用11噸車，若不超過300張細木工板，則使用7噸貨車。4.2百源木業(yè)公司的配送線路的分析與優(yōu)化已知百源木業(yè)公司為0點，分別向9個小客戶點配送細木工板，其擁有一輛7噸的車和兩輛11噸的車， 7噸卡車最大容量為300張細木工板，11噸卡車最大載量為500張。設各點間的距離為，節(jié)約距離為。每輛車的載貨量為，各點需求量為，每輛車的行駛里程為，且公里，婺源為0點，客戶點1，2，9。各縣市的細木工板運量和配送距離如表2所示。表4-1 運輸任務表客戶1景德鎮(zhèn)2

33、樂平市3鷹潭市4貴溪市5德興市6上饒市7常山縣8開化縣9黃山市貨運量（張/周）18012012060802207090200配送距離（km）75.989.2186.7170.357.0153.887.081.5 原配送線路基本數(shù)據(jù)分析目前，百源木業(yè)有限公司對小客戶公司采用的配送模式如圖2所示。各配送線路低得里程，所需司機數(shù)量及工資的基本情況如表3所示。表4-2 配送信息表路線運距運貨量車型司機0-1-2-0213.7km3007噸貨車10-3-4-0373.4km1807噸貨車20-5-6-0315.4km3007噸貨車10-7-8-0202.7km1607噸貨車10-9-0165.0km20

34、07噸貨車1由上表可知，公司每周需7噸貨車5車次配送，司機6人次，所需工資600元，運輸總里程為1270.2千米，消耗的柴油266.75升，所需燃油費1885.87元，一共花費2485.87元。4.2.2 基于節(jié)約算法的企業(yè)配送路線優(yōu)化首先，確定各縣市間的最短距離，縣市間最距離表4所示。表4-3 各縣市間最短距離表 （單位：千米）縣市0婺源縣1景德鎮(zhèn)2樂平市3鷹潭市4貴溪市5德興市6上饒市7常山縣8開化縣9黃山市0婺源縣075.989.2186.7170.357.0153.887.081.582.51景德鎮(zhèn)048.6157.1173.886.1194.3161.2148.9154.72樂平市0

35、97.3117.048.6143.1158.1156.4170.53鷹潭市016.4125.098.5170.2206.3268.74貴溪市0107.281.5153.9190.1251.35德興市0104.6103.298.3103.16上饒市083.3115.7232.07常山縣034.2126.88開化縣091.49黃山市0數(shù)據(jù)來源：谷歌地圖然后，形成一初始解，令，最短路徑（=1，9），且公里，載貨量，且，對9個客戶點進行標記，且。其次，求節(jié)約里程。根據(jù)最短距離表，根據(jù)式（1）計算出用戶間的節(jié)約里程,并由大到小排列，編制節(jié)約里程順序表，如表5所示。 表4-4 節(jié)約里程順序表 （單位：千米

36、）連接點節(jié)約里程連接點節(jié)約里程連接點節(jié)約里程連接點節(jié)約里程3-4340.63-5118.71-472.42-718.14-6242.61-2116.53-861.92-814.33-6242.05-6106.14-861.71-88.52-3178.61-3105.57-952.76-94.36-7157.53-7103.51-546.81-93.72-4142.54-7103.45-740.81-71.77-8124.32-699.95-840.54-91.54-5120.32-597.65-936.42-91.26-8119.68-972.61-635.43-90.5最后，按節(jié)約里程從大到

37、小合并路徑（1）對于。故合并3，4兩點，則。（2）對于。故合并4，6兩點，則（3）對于因為3與6處在同一回路中，故不滿足合并條件。（4）對于故不滿足合并條件。（5）對于。故合并6，7兩點，則。（6）余下各點的貨運量均大于30，故回路0-3-4-6-7-0不能再與其他點合并。接下來的討論將跳過與點3，4，6，7相關的。（7）對于。故合并1，2兩點，則。（8）對于。故合并2，5兩點，則（9）對于。故合并8，9兩點，則。（10），故線路0-1-2-5-0與線路0-8-9-0不能合并。至此，合并結束。最后得到的最優(yōu)結果如表6所示，優(yōu)化線路圖如圖4所示。表4-5節(jié)約法優(yōu)化結果路線運距運貨量車型司機0-3

38、-4-6-7-0454.8km47011噸貨車20-1-2-5-0230.1km38011噸貨車10-8-9-0255.4km2907噸貨車1由上表可知，公司每周需11噸貨車2車次和7噸貨車1車次配送，司機4人次，所需工資400元，運輸總里程為940.3千米，消耗的柴油239.56升，所需燃油費1686.60元，一共花費2086.60元。00123456879圖4-1 節(jié)約算法求解線路結果4.2.3 基于掃描算法的企業(yè)配送路線優(yōu)化對百源木業(yè)周邊的9個縣市采用掃描算法進行配送線路的優(yōu)化。首先建立極坐標系：以百源木業(yè)有限公司所在地婺源縣作為原點，并以點1景德鎮(zhèn)與原點的連線為零角度建立極坐標系，各點

39、的貨運量及極坐標的角坐標值如表7所示。坐標系如圖5所示。表4-6 運量和極坐標的角坐標值客戶1景德鎮(zhèn)2樂平市3鷹潭市4貴溪市5德興市6上饒市7常山縣8開化縣9黃山市貨運量（張/周）18012012060802207090200角坐標03446526110315216923800123456879圖4-2 掃描算法的掃描過程然后分組：從角度為零向逆時針方向進行掃描，如圖所示。第一個被分組的是客戶1，=180；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶2，=180+120=300；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶3，300+120=420；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶4，=420+60=480；繼續(xù)轉(zhuǎn)動，下個被分組

40、的是客戶6，=480+80=560500，由于超過了限制，按分組規(guī)則，需要一個新的組，這樣在第一組里只有客戶1，2，3，4，=480。進行第二組掃描，最先掃描到的是客戶5，=80；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶6，=80+220=300；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶7，=300+70=370；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶8，=370+90=460；繼續(xù)轉(zhuǎn)動，下個被分組的是客戶9，=460+200=660500，超過限制，所以需要一個新的組，這樣在第二組中只有客戶5，6，7，8，=460。在第三組中只剩一個客戶9，故顧客9單獨在一組，=200。這時，可以得到如圖6所示的分組結果。001234568

41、79圖4-3 掃描算法求解結果最后對各子回路內(nèi)的線路優(yōu)化：對上面的3個組，都已經(jīng)是一個單回路運輸問題，對每個組進行線路優(yōu)化。供應點0是任何一個組的TSP問題的起點和終點，用最近插入法分別對三個客戶組進行求解。對第一組進行求解。比較表4-2 中從0出發(fā)的所有路徑大小，這樣，就有顧客點0，1構成一個子回路，。然后考慮剩下顧客點2，3，4到0和1中某一點的最小距離：由于對稱性，無論將2插入到0和1之間往返路徑中，結果都是一樣的，這樣，構成了一個新的子回路。接下來考慮剩下的顧客點3，4到0，1，2中某一點的最小距離顧客點3有3個位置可以插入，現(xiàn)在分析將點3加入到哪里合適。插入到（0，1）之間，。插入到

42、（1，2）之間，。插入到（2，0）之間，。比較可知，插入到（2，0）之間增量最小，所以將顧客點3加入到（2，0）間，結果為重復上面的步驟，將顧客點4加入到子回路中，就可得到一個用最近插入法求得的可行解，總行駛距離為：。對第二組進行求解，可得，總行駛距離為：。對第三組進行求解，可得，總行駛距離為：。最后得到的最優(yōu)結果如表8所示，優(yōu)化線路圖如圖7所示。表4-7掃描算法優(yōu)化結果路線運距運貨量車型司機0-1-2-3-4-0408.5km48011噸貨車20-5-6-7-8-0360.6km46011噸貨車20-9-0165.0km2007噸貨車1由上表可知，公司每周需11噸貨車2車次和7噸貨車1車次配

43、送，司機5人次，所需工資500元，運輸總里程為934.1千米，消耗的柴油242.31升，所需燃油費1713.11元，一共花費2213.11 元。00123456879圖4-4 掃描算法求解線路結果4.2.4 基于改進的最近插入法的企業(yè)配送路線優(yōu)化令T=0,N=0，1，2,10，比較表4-2 中從0出發(fā)的所有路徑大小。因為，所以就有顧客點0，1構成一個子回路，此時，。然后在剩余顧客點（1，2，3，4，6，7，8，9）中尋找到0和5中某一點的最小距離，,因為，所以在子回路插入點1。由于對稱性，無論將1插入到0和5之間往返路徑中，結果都是一樣的，這樣，構成了一個新的子回路，。再次尋找剩余顧客點到0，

44、1， 5中某一點的最小距離：可知最小距離為此時, ，因為，所以在子回路插入點2。將點2分別插入（0，1），（1，5），（5，0）中，比較得：插入到（1，5）中增量最小，。此時構成了一個新的子回路，。再次對剩余的顧客點按照上訴方法進行優(yōu)化，可構成另子回路和子回路利用改進的最近插入法得到優(yōu)化結果如表9所示，優(yōu)化線路結果如圖8所示。表4-8 改進的最近插入法優(yōu)化結果路線運距運貨量車型司機0-1-2-5-0230.1km47011噸貨車10-3-4-6-0438.4km18011噸貨車20-7-8-9-0295.1km49011噸貨車1由上表可知，公司每周需11噸貨車3車次和，司機4人次，所需工資40

45、0元，運輸總里程為963.6千米，消耗的柴油260.17升，所需燃油費1839.42元，一共花費2239.42元。00123456879圖4-5 改進的最近插入法求解線路結果4.3 三種優(yōu)化方案比較分析由上文可知，通過節(jié)約算法，掃描算法和改進后的最近插入法分別對配送線路進行優(yōu)化，可得到三種不同的優(yōu)化方案，因此我們需要通過一系列指標來評價方案的優(yōu)劣性。本文將以所需車輛數(shù)，行駛總里程，總油耗，人力資源和總費用這些指標，對三種優(yōu)化后的方案進行評價分析，如表10所示。表4-9優(yōu)化結果對比表狀態(tài)優(yōu)化前優(yōu)化后節(jié)約算法掃描算法改進后的最近插入法各車型車次(次)7t511011t0223總運輸里程(km)12

46、70.2940.3934.1963.6節(jié)約里程數(shù)（km）329.9336.1306.6油耗（L）266.75239.56242.31260.17節(jié)約油耗（L）27.1924.446.58司機（次）6454節(jié)約人力（次）212總費用（元）2485.872086.602313.112239.42節(jié)約費用（元）399.27172.76246.45從上表的對比中可知，從車次需求數(shù)的角度來看，優(yōu)化后的三種方案需求車次數(shù)相同，但優(yōu)化后的方案與優(yōu)化前方案相比較節(jié)約了2/5的車次需求。優(yōu)化后的方案需要使用更少的車次，減少了百源木業(yè)用車緊張進而租車情況的出現(xiàn)，使百源木業(yè)車輛安排使用上具有更大彈性。因此，在用車角

47、度上考慮，優(yōu)化后的方案均比優(yōu)化前的方案合理，優(yōu)化后的三種方案等價。從總運輸里程角度考慮，優(yōu)化后的三種方案的總運輸里程分別為940.3千米，934.1千米，963.6千米，與原方案的1303.4千米相比較，均減少了車輛行駛的里程數(shù)。優(yōu)化后的方案能減少了公司車輛的損耗和資源的浪費，給百源木業(yè)帶去更多的效益。因此，從運輸里程的角度考慮，優(yōu)化后的方案掃描算法最優(yōu)，節(jié)約算法次之，改進后的最近插入法再次之。從燃油消耗的角度考慮，優(yōu)化后的三種方案的消耗分別為239.56升，242.31升，260.17升，與原方案的266.75升相比較，三種優(yōu)化方案均降低了油耗量，改進后的插入法優(yōu)化后的方案消耗更多的油耗。配

48、送線路優(yōu)化后，不僅能減少百源木業(yè)公司燃油費用的支出，還能降低社會資源的浪費。因此，從燃油消耗的角度上考慮，節(jié)約算法最優(yōu)，掃描算法次之。從公司人力資源消耗角度來考慮，優(yōu)化后的方案所需司機依次為4，5，4人次，減少人力的消耗為2，1，2人次。三種優(yōu)化后的方案均能使公司在人員安排上將更具有彈性，還能降低公司費用的支出。因此，從百源木業(yè)人力資源消耗的角度考慮，節(jié)約算法和改進后的最近插入法最優(yōu)，掃描算法次之。從支出的總費用角度來考慮，優(yōu)化后的方案的費用支出依次2086.60元，2313.11元，2239.42元，與原方案的為2485.87元相比較，改進后的插入法優(yōu)化后的方案花費更多的費用支出。因此，從支

49、出總費用的角度考慮，節(jié)約算法最優(yōu)，改進后的最近插入法次之。結合車次需求數(shù)，總運輸里程，燃油消耗，人力資源消耗，支出的總費用五個角度一齊分析，節(jié)約算法最優(yōu)。但是，本文的配送距離略有超出配送最佳范圍，模型存在著一定的缺陷。在計算過程中也將一些因素理想化了，與實際情況不完全相符。例如，并未考慮具體的道路信息，運輸規(guī)章等。因此，百源木業(yè)應該根據(jù)實際情況合理選擇配送方案。結論百源木業(yè)為了推廣品牌，擴大市場，對小客服實施了進行送貨上門服務。但隨之而來的就是配送成本的問題，公司為保持正常的盈利，降低配送成本則勢在必行，這就意味著公司要對原配送路線進行優(yōu)化。本文針對百源木業(yè)有限公司9個縣市配送狀況進行了線路規(guī)

50、劃，應用了節(jié)約算法、掃描算法及改進的最近插入法三種方法進行了計算分析，經(jīng)過比較3種結果，選擇出了一個最優(yōu)方案，經(jīng)過效益分析，證明經(jīng)過優(yōu)化后的配送里程數(shù)縮短了329.9km，節(jié)約燃油27.17升，從而降低了每天的運輸費用大概375元，除此以外，每周減少發(fā)車次數(shù)2次，司機2人次，輛閑置下來的貨車和司機還可以應對一些緊急情況，提高了公司的服務質(zhì)量。求解車輛路徑問題的方法非常豐富，本文采用了3種方法雖然都能夠得到可行的配送運輸路徑方案，但是只能是可行解而不是精確解。節(jié)約算法，掃描算法和改進后的最近插入法都是解決VRP模型的算法。這類算法雖然能夠比較快的解決有關問題，但其優(yōu)劣往往取決于算法設計者的實際經(jīng)

51、驗以及處理樣本空間的大小。在實際求解過程中，應根據(jù)各類算法的使用范圍，并針對配送優(yōu)化問題的具體情況，尋找最適合的求解方法，找到最優(yōu)配送路路線。對于大部分企業(yè)來說，配送成本最低和滿足客戶對時間的高要求是配送中急需解決的問題，這都需要研究物流配送路徑優(yōu)化模型和算法來解決。從配送中心到客戶位置的物流在配送領域是一個負載的調(diào)度問題。如果能通過比較科學的物流配送路徑優(yōu)化模型和算法，來實現(xiàn)企業(yè)的人工調(diào)度和車輛安排，使得物流中心本身運作效率更高，成本控制得當，企業(yè)的效益也會不斷提升。在物流快速發(fā)展的大背景下，百源木業(yè)有限公司要充分運用物流理論，與實踐相結合，同時考慮到時代賦予產(chǎn)品特殊的意義，積極拓展自己的經(jīng)

52、營方式，與第三方物流公司保持積極地合作，給企業(yè)注入新的血液和活力。致謝語值此拙作完成之際，我首先要衷心地感謝XXX指導老師，他為本人從事這一方向的研究給予了充分的鼓勵和悉心的指導。師從XXX老師，我不僅在學術研究和科研方面得到了諄諄教誨，導師嚴謹細致的治學態(tài)度、寬厚正直的待人之道更是我學之不盡的人生財富。在此，謹向周老師表示最真誠的感謝和崇高的敬意!最后，還要感謝xx大學所有關心和教育過學生的老師們，感謝xx大學圖書館對于論文的幫助，以及百源木業(yè)有限公司提供寶貴的資料。同時，感謝評閱本文的各位專家，敬請?zhí)岢鰧氋F的意見，并予以指正。衷心地感謝在我完成論文的過程中給與幫助和支持的所有老師、同學和朋

53、友！參考文獻1 高曉亮,伊俊敏,甘衛(wèi)華.倉儲與配送管理M.清華大學出版社,2006.2 孔少徹,梁彤錚.商品物流配送優(yōu)化策略探討J.市場論壇,2009(7):94-95. 3 Elliot Rabinovich, Manus Rungtusanatham and Timothy M. Laseter. Physical distribution service performance and Internet retailer margins: The drop-shipping contextJ.Journal of Operations Management,2008(6):767-780

54、.4 蔡臨寧.物流系統(tǒng)規(guī)劃建模實例分析M.北京:機械工業(yè)出版社,2003.孔少徹,梁彤錚.商品物流配送優(yōu)化策略探討J.市場論壇,2009(7):94-95.5 孫焰.現(xiàn)代物流管理技術M.上海:同濟大學出版社,2004.6 Gianpaolo Ghiani. Gilbert Laporte. Roberto Musmanno. Introduction to Logistics Systems Planning and Control M. T&T Productions Ltd, London,2004(1):3-15.7 王鑫.物流配送中車輛優(yōu)化調(diào)度問題的研究與實踐D.沈陽:沈陽航空工業(yè)學院

55、計算機應用技術,2006.8 徐劍,牟燕妮等.物流配送車輛調(diào)度優(yōu)化方法比較研究J.物流科技,2006(2):46-49.9 許星,物流配送路徑優(yōu)化問題的研究D.浙江:浙江大學計算機科學與技術學院計算機應用技術,2006.10 韓世蓮,物流配送線路多目標優(yōu)化方法研究D.江蘇:東南大學載運工具運用工程,2006.11 Henning Rekersbrink, Thomas Makuschewitz, Bernd Scholz-Reiter. A distributed routing concept for vehicle routing problemsJ. Logistics Research

56、,2009,(1):45-52.12 李金蘋.現(xiàn)代物流配送系統(tǒng)的運輸優(yōu)化調(diào)度方案J.物流技術,2002,(5):11-13.附錄資料：不需要的可以自行刪除C語言中如何獲取時間？精度如何？1 使用time_t time( time_t * timer ) 精確到秒2 使用clock_t clock() 得到的是CPU時間精確到1/CLOCKS_PER_SEC秒3 計算時間差使用double difftime( time_t timer1, time_t timer0 )4 使用DWORD GetTickCount() 精確到毫秒5 如果使用MFC的CTime類，可以用CTime:GetCurre

57、ntTime() 精確到秒6 要獲取高精度時間，可以使用BOOL QueryPerformanceFrequency(LARGE_INTEGER *lpFrequency)獲取系統(tǒng)的計數(shù)器的頻率BOOL QueryPerformanceCounter(LARGE_INTEGER *lpPerformanceCount)獲取計數(shù)器的值然后用兩次計數(shù)器的差除以Frequency就得到時間。7 Multimedia Timer FunctionsThe following functions are used with multimedia timers.timeBeginPeriod/timeEn

58、dPeriod/timeGetDevCaps/timeGetSystemTime/*/用標準C實現(xiàn)獲取當前系統(tǒng)時間的函數(shù)一.time()函數(shù)time(&rawtime)函數(shù)獲取當前時間距1970年1月1日的秒數(shù)，以秒計數(shù)單位，存于rawtime 中。#include time.hvoid main ()time_t rawtime;struct tm * timeinfo;time ( &rawtime );timeinfo = localtime ( &rawtime );printf ( 007The current date/time is: %s, asctime (timeinfo)

59、 );exit(0);=#include - 必須的時間函數(shù)頭文件time_t - 時間類型（time.h 定義是typedef long time_t; 追根溯源，time_t是long）struct tm - 時間結構，time.h 定義如下：int tm_sec;int tm_min;int tm_hour;int tm_mday;int tm_mon;int tm_year;int tm_wday;int tm_yday;int tm_isdst;time ( &rawtime ); - 獲取時間，以秒計，從1970年1月一日起算，存于rawtimelocaltime ( &rawti

60、me ); - 轉(zhuǎn)為當?shù)貢r間，tm 時間結構asctime （）- 轉(zhuǎn)為標準ASCII時間格式：星期 月 日 時：分：秒 年二.clock()函數(shù),用clock()函數(shù)，得到系統(tǒng)啟動以后的毫秒級時間，然后除以CLOCKS_PER_SEC，就可以換成“秒”，標準c函數(shù)。clock_t clock ( void );#includeclock_t t = clock();long sec = t / CLOCKS_PER_SEC;他是記錄時鐘周期的，實現(xiàn)看來不會很精確，需要試驗驗證；三.gettime(&t); 據(jù)說tc2.0的time結構含有毫秒信息#include#includeint mai