德邦物流線(xiàn)路優(yōu)化講解

1、德邦物流配送線(xiàn)路優(yōu)化研究 摘要 伴隨著國(guó)內(nèi)經(jīng)濟(jì)的快速發(fā)展，作為國(guó)家重點(diǎn)扶持的物流產(chǎn)業(yè)也快速成長(zhǎng)起來(lái)。物流市場(chǎng)在壯大的同時(shí)也面臨著金融危機(jī)來(lái)襲、市場(chǎng)競(jìng)爭(zhēng)日趨激烈等不利因素，這既是我國(guó)物流企業(yè)帶來(lái)機(jī)遇，又是巨大的挑戰(zhàn)。本文用首先簡(jiǎn)短的文字介紹了德邦物流公司的基本情況及在配送線(xiàn)路中存在的問(wèn)題，對(duì)物流配送線(xiàn)路優(yōu)化目標(biāo)和方法進(jìn)行了簡(jiǎn)單概述，然后對(duì)物流配送線(xiàn)路優(yōu)化的方法進(jìn)行了簡(jiǎn)單的概述，最后通過(guò)節(jié)約算法，改進(jìn)后的插入法，掃描法這三種方法對(duì)配送線(xiàn)路進(jìn)行了優(yōu)化，提出物流配送線(xiàn)路優(yōu)化的方案，并且得到了相對(duì)滿(mǎn)意的結(jié)果。優(yōu)化后的配送線(xiàn)路有效提高了德邦物流公司的作業(yè)效率，降低物流成本，從而提升企業(yè)的經(jīng)濟(jì)效益，并讓德邦

2、能夠在激烈的競(jìng)爭(zhēng)市場(chǎng)立足，同時(shí)，也可以給同類(lèi)企業(yè)乃至行業(yè)提供參考。關(guān)鍵詞：德邦物流 配送線(xiàn)路優(yōu)化 節(jié)約里程法25Research on logistics distribution routing optimization DebangAbstract Along with the rapid development of domestic economy, as the national key support of the logistics industry also rapidly grow up. Logistics market in growing at the same tim

3、e is faced with the financial crisis hit, the unfavorable factors such as market competition becomes more intense, it is the opportunity of logistics enterprises in our country, is a huge challenge. Gravels with brief text first introduced the basic situation of the logistics company and the problem

4、s existing in the distribution line, the goal and the methods of logistics distribution route optimization has carried on the simple overview, and then to the logistics distribution route optimization method to carry on the simple summary, finally through the saving algorithm, the improved insert me

5、thod and scanning method of these three methods are optimized for distribution lines, logistics distribution route optimization scheme is put forward, and a relatively satisfactory results are obtained. Optimized distribution lines effectively improve the gravels logistics companys efficiency, reduc

6、e logistics costs, thereby improve enterprise economic benefits, and gravels can in the fierce market competition, at the same time, also can provide a reference for similar enterprises and even the industry.keyword: Debang logistics Distribution route optimization Save mileage method目錄引言1第1章 德邦物流公司

7、簡(jiǎn)介21.1德邦物流公司概述21.2德邦物流配送線(xiàn)路現(xiàn)狀31.3德邦物流企業(yè)配送過(guò)程中存在的問(wèn)題41.4 配送線(xiàn)路優(yōu)化的意義5第2章 配送線(xiàn)路優(yōu)化的方法綜述72.1節(jié)約算法72.1.1 節(jié)約算法的原理72.1.2 節(jié)約里程算法主要步驟82.2 改進(jìn)后的最近插入法82.3 掃描算法10第3章 德邦物流配送線(xiàn)路優(yōu)化設(shè)計(jì)113.1 線(xiàn)路優(yōu)化基礎(chǔ)數(shù)據(jù)處理113.2 基于節(jié)約算法的企業(yè)配送路線(xiàn)優(yōu)化123.3 基于改進(jìn)的最近插入法的企業(yè)配送路線(xiàn)優(yōu)化163.4 基于掃描算法的企業(yè)配送路線(xiàn)優(yōu)化183.5 三種配送線(xiàn)路優(yōu)化分案比較分析21結(jié)論23致謝語(yǔ)24參考文獻(xiàn)25引言城市物流因其在城市經(jīng)濟(jì)和居民生活中的重要

8、作用，越來(lái)越受到廣大學(xué)者的關(guān)注，成為當(dāng)前物流研究的一種重要領(lǐng)域。城市物流配送體系的構(gòu)建主要是以城市道路網(wǎng)為載體，以主要的物資生產(chǎn)地、集散地為依托，通過(guò)構(gòu)建具有合理規(guī)模、優(yōu)良服務(wù)、先進(jìn)技術(shù)的網(wǎng)絡(luò)，為居民生活、城市管理、商業(yè)貿(mào)易等提供高效的、優(yōu)質(zhì)的物流配送服務(wù)，實(shí)現(xiàn)物流配送的快速化、專(zhuān)業(yè)化，配送過(guò)程的的規(guī)?；?、集約化、多樣化。物流產(chǎn)業(yè)作為現(xiàn)代社會(huì)的新興產(chǎn)業(yè)，已經(jīng)成為社會(huì)發(fā)展不可或缺的主要?jiǎng)恿?，而貨物的配送是各個(gè)物流企業(yè)運(yùn)作的重要環(huán)節(jié)，如何優(yōu)化配送線(xiàn)路，為企業(yè)節(jié)約時(shí)間成本和人力物力，更是企業(yè)研究的重中之重，因此本文就德邦物流的配送線(xiàn)路優(yōu)化問(wèn)題進(jìn)行了簡(jiǎn)單的概述和研究，文中以德邦物流公司為例，旨在提高德

