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

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

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

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章 **有限公司配送運(yùn)作現(xiàn)狀5</p><p>　　2.1 公司簡介5<

8、;/p><p>　　2.2 公司配送現(xiàn)狀5</p><p>　　第3章 物流配送模型及方法描述8</p><p>　　3.1 多回路運(yùn)輸—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改進(jìn)后的最近插入法10</p><p>　　3.4.1 最近插入法10</p><p>　　3.

10、4.2 改進(jìn)的最近插入法11</p><p>　　第4章 **有限公司配送路線優(yōu)化研究12</p><p>　　4.1 建立VRP模型12</p><p>　　4.2**公司的配送線路的分析與優(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 基于改進(jìn)的最近插入法的企業(yè)配送路線優(yōu)化21</p><p>　　4.3 三種優(yōu)化方案比較分析22</p><p><b>　　結(jié)論25</b></p><p><

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、;　　3.2.1節(jié)約算法的基本原理</p><p>　　節(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)輸距離[6]。相應(yīng)的變化值，叫做節(jié)約距離，如式（1）所示。</p><p><b>　?。?）<

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

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

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

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

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

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

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

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

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

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

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

44、p><p>　　4.1 建立VRP模型</p><p>　　多回路運(yùn)輸問題時(shí)現(xiàn)實(shí)生活中十分常見的一種調(diào)配問題。此類調(diào)配問題的核心問題是車輛調(diào)度。因此VRP模型也應(yīng)運(yùn)而生，成了解決多回路問題的一個(gè)相當(dāng)成功的模型。據(jù)此對**有限公司的配送系統(tǒng)建立VRP模型。</p><p>　　基本條件：**公司需給9個(gè)客戶送貨，客戶依次為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元，司機(jī)每天工資100元。</p><p>　　模型目標(biāo)：確定所需要的車輛的數(shù)目N、車輛類型、司機(jī)數(shù)量以及各車行走的路徑，并指派這些車輛到一個(gè)回路中，同時(shí)包括回路內(nèi)的路徑安排和調(diào)度，使得運(yùn)輸總費(fèi)用最小。</p><p><b>　　限制條件：

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

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

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

49、路低得里程，所需司機(jī)數(shù)量及工資的基本情況如表3所示。</p><p>　　表4-2 配送信息表</p><p>　　由上表可知，公司每周需7噸貨車5車次配送，司機(jī)6人次，所需工資600元，運(yùn)輸總里程為1270.2千米，消耗的柴油266.75升，所需燃油費(fèi)1885.87元，一共花費(fèi)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個(gè)客戶

51、點(diǎn)進(jìn)行標(biāo)記，且。</p><p>　　其次，求節(jié)約里程。根據(jù)最短距離表，根據(jù)式（1）計(jì)算出用戶間的節(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兩點(diǎn)，則。</p><p><b>　?。?）對于</b></p><p><b>　　。</b></p><p>　　故合并4，6兩點(diǎn)，則</p>

53、<p>　?。?）對于因?yàn)?與6處在同一回路中，故不滿足合并條件。</p><p>　?。?）對于故不滿足合并條件。</p><p><b>　　（5）對于</b></p><p><b>　　。</b></p><p>　　故合并6，7兩點(diǎn)，則</p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

81、文的過程中給與幫助和支持的所有老師、同學(xué)和朋友！</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 高曉亮,伊俊敏,甘衛(wèi)華.倉儲(chǔ)與配送管理[M].清華大學(xué)出版社,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):76

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

84、ert 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)化調(diào)度問題的研究與實(shí)踐[D].沈陽:沈陽航空工業(yè)學(xué)院計(jì)算機(jī)應(yīng)用技術(shù),2006.</p&

85、gt;<p>　　[8] 徐劍,牟燕妮等.物流配送車輛調(diào)度優(yōu)化方法比較研究[J].物流科技,2006(2):46-49.</p><p>　　[9] 許星,物流配送路徑優(yōu)化問題的研究[D].浙江:浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)應(yīng)用技術(shù),2006.</p><p>　　[10] 韓世蓮,物流配送線路多目標(biāo)優(yōu)化方法研究[D].江蘇:東南大學(xué)載運(yùn)工具運(yùn)用工程,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)代物流