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

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

2、能夠在激烈的競爭市場立足，同時(shí)，也可以給同類企業(yè)乃至行業(yè)提供參考。關(guā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、簡介21.1德邦物流公司概述21.2德邦物流配送線路現(xiàn)狀31.3德邦物流企業(yè)配送過程中存在的問題41.4 配送線路優(yōu)化的意義5第2章 配送線路優(yōu)化的方法綜述72.1節(jié)約算法72.1.1 節(jié)約算法的原理72.1.2 節(jié)約里程算法主要步驟82.2 改進(jìn)后的最近插入法82.3 掃描算法10第3章 德邦物流配送線路優(yōu)化設(shè)計(jì)113.1 線路優(yōu)化基礎(chǔ)數(shù)據(jù)處理113.2 基于節(jié)約算法的企業(yè)配送路線優(yōu)化123.3 基于改進(jìn)的最近插入法的企業(yè)配送路線優(yōu)化163.4 基于掃描算法的企業(yè)配送路線優(yōu)化183.5 三種配送線路優(yōu)化分案比較分析21結(jié)論23致謝語24參考文獻(xiàn)25引言城市物流因其在城市經(jīng)濟(jì)和居民生活中的重要

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

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

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

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

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

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

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

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

16、的產(chǎn)品，一般必須按合理流向的方向運(yùn)輸，如果與合理流向圖指定的方向相反，也屬對流運(yùn)輸。 2. 返程或起程空駛空車無貨載行駛，可以說是不合理運(yùn)輸?shù)淖顕?yán)重形式。在實(shí)際運(yùn)輸組織中，有時(shí)候必須調(diào)運(yùn)空車，從管理上不能將其看成不合理運(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)輸而不辦，卻選擇路程較長路線進(jìn)行運(yùn)輸?shù)囊环N不合理形式。 4. 重復(fù)運(yùn)輸。它是指本來可以直接將貨物運(yùn)到目的地，但是在未達(dá)目的地之處，或目的地之外的其他場所將貨卸下，再重復(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)輸。它指的是指貨物從銷地或中轉(zhuǎn)地向產(chǎn)地或起運(yùn)地回流的一種運(yùn)輸現(xiàn)象。其不合理程度要甚于對流運(yùn)輸，其原因在于，往返兩程的運(yùn)輸都是不必要的，形成了雙程的浪費(fèi)。倒流運(yùn)輸也可以看成是隱蔽對流的一種特殊形式。 6. 過遠(yuǎn)運(yùn)輸過遠(yuǎn)運(yùn)輸是指調(diào)運(yùn)物資舍近求遠(yuǎn)，近處有資源不調(diào)而從遠(yuǎn)處調(diào)，這就造成可采取近程運(yùn)輸而未采取，拉長了貨物運(yùn)距的浪費(fèi)現(xiàn)象。過遠(yuǎn)運(yùn)輸占用運(yùn)力時(shí)間長、運(yùn)輸工具周轉(zhuǎn)慢、物資占壓資金時(shí)間長、遠(yuǎn)距離自然條件相差大。當(dāng)然德邦物流也還存在著：誠信度不高，不夠

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

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

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

21、優(yōu)勢，實(shí)現(xiàn)了企業(yè)物流活動(dòng)的整合，而且思路清晰簡單，便于試行。節(jié)約算法的缺點(diǎn)：過于強(qiáng)調(diào)節(jié)約路程，而沒有考慮行程中的時(shí)間因素。不能對顧客的需求進(jìn)行靈活多變的處理，節(jié)約算法更適合需要需求穩(wěn)定或需求的時(shí)間不緊迫，這顯然不能滿足現(xiàn)代多變的市場環(huán)境。節(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)輸距離。相應(yīng)的變化值，叫做節(jié)約距離，如式（1）所示。 （1）調(diào)整過程如圖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è)初始解。確定各車輛配送點(diǎn)集令, =1,2,n (先采取單點(diǎn)配送)。第二步,進(jìn)行節(jié)約度的計(jì)算。計(jì)算所有點(diǎn)對的節(jié)約度Cij，然后對計(jì)算結(jié)果進(jìn)行升序排列。第三步，進(jìn)行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始，直到節(jié)約里程Cij的隊(duì)列空為止,重復(fù)下列步驟:按照節(jié)約里程Cij隊(duì)列從大到小的順序,分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過2),將i, j連接起來,即可令。如果不是這樣,則從節(jié)約里程隊(duì)列中去除當(dāng)前的節(jié)約里程，分析下一個(gè)客戶對。2.