9、邦物流公司的作業(yè)效率，降低物流成本，從而提升企業(yè)的經(jīng)濟(jì)效益，并讓德邦能夠在激烈的競(jìng)爭(zhēng)市場(chǎng)立足，同時(shí)，也可以給同類(lèi)企業(yè)乃至行業(yè)提供參考。本論文針對(duì)德邦物流配送線(xiàn)路優(yōu)化進(jìn)行研究，一共分為四部分介紹。第一部分是引言；第二部分是對(duì)德邦物流公司的簡(jiǎn)介，其中介紹了德邦物流公司的概況、德邦物流公司的業(yè)務(wù)簡(jiǎn)介、德邦物流公司配送線(xiàn)路的情況，第三部分是配送線(xiàn)路優(yōu)化的方法綜述；第四部分是對(duì)德邦物流公司配送線(xiàn)路的優(yōu)化方案計(jì)算，包括基于節(jié)約里程法的德邦物流公司廈門(mén)市內(nèi)運(yùn)輸分析、改進(jìn)后插入啟發(fā)式算法和掃描算法的配送優(yōu)化方案計(jì)算，通過(guò)多種方法結(jié)合，來(lái)研究德邦物流公司的配送線(xiàn)路優(yōu)化問(wèn)題，系統(tǒng)通過(guò)系統(tǒng)的定量計(jì)算方法來(lái)探索出德邦

10、物流企業(yè)配送線(xiàn)路的較滿(mǎn)意方案。第1章 德邦物流公司簡(jiǎn)介1.1德邦物流公司概述德邦是國(guó)家“AAAAA”級(jí)物流企業(yè)，主營(yíng)國(guó)內(nèi)公路零擔(dān)運(yùn)輸業(yè)務(wù)，創(chuàng)始于1996年。截止2013年3月，公司已在全國(guó)31個(gè)省級(jí)行政區(qū)開(kāi)設(shè)直營(yíng)網(wǎng)點(diǎn) 2900多家，吸納就業(yè)人員達(dá)27000人，日均貨物流通量達(dá)到三萬(wàn)噸的大型物流企業(yè)。服務(wù)網(wǎng)絡(luò)遍及全國(guó)，自有營(yíng)運(yùn)車(chē)輛5400余臺(tái)，全國(guó)轉(zhuǎn)運(yùn)中心總面積超過(guò)85萬(wàn)平方米。公司始終以客戶(hù)為中心隨時(shí)候命、持續(xù)創(chuàng)新，始終堅(jiān)持自建營(yíng)業(yè)網(wǎng)點(diǎn)、自購(gòu)進(jìn)口車(chē)輛、搭建最優(yōu)線(xiàn)路，優(yōu)化運(yùn)力成本，為客戶(hù)提供快速高效、便捷及時(shí)、安全可靠的服務(wù)體驗(yàn)，助力客戶(hù)創(chuàng)造最大的價(jià)值。公司秉承“承載信任、助力成功”的服務(wù)理念，

11、保持銳意進(jìn)取、注重品質(zhì)的態(tài)度，強(qiáng)化人才戰(zhàn)略，通過(guò)不斷的技術(shù)創(chuàng)新和信息化系統(tǒng)的搭建，提升運(yùn)輸網(wǎng)絡(luò)和標(biāo)準(zhǔn)化 體系，創(chuàng)造最優(yōu)化的運(yùn)載模式，為廣大客戶(hù)提供安全、快速、專(zhuān)業(yè)、滿(mǎn)意的物流服務(wù)。一直以來(lái)，公司都致力于與員工共同發(fā)展和成長(zhǎng)，打造人企雙贏。在推動(dòng)經(jīng)濟(jì) 發(fā)展，提升行業(yè)水平的同時(shí)，努力創(chuàng)造更多的社會(huì)效益，為國(guó)民經(jīng)濟(jì)的持續(xù)發(fā)展，和諧社會(huì)的創(chuàng)建做出積極貢獻(xiàn)，努力將德邦打造成為中國(guó)人首選的國(guó)內(nèi)物流運(yùn)營(yíng)商，實(shí)現(xiàn)“為中國(guó)提速”的使命。目前，德邦物流公司的業(yè)務(wù)主要以汽運(yùn)為主，占到75%以上，空運(yùn)占的比例不足25%，并且近年來(lái)，汽運(yùn)業(yè)務(wù)增長(zhǎng)快速，空運(yùn)業(yè)務(wù)增長(zhǎng)緩慢。為此，德邦物流公司陸續(xù)開(kāi)發(fā)了“精準(zhǔn)卡航、精準(zhǔn)城運(yùn)、

12、精準(zhǔn)汽運(yùn)、精準(zhǔn)空運(yùn)”等品牌產(chǎn)品，此外還有保價(jià)運(yùn)輸、代收客戶(hù)貨款、安全包裝等輔助業(yè)務(wù)，增加企業(yè)利潤(rùn)。面對(duì)國(guó)內(nèi)廣闊的物流市場(chǎng)，德邦物流公司僅僅瞄準(zhǔn)了物流行業(yè)的一小塊區(qū)域零擔(dān)物流，核心的地方定位在30公斤1噸的貨量。因?yàn)椋?0公斤以下的貨物，快遞公司做得更專(zhuān)業(yè)，1噸以上的整車(chē)運(yùn)輸做的更專(zhuān)業(yè)，而德邦是把30公斤1噸這種比較零散的貨物的運(yùn)輸作為企業(yè)的一個(gè)專(zhuān)長(zhǎng)進(jìn)行發(fā)展。明確目標(biāo)，發(fā)揮自己的特點(diǎn)，抓住發(fā)展的機(jī)遇，德邦物流公司才會(huì)發(fā)展如此迅速。 1.2德邦物流配送線(xiàn)路現(xiàn)狀 目前德邦物流公司在全國(guó)30個(gè)省、市、自治區(qū)開(kāi)設(shè)營(yíng)業(yè)網(wǎng)點(diǎn)3000多家，服務(wù)網(wǎng)路遍及國(guó)內(nèi)500多個(gè)城市和地區(qū)，覆蓋全國(guó)90%的經(jīng)濟(jì)中心和人口，

