課程設(shè)計(jì)論文——基于節(jié)約算法的某建材企業(yè)配送路線優(yōu)化

1、物流系統(tǒng)優(yōu)化與設(shè)計(jì)題 目: 基于節(jié)約算法的某建材企業(yè) 配送線路優(yōu)化分析 姓 名: 學(xué) 院: 專 業(yè): 班 級(jí): 學(xué) 號(hào): 2011年 6 月 21 日目 錄摘要2關(guān)鍵詞21背景介紹21.1研究?jī)?nèi)容 21.2研究方法31.3研究目的×××31.4研究意義×××32.案例分析33.優(yōu)化方法 43.1一般VSP模型43.2節(jié)約算法44. 優(yōu)化方案54.1案例數(shù)據(jù)分析 54.2構(gòu)造網(wǎng)絡(luò)圖 64.3配送線路優(yōu)化 75.總結(jié)7參考文獻(xiàn)8圖1 配送中心分布圖5圖2 配送點(diǎn)中心網(wǎng)絡(luò)圖6表 1 配送點(diǎn)和各零售部的關(guān)系6表 2 物資需求量6表 3 點(diǎn)對(duì)間

2、的距離cij6表 4 節(jié)約值表7基于節(jié)約算法的某建材企業(yè)配送路線優(yōu)化 摘要：隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展，作為“第三利潤(rùn)源泉”的物流對(duì)經(jīng)濟(jì)活動(dòng)的影響日益明顯，越來(lái)越引起了人們的重視，成為“當(dāng)前最重要的競(jìng)爭(zhēng)領(lǐng)域”。配送是物流中一個(gè)重要的直接與消費(fèi)者相連的環(huán)節(jié)，物流配送車輛優(yōu)化調(diào)度，是物流配送中關(guān)鍵的一環(huán)，對(duì)企業(yè)節(jié)約成本、增加利潤(rùn)起著重要的作用。本文對(duì)區(qū)域建材配送問(wèn)題進(jìn)行了研究，一某建材企業(yè)為例，利用節(jié)約啟發(fā)式算法，考慮了約束條件，構(gòu)建了數(shù)學(xué)模型，得出該企業(yè)最佳配送路線和車輛的綜合調(diào)度方案。關(guān)鍵詞：區(qū)域建材配送；節(jié)約算法；線路優(yōu)化 1. 背景介紹1.1研究?jī)?nèi)容配送是物流中一個(gè)重要的直接與消費(fèi)者相連的環(huán)節(jié)。配

3、送一般定義為，將貨物從物流結(jié)點(diǎn)送達(dá)收貨人的過(guò)程。主要包括集貨作業(yè)、配貨作業(yè)、車載貨物的配裝、配送線路的確定四個(gè)環(huán)節(jié)。隨著物流配送集約化、一體化的發(fā)展，常將配送的各環(huán)節(jié)綜合起來(lái)，核心部分為配送車輛的集貨、貨物配裝及送貨過(guò)程。進(jìn)行配送系統(tǒng)優(yōu)化，主要就是配送車輛優(yōu)化調(diào)度，包括激活線路優(yōu)化、貨物配裝及送貨線路優(yōu)化，以及集貨、貨物配裝和送貨一體化優(yōu)化。物流配送車輛優(yōu)化調(diào)度，是物流配送優(yōu)化中關(guān)鍵的一環(huán)。對(duì)貨車車輛進(jìn)行優(yōu)化調(diào)度，可以提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化。制定合理的物流配送方案是整個(gè)物流環(huán)節(jié)中最重要的組成部分，也是合理控制物流成本輸出的先決條件。整個(gè)物流配送的環(huán)節(jié)都需要圍繞著全套的物流配送方案進(jìn)行

4、，包括對(duì)物流系統(tǒng)中各子系統(tǒng)，如運(yùn)輸、儲(chǔ)存、配送、裝卸、包裝等各環(huán)節(jié)所組成的物流整體活動(dòng)的規(guī)劃，做到合理的支配其中的各個(gè)環(huán)節(jié)。建材物流是指包含建材的廢棄與還原，連接建材供應(yīng)商（供給主體）與建筑工程（需要主體），克服時(shí)間與空間距離并且創(chuàng)造一部分形質(zhì)效果的物理性經(jīng)濟(jì)活動(dòng)。具體包括：采購(gòu)、運(yùn)輸、保管、裝卸搬運(yùn)、流通加工等活動(dòng)以及有關(guān)的信息活動(dòng)。當(dāng)前國(guó)內(nèi)建筑業(yè)正處于快速繁榮期，奧運(yùn)工程項(xiàng)目的全面建設(shè)和房地產(chǎn)項(xiàng)目投資的巨額增長(zhǎng)，勢(shì)必會(huì)帶動(dòng)一個(gè)新型的行業(yè)建材物流業(yè)的發(fā)展壯大，建材、家裝物流已悄然走進(jìn)我們的生活。建材種類繁多，性質(zhì)各異，因此建材物流有其自身特有的多樣性和復(fù)雜性等特點(diǎn)：供應(yīng)物流占主導(dǎo)、物流流程長(zhǎng)