23、2 改進(jìn)后的最近插入法TSP模型是單回路運(yùn)輸問題的最為典型的一個(gè)模型，它的全稱是Traveling Salesman Problem1，中文叫做旅行商問題。它是一個(gè)典型的NP-Hard問題，對于大規(guī)模的線路優(yōu)化問題，無法獲得最優(yōu)解。最近插入法就是一種解決此問題的啟發(fā)式算法。最近插入法是Rosenkrantz和Stearns等人在1977年提出的一種用于解決TSP(旅行商)問題的算法?；趨⒖键c(diǎn)的插入法對參考點(diǎn)的選擇有很大的依賴性，一個(gè)簡單的改進(jìn)方法是基于多個(gè)隨機(jī)參考點(diǎn)進(jìn)行的多次搜索，進(jìn)而選出性能最好的解，但這顯然勢必會(huì)大大增加搜索量，另外對于大規(guī)模問題參考點(diǎn)的位置的改變對性能的改進(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）代替原來的?。╥，j），并將節(jié)點(diǎn)加入到子回路中。（4）重復(fù)步驟（2）、（3），直到所有的節(jié)點(diǎn)都加入到子回路中。這樣，子回路就演變?yōu)榱艘粋€(gè)TSP的解。由于最近插入法解決的是單回路運(yùn)輸問題，故在此方法基礎(chǔ)上進(jìn)行改進(jìn)和修正，使其能解決多回路運(yùn)輸VRP問題。有改進(jìn)的方法如下：（1）找到最小的節(jié)點(diǎn)，形成一個(gè)子回路（subtour），。（2）在剩下的節(jié)點(diǎn)中

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

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

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

28、邦物流的配送線路現(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）通過各點(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è)配送路線優(yōu)化利用節(jié)約法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配送中心的運(yùn)輸能力和配送中心到各個(gè)用戶

30、以及各個(gè)用戶之間的距離來制定使總的車輛運(yùn)輸?shù)膰嵐飻?shù)最小的配送方案。另還需滿足以下條件；（1）所有用戶的要求；（2）不使任何一輛車超載；（3）每輛車每天的總運(yùn)行時(shí)間或行駛里程不超過規(guī)定的上限；（4）用戶到貨時(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）按從大到小合并路徑對 , , 令, ,，對， 對，不滿足合并條件對， ，對， ，不滿足合并條件對，不滿足合并條件對，不滿足合并條件對，與同

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

33、圖3-2所示0123456879圖3-2 優(yōu)化線路圖3.3 基于改進(jìn)的最近插入法的企業(yè)配送路線優(yōu)化插入法用于求解車輛路線問題的方法，其結(jié)合最鄰近法與節(jié)省法的觀念，依序?qū)㈩櫩忘c(diǎn)插入路徑中以構(gòu)建配送路線。該方法首先將節(jié)省值的觀念應(yīng)用于循序路線建立上，首先以離場站最近的需求點(diǎn)作為路線的種子點(diǎn)，再根據(jù)最鄰近點(diǎn)插入法的概念，以插入值最小者作為下一個(gè)插入點(diǎn)，最后再用一般化節(jié)省值公式，以其中節(jié)省值最大者來決定插入的位置，重復(fù)進(jìn)行選取與插入的步驟，直到超過車輛容量或路程限制時(shí)，再建立另一條路線。插入法的計(jì)算步驟如下： 令T=0,N=0，1，2,9，比較表4-2 中從0出發(fā)的所有路徑大小。因?yàn)椋跃陀蓄櫩忘c(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。由于對稱性，無論將1插入到0和5之間往返路徑中，結(jié)果都是一樣的，這樣，構(gòu)成了一個(gè)新的子回路，。 再次尋找剩余顧客點(diǎn)到0，1， 5中某一點(diǎn)的最小距離：可知最小距離為，此時(shí), ，因?yàn)?，所以在子回路插入點(diǎn)2。 將點(diǎn)2分別插入（0，1），（1，5），（5，0）中，比較得：插入到（1，5）中增量最小，。此時(shí)構(gòu)成了一個(gè)新的子回路，。 再次對剩余的顧客點(diǎn)按照上訴方法進(jìn)行優(yōu)化，可構(gòu)成另子回路和子回路利用改進(jìn)的最近插入法得到優(yōu)化結(jié)果如表3-4所示，優(yōu)化線路結(jié)果如圖3-3所示

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