13、但相對(duì)集中在東部沿海發(fā)達(dá)城市，中西部偏遠(yuǎn)山區(qū)因?yàn)榻?jīng)濟(jì)發(fā)展程度相對(duì)落后，貨量較小，架設(shè)網(wǎng)點(diǎn)收益較低。因此，中西部薄弱地區(qū)的網(wǎng)點(diǎn)稀疏，不利于企業(yè)配送貨場(chǎng)的建設(shè)，同時(shí)，開(kāi)往此地的車(chē)輛空載率偏高，造成了浪費(fèi)。本文以德邦物流在廈門(mén)市的配送線(xiàn)路現(xiàn)實(shí)情況進(jìn)行分析。已知廈門(mén)德邦物流公司公司位置為0點(diǎn)，分別向周?chē)幪?hào)為1、2、3、4、5、6、7、8、9共9個(gè)小客戶(hù)點(diǎn)配送汽車(chē)配件，其擁有一輛7噸的車(chē)和兩輛11噸的車(chē)，7噸卡車(chē)最大容量為300個(gè)汽車(chē)配件，11噸卡車(chē)最大載量為500個(gè)。設(shè)各點(diǎn)間的距離為，節(jié)約距離為。各點(diǎn)需求量為，每輛車(chē)的行駛里程為，公里，客戶(hù)點(diǎn)1，2，9。如表1-1表1-1 各點(diǎn)的需求量和配送距離客戶(hù)

14、123456789需求量（個(gè)/日）18012012060802207090200配送距離（km）7.598.9218.6717.035.715.388.78.158.25（資料來(lái)源：廈門(mén)德邦物流信息系統(tǒng)）各配送線(xiàn)路的里程，所需司機(jī)數(shù)量的基本情況如表1-2所示表1-2 配送信息表路線(xiàn)運(yùn)距運(yùn)貨量車(chē)型司機(jī)0-1-2-021.37km3007噸貨車(chē)10-3-4-037.34km1807噸貨車(chē)10-5-6-031.54km3007噸貨車(chē)10-7-8-020.27km1607噸貨車(chē)10-9-016.50km2007噸貨車(chē)1（資料來(lái)源：廈門(mén)德邦物流信息系統(tǒng)）由上表可知，公司每日需7噸貨車(chē)5車(chē)次配送，司機(jī)5人

15、次，運(yùn)輸總里程為127.02千米。1.3德邦物流企業(yè)配送過(guò)程中存在的問(wèn)題 從當(dāng)前我國(guó)物流配送的現(xiàn)狀來(lái)看，廈門(mén)德邦物流公司的業(yè)務(wù)流程的信息化程度還是比較高的，實(shí)現(xiàn)了下游客戶(hù)的電子要貨，企業(yè)內(nèi)部也實(shí)現(xiàn)了信息化管理。但是從供應(yīng)鏈管理的角度來(lái)看，也僅僅是處于物流配送供應(yīng)鏈管理的理論階段，還有很多需要完善的環(huán)節(jié)。我們今天主要來(lái)介紹廈門(mén)德邦物流在配送和配送線(xiàn)路上存在的問(wèn)題。1. 對(duì)流運(yùn)輸。對(duì)流運(yùn)輸亦稱(chēng)相向運(yùn)輸、交錯(cuò)運(yùn)輸，是指同一種貨物，或彼此間可以互相代用而又不影響管理、技術(shù)及效益的貨物，在同一線(xiàn)路上或平行線(xiàn)路上作相對(duì)方向的運(yùn)送，而與對(duì)方運(yùn)程的全部或一部分發(fā)生重迭交錯(cuò)的運(yùn)輸稱(chēng)對(duì)流運(yùn)輸。已經(jīng)制定了合理流向圖

16、的產(chǎn)品，一般必須按合理流向的方向運(yùn)輸，如果與合理流向圖指定的方向相反，也屬對(duì)流運(yùn)輸。 2. 返程或起程空駛空車(chē)無(wú)貨載行駛，可以說(shuō)是不合理運(yùn)輸?shù)淖顕?yán)重形式。在實(shí)際運(yùn)輸組織中，有時(shí)候必須調(diào)運(yùn)空車(chē)，從管理上不能將其看成不合理運(yùn)輸。但是，因調(diào)運(yùn)不當(dāng)，貨源計(jì)劃不周，不采用運(yùn)輸社會(huì)化而形成的空駛，是不合理運(yùn)輸?shù)谋憩F(xiàn)。 3. 迂回運(yùn)輸。迂回運(yùn)輸是舍近取遠(yuǎn)的一種運(yùn)輸?？梢赃x取短距離進(jìn)行運(yùn)輸而不辦，卻選擇路程較長(zhǎng)路線(xiàn)進(jìn)行運(yùn)輸?shù)囊环N不合理形式。 4. 重復(fù)運(yùn)輸。它是指本來(lái)可以直接將貨物運(yùn)到目的地，但是在未達(dá)目的地之處，或目的地之外的其他場(chǎng)所將貨卸下，再重復(fù)裝運(yùn)送達(dá)目的地，這是重復(fù)運(yùn)輸?shù)囊环N形式。另一種形式是，同品