5、、結(jié)點(diǎn)多、物流量的不穩(wěn)定性、物流服務(wù)場(chǎng)所的變動(dòng)性、物流服務(wù)方式的靈活性等。建筑業(yè)投資巨大，通常是數(shù)億元以上或者百億元以上，一般認(rèn)為，工程建設(shè)項(xiàng)目中材料成本占工程項(xiàng)目造價(jià)的6070，而物流費(fèi)用占材料成本的17左右，也就是說(shuō)，物流費(fèi)用約占工程項(xiàng)目造價(jià)的11左右?？梢?，物流費(fèi)用在建筑業(yè)的造價(jià)中占有很高的比重，而且物流效率的高低還會(huì)影響建材占用資金的數(shù)量和施工效率，建材物流已然成為建筑業(yè)的第三利潤(rùn)源。當(dāng)前學(xué)術(shù)界對(duì)建材物流的關(guān)注程度不高、研究成果不多，因此，有必要對(duì)當(dāng)前國(guó)內(nèi)建材物流現(xiàn)狀和未來(lái)發(fā)展趨勢(shì)進(jìn)行分析和研究。建材物流配送受到高度重視。建材與其他商品的一個(gè)重要不同點(diǎn)是量大、體重、價(jià)值低，物流費(fèi)用在商

6、品成本中占很大比重。降低物流成本是提高競(jìng)爭(zhēng)能力的重要途徑。因此，規(guī)?；I(yè)化、現(xiàn)代化的建材物流配送中心、功能完善的大型建材物流園區(qū)將成為建材物流發(fā)展的主流趨勢(shì)，不僅可以提高物流配送效率和質(zhì)量，還可以減輕城市建材流通壓力。由于經(jīng)濟(jì)發(fā)展帶來(lái)了貨物的急劇增加，消費(fèi)向小批量、多批次、多品種轉(zhuǎn)化，銷售企業(yè)向大型化、綜合化發(fā)展，使得配送數(shù)量迅速增加，同時(shí)建材種類的多樣性，也使得配送工作難度增加。本文就區(qū)域建材配送系統(tǒng)的關(guān)鍵技術(shù)中的車輛調(diào)度問(wèn)題進(jìn)行了研究，關(guān)鍵技術(shù)即是指集貨、配貨及車輛調(diào)度優(yōu)化。其中，重點(diǎn)研究了合理確定配送路線的問(wèn)題，這是整個(gè)配送網(wǎng)絡(luò)優(yōu)化的關(guān)鍵環(huán)節(jié)。合理確定配送路線就是用最少的動(dòng)力，走最短

7、的里程，花最少的費(fèi)用，經(jīng)最少的環(huán)節(jié)，以最快的速度把貨物運(yùn)至用戶手中。合理規(guī)劃配送路線對(duì)配送成本的影響要比一般運(yùn)輸大得多，所以必須在全面計(jì)劃的基礎(chǔ)上，制定高效的運(yùn)輸路線，選擇合理的運(yùn)輸方式和運(yùn)輸工具。建材行業(yè)的配送過(guò)程中，根據(jù)建材的特殊性，充分考慮了貨車裝載量的約束以實(shí)現(xiàn)運(yùn)輸?shù)膬?yōu)化。1.2研究方法在研究過(guò)程中，通過(guò)選取案例企業(yè)的某一配送區(qū)域，就配送系統(tǒng)的優(yōu)化問(wèn)題用數(shù)學(xué)方法進(jìn)行了定量分析和研究，對(duì)各個(gè)配送點(diǎn)的需求進(jìn)行假設(shè)，建立了數(shù)學(xué)模型，通過(guò)分析計(jì)算得出該配送區(qū)域的最優(yōu)配送路線和車輛數(shù)量的需求數(shù)量。1.3研究目的對(duì)案例企業(yè)的物流配送系統(tǒng)進(jìn)行分析，得出優(yōu)化方案，節(jié)約物流成本，從而提高企業(yè)的利潤(rùn)。同時(shí)