36、顧客群的排程。關(guān)于掃描算法的企業(yè)配送線路優(yōu)化，我們通過以不同客戶為起始點(diǎn)進(jìn)行掃描計(jì)算分析并比較，我們得到的最優(yōu)方案是以1為起始點(diǎn)的方案，計(jì)算如下圖3-4所示：0123456879圖3-4 優(yōu)化線路圖 建立極坐標(biāo)系，以O(shè)為極坐標(biāo)系的原點(diǎn) 分組。從角度為零向逆時(shí)針方向進(jìn)行掃描，第一個(gè)被分組的是顧客1，Load1=180；繼續(xù)轉(zhuǎn)動(dòng)，下一個(gè)被分組的是顧客2，Load1 =300。由于負(fù)載還沒有超過限制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)的線路優(yōu)化。對上面三個(gè)組都已經(jīng)是一個(gè)單回路運(yùn)輸問題，下面用最近鄰點(diǎn)啟發(fā)式算法進(jìn)行路徑優(yōu)化：由表3-1可知，1、2、5、3之間的最短距離，則先令， ，路線為012350由表3-1可知3、4、5、9之間的距離。則先令， ， 路線為046780由表3-1可知0、9之間的距離。則 路線為090優(yōu)化線路結(jié)果如下表3-6所示。表3-6 改進(jìn)的最近插入法優(yōu)化結(jié)果圖路線運(yùn)距運(yùn)貨量車型

38、司機(jī)0-1-2-3-5-040.24km50011噸貨車10-4-6-7-8-048.33km44011噸貨車10-9-016.5km2007噸貨車1由上表可知，需司機(jī)3人次，運(yùn)輸總里程為105.07km。3.5 三種配送線路優(yōu)化分案比較分析關(guān)于德邦物流的線路優(yōu)化研究，我們用了節(jié)約算法、改進(jìn)后的插入算法、掃描算法三種方法進(jìn)行計(jì)算，我們通過表3-7進(jìn)行了簡單的比較，并選出較為滿意的配送方案。表3-7 3種方案比較分析表狀態(tài)優(yōu)化前優(yōu)化后節(jié)約算法改進(jìn)后的最近插入法掃描算法各車型車次(次)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é)合車次需求數(shù)，總運(yùn)輸里程，人力資源消耗等角度綜合比較分析，本文假設(shè)11噸的車與7噸的車油耗相等，每公里油耗為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元。通過三者的對比我們發(fā)現(xiàn)掃描法優(yōu)化的配送路線方案較為滿意，每月可為廈門德邦物流節(jié)省7576.85元。但是，本文的配送距離略有超出配送最佳范圍，模型存在著一定的缺陷。在計(jì)算過程中也將一些因素理想化了，與實(shí)際情況不完全相符。例如，并未考慮具體的道路信息，運(yùn)輸規(guī)章，車輛的成本及其日常維護(hù)等。結(jié)論在國民生產(chǎn)總值中，流通、物流所占的比例達(dá)到20%，就業(yè)人口的比例約占50%。在我們購買的商品的價(jià)格中，物流費(fèi)用約有10%。從此也可看出物流活動(dòng)對我們生活的重要性。事實(shí)與實(shí)踐已經(jīng)證明，由于物流能夠大幅度降低企業(yè)的總成本，加

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