17、種貨物在同一地點(diǎn)一面運(yùn)進(jìn)，同時(shí)又向外運(yùn)出。重復(fù)運(yùn)輸?shù)淖畲竺∈窃黾恿朔潜匾闹虚g環(huán)節(jié)，這就延緩了流通速度，增加了費(fèi)用，增大了貨損。 5. 倒流運(yùn)輸?shù)沽鬟\(yùn)輸。它指的是指貨物從銷(xiāo)地或中轉(zhuǎn)地向產(chǎn)地或起運(yùn)地回流的一種運(yùn)輸現(xiàn)象。其不合理程度要甚于對(duì)流運(yùn)輸，其原因在于，往返兩程的運(yùn)輸都是不必要的，形成了雙程的浪費(fèi)。倒流運(yùn)輸也可以看成是隱蔽對(duì)流的一種特殊形式。 6. 過(guò)遠(yuǎn)運(yùn)輸過(guò)遠(yuǎn)運(yùn)輸是指調(diào)運(yùn)物資舍近求遠(yuǎn)，近處有資源不調(diào)而從遠(yuǎn)處調(diào)，這就造成可采取近程運(yùn)輸而未采取，拉長(zhǎng)了貨物運(yùn)距的浪費(fèi)現(xiàn)象。過(guò)遠(yuǎn)運(yùn)輸占用運(yùn)力時(shí)間長(zhǎng)、運(yùn)輸工具周轉(zhuǎn)慢、物資占?jí)嘿Y金時(shí)間長(zhǎng)、遠(yuǎn)距離自然條件相差大。當(dāng)然德邦物流也還存在著：誠(chéng)信度不高，不夠

18、負(fù)責(zé)；機(jī)械化程度不高；物流工作人員的工作效率低；物流成本過(guò)高的問(wèn)題不作為本文的重點(diǎn)研究對(duì)象。1.4 配送線(xiàn)路優(yōu)化的意義配送運(yùn)輸由于配送方法的不同，其運(yùn)輸過(guò)程也不盡相同，影響配送運(yùn)輸?shù)囊蛩睾芏?，如?chē)流量的變化、道路狀況、客戶(hù)的分布狀況和配送中心的選址、道路交通網(wǎng)、車(chē)輛定額載重量以及車(chē)輛運(yùn)行限制等。配送線(xiàn)路優(yōu)化就是整合影響配送運(yùn)輸?shù)母鞣N因素，適時(shí)適當(dāng)?shù)乩矛F(xiàn)有的運(yùn)輸工具和道路狀況，及時(shí)、安全、方便、經(jīng)濟(jì)地將客戶(hù)所需的商品準(zhǔn)確地送達(dá)客戶(hù)手中。在配送運(yùn)輸線(xiàn)路設(shè)計(jì)中，需根據(jù)不同客戶(hù)群的特點(diǎn)和要求，選擇不同的線(xiàn)路設(shè)計(jì)方法，最終達(dá)到節(jié)省時(shí)間、運(yùn)距和降低配送運(yùn)輸成本的目的。選擇合的理配送路線(xiàn)，對(duì)德邦物流和社會(huì)

19、都具有很重要的意義。配送線(xiàn)路優(yōu)化對(duì)德邦物流來(lái)說(shuō)，(1)優(yōu)化配送路線(xiàn)，可以減少配送時(shí)間和配送里程，提高配送效率，增加車(chē)輛利用率，降低配送成本。(2)可以加快物流速度，能準(zhǔn)時(shí)、快速地把貨物送到客戶(hù)的手中，提高客戶(hù)滿(mǎn)意度。(3)使配送作業(yè)安排合理化，提高企業(yè)作業(yè)效率，有利于德邦物流在同行中的提高競(jìng)爭(zhēng)力與效益。配送線(xiàn)路優(yōu)化對(duì)社會(huì)來(lái)說(shuō)，它可以節(jié)省運(yùn)輸車(chē)輛，減少車(chē)輛空載率，降低了社會(huì)物流成本，對(duì)其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。與此同時(shí)，還能緩解交通緊張狀況，減少噪聲、尾氣排放等運(yùn)輸污染，對(duì)民生和環(huán)境也有不容忽視的作用。第2章 配送線(xiàn)路優(yōu)化的方法綜述通過(guò)查找資料和咨詢(xún)論文指導(dǎo)老師，了解了關(guān)于線(xiàn)路優(yōu)化的方

20、法有以下幾種精確優(yōu)化方法，啟發(fā)式算法，模擬方法，交互優(yōu)化法，吞圈法，插入法，掃描法，當(dāng)然還有一些我不知道的，從以上方法中我采用個(gè)人比較了解和熟悉的方法是節(jié)約里程法、改進(jìn)后的最近插入法和掃描法。我用這三種方法對(duì)德邦物流公司配送系統(tǒng)的優(yōu)化方案進(jìn)行優(yōu)化，其基本原理、優(yōu)缺點(diǎn)。適用范圍、計(jì)算方法如下文介紹。2.1節(jié)約算法2.1.1 節(jié)約算法的原理節(jié)約算法（Saving Algorithm）是用來(lái)解決運(yùn)輸車(chē)輛數(shù)目不確定的VRP問(wèn)題，它是目前用來(lái)解決VRP模型最有名的啟發(fā)式算法。節(jié)約算法的優(yōu)點(diǎn)：是一種簡(jiǎn)便易行的方法，一方面體現(xiàn)出優(yōu)化運(yùn)輸?shù)倪^(guò)程，與一般方法對(duì)比縮短了運(yùn)輸路程；另一方面。它也體現(xiàn)了物流配送網(wǎng)絡(luò)的