8、也是通過(guò)對(duì)案例企業(yè)的研究，進(jìn)一步了解物流配送中車輛優(yōu)化調(diào)度對(duì)節(jié)約企業(yè)成本的重要影響，對(duì)提高勞動(dòng)生產(chǎn)率、提高經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化、促進(jìn)社會(huì)發(fā)展和經(jīng)濟(jì)建設(shè)的重要作用。企業(yè)只有改進(jìn)物流環(huán)節(jié)，重視配送優(yōu)化，才能降低物流成本，減少運(yùn)營(yíng)費(fèi)用，提高配送效率，從而取得優(yōu)勢(shì)。1.4研究意義現(xiàn)代物流作為一種先進(jìn)流通方式管理技術(shù)在世界廣泛范圍內(nèi)得到高度的重視，并在生產(chǎn)、流通、服務(wù)領(lǐng)域得到廣泛應(yīng)用而獲得快速發(fā)展，正在成為改變經(jīng)濟(jì)運(yùn)行方式和企業(yè)發(fā)展模式的重要手段。特別是供應(yīng)鏈物流管理技術(shù)的出現(xiàn)和發(fā)展，更是提升了物流的發(fā)展水平和加快了物流的集成化程度。隨著全球經(jīng)濟(jì)的一體化的發(fā)展，由于集成化物流的理念得到進(jìn)一步的推廣，

9、物流系統(tǒng)比以往任何時(shí)候都要復(fù)雜，技術(shù)的應(yīng)用和管理具有很強(qiáng)的系統(tǒng)性，如何降低各個(gè)環(huán)節(jié)企業(yè)的物流成本，提高物流服務(wù)水平，最大限度地滿足客戶需求，具有積極而現(xiàn)實(shí)的意義。物流系統(tǒng)解決方案中，運(yùn)輸與配送問(wèn)題占有很重要的地位，主要原因是運(yùn)輸和配送過(guò)程的成本占物流總成本的很大比重，根據(jù)現(xiàn)有的研究成果，大約在70%90%之間。解決運(yùn)輸成本的合理化，集中體現(xiàn)在運(yùn)輸過(guò)程的合理組織與安排上，通過(guò)路徑的優(yōu)化來(lái)體現(xiàn)這種對(duì)降低運(yùn)輸成本具有重要作用的管理工具與具體物流活動(dòng)的運(yùn)作，是安排合理運(yùn)輸、解決運(yùn)輸與配送問(wèn)題的重要手段，也是實(shí)現(xiàn)物流管理科學(xué)化和合理化的重要途徑。本文重點(diǎn)通過(guò)節(jié)約啟發(fā)式算法，求解物流配送優(yōu)化路徑的問(wèn)題，通

10、過(guò)理論與實(shí)踐的結(jié)合，尋求降低物流成本與提高物流效率的重要途徑。2. 案例分析該企業(yè)的經(jīng)營(yíng)產(chǎn)品為建筑材料，主要的客戶位于南京市雨花臺(tái)區(qū)的幾大建材裝飾城，主要是金虹市場(chǎng)、長(zhǎng)江裝飾城、西郊物資商場(chǎng)、綠色建材市場(chǎng)等，同時(shí)公司自己設(shè)有下屬的經(jīng)營(yíng)銷售部。所以擬在需求點(diǎn)附近設(shè)置一處配送中心，對(duì)各需求點(diǎn)進(jìn)行建材的配送。由于物流成本在企業(yè)中占很大比重，而配送是企業(yè)物流中的關(guān)鍵環(huán)節(jié)，所以需要對(duì)該區(qū)域的配送線路進(jìn)行優(yōu)化，已得到最短路徑，節(jié)約運(yùn)輸成本，從而降低企業(yè)的運(yùn)營(yíng)成本，提高利潤(rùn)。該配送中心現(xiàn)有解放牌前四后四的倉(cāng)柵式貨車四輛，每輛車的載重量為15噸，每輛車每趟會(huì)產(chǎn)生一定的費(fèi)用，在實(shí)施優(yōu)化的過(guò)程中，要考慮貨車載重量