21、優(yōu)勢(shì)，實(shí)現(xiàn)了企業(yè)物流活動(dòng)的整合，而且思路清晰簡(jiǎn)單，便于試行。節(jié)約算法的缺點(diǎn)：過(guò)于強(qiáng)調(diào)節(jié)約路程，而沒(méi)有考慮行程中的時(shí)間因素。不能對(duì)顧客的需求進(jìn)行靈活多變的處理，節(jié)約算法更適合需要需求穩(wěn)定或需求的時(shí)間不緊迫，這顯然不能滿(mǎn)足現(xiàn)代多變的市場(chǎng)環(huán)境。節(jié)約算法的核心思想是將運(yùn)輸問(wèn)題中存在的兩個(gè)回路（0， ，i，0）和（0，j， ，0）合并成一個(gè)回路（0， ，i，j，0）。在上面的合并操作中，整個(gè)運(yùn)輸問(wèn)題的總運(yùn)輸距離會(huì)發(fā)生變化，如果變化后總運(yùn)輸距離下降，則稱(chēng)節(jié)約了運(yùn)輸距離。相應(yīng)的變化值，叫做節(jié)約距離，如式（1）所示。 （1）調(diào)整過(guò)程如圖2-1所示。jji 00i 調(diào)整前 調(diào)整后 圖2-1 節(jié)約算法的圖像描述2

22、.1.2 節(jié)約里程算法主要步驟已知條件:需求點(diǎn)集=1,2, n,各點(diǎn)需求量,各點(diǎn)間最短距離。第一步,形成一個(gè)初始解。確定各車(chē)輛配送點(diǎn)集令, =1,2,n (先采取單點(diǎn)配送)。第二步,進(jìn)行節(jié)約度的計(jì)算。計(jì)算所有點(diǎn)對(duì)的節(jié)約度Cij，然后對(duì)計(jì)算結(jié)果進(jìn)行升序排列。第三步，進(jìn)行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開(kāi)始，直到節(jié)約里程Cij的隊(duì)列空為止,重復(fù)下列步驟:按照節(jié)約里程Cij隊(duì)列從大到小的順序,分析客戶(hù)i和j之間合并的可能性(是否滿(mǎn)足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過(guò)2),將i, j連接起來(lái),即可令。如果不是這樣,則從節(jié)約里程隊(duì)列中去除當(dāng)前的節(jié)約里程，分析下一個(gè)客戶(hù)對(duì)。2.

23、2 改進(jìn)后的最近插入法TSP模型是單回路運(yùn)輸問(wèn)題的最為典型的一個(gè)模型，它的全稱(chēng)是Traveling Salesman Problem1，中文叫做旅行商問(wèn)題。它是一個(gè)典型的NP-Hard問(wèn)題，對(duì)于大規(guī)模的線(xiàn)路優(yōu)化問(wèn)題，無(wú)法獲得最優(yōu)解。最近插入法就是一種解決此問(wèn)題的啟發(fā)式算法。最近插入法是Rosenkrantz和Stearns等人在1977年提出的一種用于解決TSP(旅行商)問(wèn)題的算法?；趨⒖键c(diǎn)的插入法對(duì)參考點(diǎn)的選擇有很大的依賴(lài)性，一個(gè)簡(jiǎn)單的改進(jìn)方法是基于多個(gè)隨機(jī)參考點(diǎn)進(jìn)行的多次搜索，進(jìn)而選出性能最好的解，但這顯然勢(shì)必會(huì)大大增加搜索量，另外對(duì)于大規(guī)模問(wèn)題參考點(diǎn)的位置的改變對(duì)性能的改進(jìn)也很有限。最

24、近插入法由四步完成：（1）找到最小的節(jié)點(diǎn)，形成一個(gè)子回路（subtour），。（2）在剩下的節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)。（3) 在子回路中找到一條?。╥，j）,使得+-最小，然后將節(jié)點(diǎn)插入到節(jié)點(diǎn)，之間，用兩條新的弧(i，k)，（k，j）代替原來(lái)的?。╥，j），并將節(jié)點(diǎn)加入到子回路中。（4）重復(fù)步驟（2）、（3），直到所有的節(jié)點(diǎn)都加入到子回路中。這樣，子回路就演變?yōu)榱艘粋€(gè)TSP的解。由于最近插入法解決的是單回路運(yùn)輸問(wèn)題，故在此方法基礎(chǔ)上進(jìn)行改進(jìn)和修正，使其能解決多回路運(yùn)輸VRP問(wèn)題。有改進(jìn)的方法如下：（1）找到最小的節(jié)點(diǎn)，形成一個(gè)子回路（subtour），。（2）在剩下的節(jié)點(diǎn)中

25、，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)。若此時(shí)回路的總貨運(yùn)量未超過(guò)車(chē)的載重限制，則繼續(xù)步驟（3），否則，轉(zhuǎn)（1）尋找新的一條回路。（3）)在子回路中找到一條?。╥，j）,使得+-最小，然后將節(jié)點(diǎn)插入到節(jié)點(diǎn)，之間，用兩條新的弧(i，k)，（k，j）代替原來(lái)的弧（i，j），并將節(jié)點(diǎn)加入到子回路中。若此時(shí)該回路的總路程為未超過(guò)車(chē)輛的行程限制，則繼續(xù)步驟（4），否則轉(zhuǎn)步驟（1），尋找新的一條回路。（4）重復(fù)步驟（2）和（3），直到每一個(gè)節(jié)點(diǎn)都被歸入某一個(gè)子回路中。2.3 掃描算法掃描算法（Sweep Algorithm）是Gillett和Miller在1974年首先提出來(lái)的，它也是用于求解車(chē)輛數(shù)目不限

26、制的CVRP問(wèn)題。掃描法分為先分組后路徑和先路徑后分組兩種，本文采用的是先分組后路徑的方法。掃描法是一種逐次逼近法，該方法不一定能求得物流配送車(chē)輛路勁優(yōu)化問(wèn)題的最優(yōu)解，但是能有效的求得問(wèn)題的滿(mǎn)意解。對(duì)于某個(gè)具體的物流配送車(chē)輛路徑優(yōu)化問(wèn)題，由于存在多種客戶(hù)編號(hào)方法，當(dāng)僅選擇一種客戶(hù)編號(hào)方案用掃描法求解時(shí)，其計(jì)算量相對(duì)較小，但相應(yīng)的解的質(zhì)量可能不會(huì)很高；當(dāng)選用多種客戶(hù)編號(hào)方案用掃描法求解時(shí)，一般能得到質(zhì)量很高的滿(mǎn)意解，但相應(yīng)的計(jì)算量會(huì)成倍增加。研究表明，對(duì)于物流配送車(chē)輛線(xiàn)路優(yōu)化問(wèn)題，當(dāng)每條線(xiàn)路上的客戶(hù)數(shù)目大體相同且配送路線(xiàn)不太多時(shí)，用掃描法求解是非常有效的。掃描算法分四個(gè)步驟完成：（1）以起始點(diǎn)作

27、為極坐標(biāo)系的原點(diǎn)，并以連通圖中的任意一顧客點(diǎn)和原點(diǎn)的連線(xiàn)定義為角度零，建立極坐標(biāo)系。然后對(duì)所有的顧客所在的位置，進(jìn)行坐標(biāo)系的變換，全部都轉(zhuǎn)換為極坐標(biāo)系。（2）分組。從最小角度的顧客開(kāi)始，建立一個(gè)組，按逆時(shí)針?lè)较?，將顧客逐個(gè)加入等到組中，直到顧客的需求總量超出了負(fù)載限制，然后建立一個(gè)新的組，繼續(xù)按逆時(shí)針?lè)较?，將顧客繼續(xù)加入到組中。（3）重復(fù)（2）的過(guò)程，直到所有的顧客都被分類(lèi)為止。（4）路徑優(yōu)化。對(duì)各個(gè)分組內(nèi)的顧客點(diǎn)，就是一個(gè)個(gè)單獨(dú)的TSP模型的線(xiàn)路優(yōu)化問(wèn)題，可以用前面介紹的TSP模型的方法對(duì)結(jié)果進(jìn)行優(yōu)化，選擇一個(gè)合理的線(xiàn)路。第3章 德邦物流配送線(xiàn)路優(yōu)化設(shè)計(jì)3.1 線(xiàn)路優(yōu)化基礎(chǔ)數(shù)據(jù)處理根據(jù)上文德

28、邦物流的配送線(xiàn)路現(xiàn)狀，我們已知n=9,m=3,W1=7,W2=W3=11，L1=L2=L3=60，令W4 =W5 =W6 =W7 =W8 =W9 =7，L4 =L5 =L6 =L7 =L8 =60下圖3-1為德邦物流與顧客分布的連通圖15.383.429.1412.688.1511.578.335.78.257.598.9210.7212.011.6.49.734.8615.470123456879圖3-1 德邦與顧客點(diǎn)分布的連通圖解：（1）通過(guò)各點(diǎn)之間的最短距離計(jì)算,我們得到了個(gè)點(diǎn)間的最短距離,如下表3-1中所示：表3-1 各點(diǎn)間的最短距離表縣市V0V1V2V3V4V5V6V7V8V9V00

29、7.598.9218.0616.425.7015.3811.578.158.25V104.8614.5916.2313.2922.9719.1615.7415.47V209.7311.3714.6223.3820.4917.0717.17V301.6412.3613.6521.9825.2226.31V4010.7212.0120.3423.5824.67V5021.0817.2713.8513.95V608.3311.5720.71V703.4212.68V809.14V903.2 基于節(jié)約算法的企業(yè)配送路線(xiàn)優(yōu)化利用節(jié)約法確定配送路線(xiàn)的主要出發(fā)點(diǎn)是，根據(jù)配送中心的運(yùn)輸能力和配送中心到各個(gè)用戶(hù)

30、以及各個(gè)用戶(hù)之間的距離來(lái)制定使總的車(chē)輛運(yùn)輸?shù)膰嵐飻?shù)最小的配送方案。另還需滿(mǎn)足以下條件；（1）所有用戶(hù)的要求；（2）不使任何一輛車(chē)超載；（3）每輛車(chē)每天的總運(yùn)行時(shí)間或行駛里程不超過(guò)規(guī)定的上限；（4）用戶(hù)到貨時(shí)間要求。節(jié)約里程數(shù)是由公式，i,j=0,1,2,3,4.9計(jì)算得出，計(jì)算結(jié)果如下所示： 0 11.65 11.06 7.78 0 0 0 0 0.37 0 17.25 13.97 0 0.92 0 0 0 0 32.84 11.4 19.79 7.65 0.99 0 0 11.4 19.79 7.65 0.99 0 = 0 0 0 0 0 0 18.62 11.96 2.92 0 16.3

31、 7.14 0 7.26 0（1）將按從小到大的順序排列如下表3-2所示：表3-2 排序表Vi ，VjVi ，VjVi ，Vj3-432.841-211.657-97.143-619.793-511.46-92.924-619.794-511.43-80.996-718.621-311.064-80.992-317.251-47.782-60.927-816.33-77.651-90.372-413.974-77.65 6-811.968-97.26 （2）按從大到小合并路徑對(duì) , , 令, ,，對(duì)， 對(duì)，不滿(mǎn)足合并條件對(duì)， ，對(duì)， ，不滿(mǎn)足合并條件對(duì)，不滿(mǎn)足合并條件對(duì)，不滿(mǎn)足合并條件對(duì)，與同