11、的約束，使得出車費(fèi)用最省。3. 優(yōu)化方法 3.1一般VSP模型為構(gòu)造數(shù)學(xué)模型，將車場(chǎng)編號(hào)為0，任務(wù)編號(hào)為,任務(wù)及車場(chǎng)均以點(diǎn)i來(lái)表示。定義變量如下：1 點(diǎn)i的任務(wù)由車輛k完成；0 否則。1 車輛k從點(diǎn)i行駛到j(luò)點(diǎn)；0 否則。則可得到車輛優(yōu)化調(diào)度數(shù)學(xué)模型如下： 模型中，表示從i點(diǎn)到j(luò)點(diǎn)的運(yùn)輸成本，它的含義可以是距離、費(fèi)用、變量、時(shí)間等，一般根據(jù)實(shí)際情況確定，可同時(shí)考慮車輛數(shù)和運(yùn)行費(fèi)用，如下確定：1) 當(dāng)i為車場(chǎng)時(shí)，包括固定費(fèi)用和運(yùn)行費(fèi)用 2) 當(dāng)i為任務(wù)時(shí)，只有運(yùn)行費(fèi)用，即 其中，為相對(duì)于運(yùn)行時(shí)間的費(fèi)用系數(shù)；為車輛的固定費(fèi)用，即增加一車輛的邊際費(fèi)用。一般認(rèn)為，派出一輛車的固定費(fèi)用遠(yuǎn)遠(yuǎn)高于車輛的行駛

12、費(fèi)用，因此該模型在極小化車輛數(shù)的前提下，再極小化運(yùn)行費(fèi)用。減小的值將會(huì)是使用的車輛數(shù)增多，而線路長(zhǎng)度縮短。若令，則模型目標(biāo)是使用的車輛數(shù)最少。3.2節(jié)約算法節(jié)約 算 法 又稱C-W 算法，是由Clarke和Wright于1964年首次提出的。它的基本思想是首先把各點(diǎn)單獨(dú)與源點(diǎn)0(車場(chǎng))相連，構(gòu)成1條僅含一個(gè)點(diǎn)的線路?？傎M(fèi)用為兩倍的從原點(diǎn)到各點(diǎn)的距離的費(fèi)用 。然后計(jì)算將點(diǎn)i和j連接在一條線路上費(fèi)用的“節(jié)約值”: S(i,j)=c0i+ ci0+ c0j+ cj0-(c0i+ cij+ cj0)= c0i+ c0j-cijS(j,i)=cij+coi-cijS(i,j) 越大，說(shuō)明把i和i連接在一

13、起時(shí)總路程減少越多。構(gòu)造線路時(shí)，根據(jù)S(i,j) 從大到小的順序進(jìn)行，實(shí)現(xiàn)時(shí)可在表上操作，具體步驟如下:Step1: 計(jì)算節(jié)約值S(i,j) ，并按從大到小順序排列成表格形式;Step2:考察表格中最大元素S(i,j) ;Step3:考察S(i,j)對(duì)應(yīng)的點(diǎn)i和點(diǎn)j，檢查是否滿足下列條件: (1)若 點(diǎn) i 和點(diǎn)j均不在己構(gòu)成的線路上，則可連接點(diǎn)i和點(diǎn)j，得到線路段 0->i->j->0，轉(zhuǎn)步驟Step4; (2)若 點(diǎn) i 或點(diǎn)j在已構(gòu)成的線路上，但不是線路的內(nèi)點(diǎn)(即不與源點(diǎn)0直接相連)， 則可以連接，連接后得到線路段0>i->j->0或0->i-&

14、gt;j->0 ，轉(zhuǎn)步驟Step4; (3)若 點(diǎn) i 和點(diǎn)j位于己構(gòu)成的不同線路上，且均不是內(nèi)點(diǎn)，則連接后的得到線路段 0->->i->j->->0，轉(zhuǎn)步驟Step4;(4)若 點(diǎn) i和 點(diǎn)j位于已構(gòu)成的同一條線路上，則不能再進(jìn)行連接，轉(zhuǎn)步驟Step3；Step4:劃去第i行和第j列，即i點(diǎn)不能再到其他點(diǎn)，而j點(diǎn)也不能由其他點(diǎn)到達(dá);Step5:若所有元素均被劃去，則己得到完整線路，算法終止;否則，在沒(méi)被劃去的元素中選擇最大元素，轉(zhuǎn)步驟Step3。4.優(yōu)化方案4.1案例數(shù)據(jù)分析該配送中心共有4輛貨車，為一種類型，最大載重量為15噸。該配送中心在世紀(jì)華聯(lián)超市附