32、理，不滿(mǎn)足合并條件對(duì)， 對(duì)，不滿(mǎn)足合并條件，同理時(shí)，也不符合滿(mǎn)足條件對(duì)，不滿(mǎn)足合并條件，同理也不滿(mǎn)足合并條件對(duì)，與已經(jīng)在同一個(gè)回路中，同理，與也已經(jīng)在同一條回路中對(duì)，令， 對(duì)， 不符合合并條件，同理，也不符合合并條件對(duì)， 不滿(mǎn)足合并條件最終的配送路徑為，即，即，即，即，最后得到的最優(yōu)結(jié)果如表3-3所示。表3-3 節(jié)約法優(yōu)化結(jié)果表路線(xiàn)運(yùn)距運(yùn)貨量車(chē)型司機(jī)0-3-4-6-7-051.61km47011噸貨車(chē)10-1-2-021.37km3007噸貨車(chē)10-8-9-025.54km2907噸貨車(chē)10-5-011.4km807噸貨車(chē)1由上表可知，需4車(chē)次配送，司機(jī)4人次，運(yùn)輸總里程為109.92km。如

33、圖3-2所示0123456879圖3-2 優(yōu)化線(xiàn)路圖3.3 基于改進(jìn)的最近插入法的企業(yè)配送路線(xiàn)優(yōu)化插入法用于求解車(chē)輛路線(xiàn)問(wèn)題的方法，其結(jié)合最鄰近法與節(jié)省法的觀念，依序?qū)㈩櫩忘c(diǎn)插入路徑中以構(gòu)建配送路線(xiàn)。該方法首先將節(jié)省值的觀念應(yīng)用于循序路線(xiàn)建立上，首先以離場(chǎng)站最近的需求點(diǎn)作為路線(xiàn)的種子點(diǎn)，再根據(jù)最鄰近點(diǎn)插入法的概念，以插入值最小者作為下一個(gè)插入點(diǎn)，最后再用一般化節(jié)省值公式，以其中節(jié)省值最大者來(lái)決定插入的位置，重復(fù)進(jìn)行選取與插入的步驟，直到超過(guò)車(chē)輛容量或路程限制時(shí)，再建立另一條路線(xiàn)。插入法的計(jì)算步驟如下： 令T=0,N=0，1，2,9，比較表4-2 中從0出發(fā)的所有路徑大小。因?yàn)?，所以就有顧客點(diǎn)0

34、，5構(gòu)成一個(gè)子回路，此時(shí)，。 在剩余顧客點(diǎn)（1，2，3，4，6，7，8，9）中尋找到0和5中某一點(diǎn)的最小距離，,因?yàn)?，所以在子回路插入點(diǎn)1。由于對(duì)稱(chēng)性，無(wú)論將1插入到0和5之間往返路徑中，結(jié)果都是一樣的，這樣，構(gòu)成了一個(gè)新的子回路，。 再次尋找剩余顧客點(diǎn)到0，1， 5中某一點(diǎn)的最小距離：可知最小距離為，此時(shí), ，因?yàn)椋栽谧踊芈凡迦朦c(diǎn)2。 將點(diǎn)2分別插入（0，1），（1，5），（5，0）中，比較得：插入到（1，5）中增量最小，。此時(shí)構(gòu)成了一個(gè)新的子回路，。 再次對(duì)剩余的顧客點(diǎn)按照上訴方法進(jìn)行優(yōu)化，可構(gòu)成另子回路和子回路利用改進(jìn)的最近插入法得到優(yōu)化結(jié)果如表3-4所示，優(yōu)化線(xiàn)路結(jié)果如圖3-3所示

35、。表3-4 改進(jìn)的最近插入法優(yōu)化結(jié)果路線(xiàn)運(yùn)距運(yùn)貨量車(chē)型司機(jī)0-1-2-5-032.77km38011噸貨車(chē)10-3-4-6-043.84km470.911噸貨車(chē)10-7-8-9-029.51km323.811噸貨車(chē)1由上表可知，需司機(jī)3人次，運(yùn)輸總里程為106.12km。優(yōu)化以后得線(xiàn)路如圖3-3所示。0123456879圖3-3 優(yōu)化線(xiàn)路圖 3.4 基于掃描算法的企業(yè)配送路線(xiàn)優(yōu)化掃描法分為兩階段性步驟：第一階段：利用極坐標(biāo)來(lái)表示各需求點(diǎn)的區(qū)位，然后任取一需求點(diǎn)為起點(diǎn)，以車(chē)輛容量為分群的約束，再以該需求點(diǎn)為零度按順時(shí)針或逆時(shí)針的方向，進(jìn)行顧客的掃描分群。第二階段：依據(jù)求解旅行商問(wèn)題的算法，求解各

36、顧客群的排程。關(guān)于掃描算法的企業(yè)配送線(xiàn)路優(yōu)化，我們通過(guò)以不同客戶(hù)為起始點(diǎn)進(jìn)行掃描計(jì)算分析并比較，我們得到的最優(yōu)方案是以1為起始點(diǎn)的方案，計(jì)算如下圖3-4所示：0123456879圖3-4 優(yōu)化線(xiàn)路圖 建立極坐標(biāo)系，以O(shè)為極坐標(biāo)系的原點(diǎn) 分組。從角度為零向逆時(shí)針?lè)较蜻M(jìn)行掃描，第一個(gè)被分組的是顧客1，Load1=180；繼續(xù)轉(zhuǎn)動(dòng)，下一個(gè)被分組的是顧客2，Load1 =300。由于負(fù)載還沒(méi)有超過(guò)限制Loadlimit =500，繼續(xù)轉(zhuǎn)動(dòng)。下一個(gè)被分組的是顧客5，Load1 =380，繼續(xù)轉(zhuǎn)動(dòng)；下一個(gè)被分組的是顧客3，Load=500；于是這段路徑已經(jīng)達(dá)到最大限度，需要一個(gè)新的組，這樣在第一個(gè)組里面只

37、有顧客1、2、5、3。在第二組中有顧客4、6、7、8，Load2 =440。繼續(xù)上面的步驟，第三組中有顧客9，Load3 =200，至此所有的顧客都被分配完畢。分組結(jié)果如下圖3-5：0123456879圖3-5 掃描法分組圖 組內(nèi)的線(xiàn)路優(yōu)化。對(duì)上面三個(gè)組都已經(jīng)是一個(gè)單回路運(yùn)輸問(wèn)題，下面用最近鄰點(diǎn)啟發(fā)式算法進(jìn)行路徑優(yōu)化：由表3-1可知，1、2、5、3之間的最短距離，則先令， ，路線(xiàn)為012350由表3-1可知3、4、5、9之間的距離。則先令， ， 路線(xiàn)為046780由表3-1可知0、9之間的距離。則 路線(xiàn)為090優(yōu)化線(xiàn)路結(jié)果如下表3-6所示。表3-6 改進(jìn)的最近插入法優(yōu)化結(jié)果圖路線(xiàn)運(yùn)距運(yùn)貨量車(chē)型

38、司機(jī)0-1-2-3-5-040.24km50011噸貨車(chē)10-4-6-7-8-048.33km44011噸貨車(chē)10-9-016.5km2007噸貨車(chē)1由上表可知，需司機(jī)3人次，運(yùn)輸總里程為105.07km。3.5 三種配送線(xiàn)路優(yōu)化分案比較分析關(guān)于德邦物流的線(xiàn)路優(yōu)化研究，我們用了節(jié)約算法、改進(jìn)后的插入算法、掃描算法三種方法進(jìn)行計(jì)算，我們通過(guò)表3-7進(jìn)行了簡(jiǎn)單的比較，并選出較為滿(mǎn)意的配送方案。表3-7 3種方案比較分析表狀態(tài)優(yōu)化前優(yōu)化后節(jié)約算法改進(jìn)后的最近插入法掃描算法各車(chē)型車(chē)次(次)7t530111t0132總運(yùn)輸里程(km)127.02109.92106.12105.07節(jié)約里程數(shù)（km）17

39、.120.921.95司機(jī)（次）5433節(jié)約人力（次）122根據(jù)上表3-7我們結(jié)合車(chē)次需求數(shù)，總運(yùn)輸里程，人力資源消耗等角度綜合比較分析，本文假設(shè)11噸的車(chē)與7噸的車(chē)油耗相等，每公里油耗為0.12升，司機(jī)的工資為每月為3500元,柴油價(jià)為7.3元每升，,。我們發(fā)現(xiàn)節(jié)約算法的日節(jié)約里程數(shù)為17.1km，可算出每日可節(jié)約14.98元，每月節(jié)約449.39元，節(jié)約算法可少一個(gè)司機(jī)，所以每月總共可節(jié)約3949.39元。改進(jìn)后的插入法節(jié)約里程數(shù)為20.9km，可算出每日節(jié)約18.31元，每月為549.25元，可少2個(gè)司機(jī)，所以每月總共可節(jié)約7549.25元。掃描算法可節(jié)約里程數(shù)為21.95km，可算出每

40、日節(jié)約19.23元，每月為576.85元，可少2個(gè)司機(jī)，所以每月總共可節(jié)約7576.85元。通過(guò)三者的對(duì)比我們發(fā)現(xiàn)掃描法優(yōu)化的配送路線(xiàn)方案較為滿(mǎn)意，每月可為廈門(mén)德邦物流節(jié)省7576.85元。但是，本文的配送距離略有超出配送最佳范圍，模型存在著一定的缺陷。在計(jì)算過(guò)程中也將一些因素理想化了，與實(shí)際情況不完全相符。例如，并未考慮具體的道路信息，運(yùn)輸規(guī)章，車(chē)輛的成本及其日常維護(hù)等。結(jié)論在國(guó)民生產(chǎn)總值中，流通、物流所占的比例達(dá)到20%，就業(yè)人口的比例約占50%。在我們購(gòu)買(mǎi)的商品的價(jià)格中，物流費(fèi)用約有10%。從此也可看出物流活動(dòng)對(duì)我們生活的重要性。事實(shí)與實(shí)踐已經(jīng)證明，由于物流能夠大幅度降低企業(yè)的總成本，加

41、快企業(yè)資金周轉(zhuǎn)，減少庫(kù)存積壓，促進(jìn)利潤(rùn)率上升，從而給企業(yè)帶來(lái)可觀的經(jīng)濟(jì)效益，國(guó)際上普遍把物流稱(chēng)為“降低成本的最后邊界”，排在降低原材料消耗、提高勞動(dòng)生產(chǎn)率之后的“第三利潤(rùn)源泉”，是企業(yè)整體利潤(rùn)的最大源泉。本文通過(guò)對(duì)德邦物流在廈門(mén)市網(wǎng)點(diǎn)進(jìn)行對(duì)調(diào)研和實(shí)地考察，對(duì)德邦物流公司配送系統(tǒng)的現(xiàn)狀進(jìn)行了分析，主要涉及了配送系統(tǒng)中的配送線(xiàn)路和網(wǎng)絡(luò)、車(chē)輛調(diào)度、配送信息系統(tǒng)，以及操作人員等存在的問(wèn)題；最后，采用定性和定量相結(jié)合的研究方法，對(duì)德邦公司的配送線(xiàn)路路規(guī)劃、車(chē)輛調(diào)度、配送信息系統(tǒng)、操作人員等方面提出了優(yōu)化方案，提高企業(yè)運(yùn)作效率，增強(qiáng)了德邦在物流行業(yè)的競(jìng)爭(zhēng)力，為企業(yè)在國(guó)內(nèi)的擴(kuò)張打下堅(jiān)實(shí)的基礎(chǔ)。由于本人知識(shí)有限，所以研究