15、近，設(shè)代碼為O，各配送點(diǎn)的代碼及分布如下圖所示：圖1.配送中心分布圖下表給出了各配送點(diǎn)與零售部的關(guān)系：表1.配送點(diǎn)和各零售部的關(guān)系編號(hào)地址需求點(diǎn)A江蘇省南京雨花臺(tái)區(qū)應(yīng)天大街長(zhǎng)江裝飾城南京長(zhǎng)江裝飾城立邦油漆經(jīng)營(yíng)部南京長(zhǎng)江裝飾城東吳木業(yè)銷售部南京長(zhǎng)江裝飾城金鴻泰裝飾材料配套中心B金虹市場(chǎng)南京市金虹市場(chǎng)鑫華昌鋁材經(jīng)營(yíng)部C江蘇省南京雨花臺(tái)區(qū)南京西郊物資商場(chǎng)南京賽虹橋建材商城云峰建材經(jīng)營(yíng)部南京市雨花臺(tái)區(qū)廣龍木業(yè)D南京市西營(yíng)村182號(hào)南京市雨花臺(tái)區(qū)佳樂(lè)門窗材料經(jīng)營(yíng)部E南京市雨花臺(tái)區(qū)西云村3號(hào)南京市雨花臺(tái)區(qū)中陵發(fā)屋F南京市雨花臺(tái)區(qū)應(yīng)天路10號(hào)南京市雨花臺(tái)區(qū)小四汽車租賃服務(wù)部G南京市雨花臺(tái)區(qū)集合村103號(hào)南京

16、市雨花臺(tái)區(qū)忠余線纜銷售部H南京市雨花臺(tái)區(qū)綠色建材市場(chǎng)內(nèi)南京綠色建材市場(chǎng)飛揚(yáng)油漆總匯各配送點(diǎn)的物資需求量如下表所示：表2.物資需求量地點(diǎn)ABCDEFGH需求量（噸)8.0 3.0 5.0 2.52.0 4.52.0 2.54.2構(gòu)造網(wǎng)絡(luò)圖將各配送中心的分布用網(wǎng)絡(luò)圖表示出來(lái)：H1.1圖2.配送點(diǎn)中心網(wǎng)絡(luò)圖用谷歌測(cè)量中配送中心與各配送點(diǎn)、配送點(diǎn)與配送點(diǎn)之間的最短距離，繪制點(diǎn)對(duì)間的距離表：表3.點(diǎn)對(duì)間的距離cijjiOABCDEFGHO1.1 1.1 2.1 1.2 1.1 2.1 0.6 1.5 A1.1 1.2 1.8 2.0 1.9 1.0 1.3 1.0 B1.1 1.2 1.9 2.1 1.

17、7 1.8 2.6 1.9 C2.1 1.8 1.9 1.5 1.7 1.8 2.6 1.9 D1.2 2.0 2.1 1.5 1.4 2.3 2.5 2.0 E1.1 1.9 1.7 1.7 1.4 2.7 1.2 2.0 F2.1 1.0 1.8 1.8 2.3 2.7 1.6 1.8 G0.6 1.3 2.6 2.6 2.5 1.2 1.6 1.6 H1.5 1.0 1.9 1.9 2.0 2.0 1.8 1.6 4.3配送線路優(yōu)化用節(jié)約算法計(jì)算出節(jié)約值，如下表右上部分?jǐn)?shù)據(jù)所示：表4.節(jié)約值表ijOABCDEFGHOA1.1 1.0 1.4 0.3 0.3 3.1 0.4 1.6 B1.

18、1 1.2 0.3 0.2 0.5 0.4 0.3 0.6 C2.1 1.8 1.9 0.8 0.5 1.6 0.1 1.7 D1.2 2.0 2.1 1.5 0.9 1.0 0.0 0.7 E1.1 1.9 1.7 1.7 1.4 0.5 0.5 0.6 F2.1 1.0 1.8 1.8 2.3 2.7 1.1 1.8 G0.6 1.3 2.6 2.6 2.5 1.2 1.6 0.5 H1.5 1.0 1.9 1.9 2.0 2.0 1.8 1.6 1 由表4可知，c(A,F)節(jié)約值最大為3.1，連接A-F點(diǎn)，根據(jù)表2可知，載重量為8+4.5=12.5<最大載重量15，滿足條件，所以A-F可連接，路程為1.0公里；2 C（F,H)節(jié)約值為最大1.8,H點(diǎn)獨(dú)立，F(xiàn)點(diǎn)已連接，但非內(nèi)點(diǎn)，連接A-F-H,載重量為12.5+2.5=15最大載重量15，A-F-H可連接，路程為1.0+1.8=2.8公里；此時(shí)車輛滿載，所以第一條線路為O-A-F-H-O;A/F/H均不可連接，劃去此三行三列；3 繼續(xù)按照節(jié)約算法，可得出第二條線路O-C-D-E-G-B-O,該線路載重量為14.5；4 第一條線路總里程為5.4里，節(jié)約里程4.9公里； 第二