改進節(jié)約法下的物流配送路徑優(yōu)化問題

1、改進節(jié)約法下的物流配送路徑優(yōu)化問題作者：天天論文網(wǎng) 日期：2016-3-16 10:21:38 點擊：3摘 要：為滿足現(xiàn)實生活中一些客戶在物流配送過程中的時間要求，在節(jié)約法的基礎(chǔ)上加入了客戶對時間的約束，提出改進的節(jié)約法，構(gòu)建模型，提出模型假設(shè)和約束條件，列出目標(biāo)函數(shù)，并給出求解過程，以阜新市A蔬菜批發(fā)中心為例進行分析，提出優(yōu)化方案.結(jié)果表明，此種方法能夠在滿足關(guān)于時間約束的情況下有效的節(jié)約配送時間，縮短配送距離，進而節(jié)約成本.這種方法優(yōu)化了之前的路徑優(yōu)化方法，加入了時間約束，更具有現(xiàn)實意義，有助于此類路徑問題的求解.關(guān)鍵詞：車輛路徑問題；節(jié)約法；改進節(jié)約法；時間窗；物流配送0引言節(jié)約法作為一

2、種經(jīng)典的啟發(fā)式算法，在求解小規(guī)模車輛運輸路線優(yōu)化問題上存在一定優(yōu)勢.但在實際生活中，有一些商品如生鮮等需要在一定的時間內(nèi)送到客戶手中，為了滿足客戶實際需求，將商品及時、準(zhǔn)確、高效、經(jīng)濟地將配送到，還要考慮客戶對服務(wù)時間的要求1.所以，不能利用節(jié)約法直接求解配送車輛路徑優(yōu)化問題.因此，為解決此類問題，提出改進的節(jié)約法，不僅考慮配送的總路程還考慮配送的時間約束，即能夠滿足實際問題中客戶對于配送時間的要求.1模型構(gòu)建本文中要解決的配送線路的優(yōu)化問題是典型的起點和終點相同的單車場非滿載有時間窗約束的車輛路徑優(yōu)化問題，即在滿足車輛容量限制、貨物需求量要求、時間限制、運輸里程限制等約束條件的前提下，以某配

3、送中心為據(jù)點，組織合適的行車路線，使配送車輛可以有序的通過一系列的需求量和位置已知的目標(biāo)顧客，并達到一定的目標(biāo).1.1模型假設(shè)及約束條件設(shè)立如下模型假設(shè)2-4：（1）配送中心以及每個客戶的所在地理位置是確定的；（2）已知每個客戶的需求量和時間約束；（3）已知配送車輛規(guī)格；（4）在配送方案中的每一條配送路徑上，每個客戶的需求量總和不能超過配送車的總裝載容量限制；（5）每一客戶所需求商品由一輛配送車進行配送；（6）在配送中心能力范圍內(nèi)安排配送，配送車輛數(shù)目不超過配送中心車輛總數(shù)目；（7）配送車輛需從配送中心出發(fā)，結(jié)束配送后要返回配送中心；（8）滿足客戶是對配送時間的要求.1.2模型描述a0為配送中

4、心頂點，ai為第i個客戶的需求點，其中（i=1,2,M）.配送中心有k輛配送車，每臺車輛的載容量為bk（k=1,2,K），每輛車裝載的商品箱數(shù)不能超過其最大裝載容量.每個客戶的需求量為ri，客戶i到客戶j的運輸距離為dij，配送中心到客戶i的距離為doi，每一段距離的運輸都會產(chǎn)生一定的配送成本，為單位距離的運輸配送費用.要求配送車輛在客戶要求的時段完成配送任務(wù)，目標(biāo)函數(shù)為總成本最小5-6.將模型中的參數(shù)和相關(guān)變量進行如下定義：a0為配送中心頂點；ai為第i個需求點；為單位距離所花費的運輸配送費用；M為客戶數(shù)目的集合；dij為客戶i到客戶j之間的距離；ri為第i個客戶的貨物需求箱數(shù)；K為配送中心

5、的車輛數(shù)；bk為第k輛配送車所裝載的箱數(shù)；sij為客戶i和客戶j之間路程的節(jié)約量；ETi為允許配送車輛到達客戶i的最早時間；LTi為允許配送車輛到達客戶i的最晚時間；Tij為配送車輛從客戶i到客戶j所用行駛時間；RTi為配送車輛到達客戶i的時間；WTi為配送車輛離開客戶i的時間；UT為配送車輛途中貨物卸貨時間；為違反客戶所規(guī)定的送貨時間而產(chǎn)生的單位懲罰成本系數(shù)；為運輸盈利的系數(shù)，元/噸/公里.為了滿足客戶i對于配送時間的約束條件，配送車輛抵達客戶的時間RTi應(yīng)滿足ETiRTiLTi，那么配送車輛到達下一個客戶j的時間即為：RTi=WTi+UT+Tij.如果令CTj為將客戶i與客戶j納入同一配送

6、路徑后，配送車輛到達客戶j的時間變化量，則CTj=RTi+UT+Tij-RTj，其中RTi=Toi.CTj0為配送車輛到達客戶j的時間延后，CTj=0為配送車輛抵達客戶j的時間沒有發(fā)生變化，CTj0(i,j=1, 2,m).如果有m個客戶，則節(jié)約值的個數(shù)為2mC；（3）將集合S中的元素sij從大到小進行排序；（4）若S=，則算法結(jié)束，否則考察集合S中的元素sij是否滿足以下三個條件之一，若滿足其中任一條件則轉(zhuǎn)步驟（5），否則轉(zhuǎn)步驟（8）；客戶i，j均不在已構(gòu)造的線路上；客戶i，j有一個在已構(gòu)造的線路上，一個不在已經(jīng)構(gòu)造的線路上，在構(gòu)造線路上的客戶是起點或者終點；客戶i和客戶j在已構(gòu)成的不同線路

7、上，且一個為自身線路中的第一個客戶，另一個為自身線路中的最后一個客戶.（5）計算連接客戶i和j之后，線路上的貨運箱數(shù)rij，若,則轉(zhuǎn)為步驟（6），否則轉(zhuǎn)為步驟（8）；（6）計算客戶i和j之后，車輛到達客戶j的時間變化量j i ij j CT=RT+UT+TRT.如果=0j CT，即配送車輛整點到達，則轉(zhuǎn)為步驟（7）；如果0j CT，即配送車輛延遲到達，則計算延遲量j+，jj+CT則轉(zhuǎn)為步驟（7），否則轉(zhuǎn)為步驟（8）；（7）將客戶i和客戶j連接成一條配送線路；（8）刪除集合S中的元素，且客戶i和客戶j不能作為配送車輛的最初或者最終的線路點.繼續(xù)搜索其余各點，將全部的2mC個節(jié)約值考察完畢，找到最

8、佳的運輸路徑.3實例分析3.1基礎(chǔ)數(shù)據(jù)分析A為阜新市蔬菜批發(fā)中心，和市內(nèi)14家大型超市簽訂合約，每天早晨根據(jù)前一日訂單及到貨的時間要求向各家超市配送貨物，蔬菜批發(fā)中心到各超市以及各超市間距離的具體情況見表1._不同超市每天的平均需求量和時間約束的具體情況見表2.表2 不同門店每天的平均需求量和時間約束Tab.2 different stores average demand and timeconstraints of each day門店要求時間窗/h編號 需求量/(箱天-1)卸貨時間UT/hETi LTi1 10 0.40 0.40 1.502 8 0.38 0.20 1.503 5 0.

9、35 0.60 3.004 12 0.50 0.20 1.005 7 0.35 0.30 2.506 9 0.40 0.10 5.007 11 0.45 0.45 8.008 10 0.40 0.60 4.009 7 0.35 0.50 8.0010 4 0.30 0.40 5.0011 9 0.50 0.30 5.0012 6 0.50 0.50 6.0013 12 0.55 0.40 2.5014 8 0.60 0.20 1.50配送車輛在進行配送的過程中，如果配送車輛從配送中心到達某個超市i的時間滿足，即配送車輛按照客戶要求時間到達了門店，則取，若車輛提前到達，則取.如果車輛在配送過程中

10、沒能滿足門店的時間約束，則設(shè)定懲罰系數(shù)為無限大.配送車輛的平均行駛速度取值為28 km/h.車輛在完成配送任務(wù)之后返回配送中心，運輸過程中各路段的情況相同，運輸盈利系數(shù)設(shè)為1元/噸/公里.車內(nèi)有效裝載面積最佳可容納公司配送過程中標(biāo)準(zhǔn)尺寸的包裝箱27個.3.2Matlab軟件求解通過對車輛路徑問題模型的建立和改進節(jié)約算法分析，本文選用Matlab軟件進行配送線路選擇的優(yōu)化求解.節(jié)約里程表和行駛時間表見表3和表4.將相關(guān)數(shù)據(jù)、參數(shù)及編程語言輸入到Matlab中進行求解，即可求得配送路徑的最優(yōu)解.根據(jù)求解結(jié)果，最終得到的配送方案為配送中心向14個超市配送的5條線路，見表5、圖1，優(yōu)化得到的配送方案的

11、總成本598.3為元，總行駛距離為119.6 km，總配送時間約為4.27 h.具體信息如下：（1）0-3-2-9-10-0（2）0-14-12-13-0（3）0-8-11-5-0（4）0-1-7-0（5）0-4-6-0表5 優(yōu)化后配送路線信息Tab.5 information of distribution route after optimization路線 配送路線 行駛距離/km)行駛時間/h1 0-3-2-9-10-0 31.9 1.142 0-14-12-13-0 30.1 1.073 0-8-11-5-0 23.3 0.834 0-1-7-0 18.4 0.665 0-4-6-0

12、 15.9 0.57合計119.6 4.27圖1配送路徑Fig.1 distribution route picture3.3結(jié)果分析A公司在進行配送線路優(yōu)化之前主要依靠司機的配送經(jīng)驗進行線路選擇，按照順路或者就近的原則將符合條件歸為同一線路，以配送人員在送貨過程中經(jīng)常采用的一個配送線路方案為例，對優(yōu)化前后的配送方案進行比較分析，見表6.優(yōu)化前常采用的配送線路方案：（1）線路一：0-10-11-12-0；（2）線路二：0-2-9-0；（3）線路三：0-1-5-6-0；（4）線路四：0-4-13-0；（5）線路五：0-14-3-0；（6）線路六：0-8-7-0.表6 優(yōu)化前配送路線信息Tab.6

13、 information of distribution route beforeoptimization路線 配送路線 行駛距離/km行駛時間/h1 0-10-11-12-0 31.0 1.112 0-2-9-0 27.3 0.983 0-1-5-6-0 18.1 0.644 0-4-13-0 24.1 0.865 0-14-3-0 23.3 0.836 0-8-7-0 23.2 0.82合計147.0 5.24通過將以上信息與利用改進節(jié)約法求得配送線路方案進行比較分析，我們可以發(fā)現(xiàn)，改進后的車輛配送路徑方案能夠有效的節(jié)約配送時間，縮短總配送里程，降低配送成本，提高公司的經(jīng)濟效益.4結(jié)論本文

14、提出了有時間窗約束的改進的節(jié)約法，建立了起訖點相同的單車場、非滿載、有時間窗約束的車輛路徑優(yōu)化問題模型，以運輸成本最小為優(yōu)化目標(biāo)，提出求解方法，并引入A公司實例，通過計算，證明該方法具有實際意義.參考文獻：1成榕,吳先鋒.最小時間路徑算法模糊結(jié)構(gòu)元改進J.遼寧工程技術(shù)大學(xué)學(xué)報(自然科學(xué)版),2014,33(5):683-686. doi:10.3969/j.issn.1008-0562.2014.05.023CHENG Rong,WU Xianfeng.Improvement of minimum-time pathalgorithm based on structured element t

15、heoryJ.Journal of LiaoningTechnical University(Natural Science),2014,33(5):683-686. doi:10.3969/j.issn.1008-0562.2014.05.0232鄭英,孟志青.基于節(jié)約算法的煙草物流配送線路優(yōu)化J.中國管理信息化, 2010,13(23):41-43.ZHENG Ying,MENG Zhiqing.Based on conservation of tobaccologistics distribution route optimization of the algorithmJ.ChinaM

16、anagement Informationization,2010,13(23):41-43.3熊燕舞,易海燕.基于TDABC的農(nóng)產(chǎn)品冷鏈配送作業(yè)成本核算與優(yōu)化J.物流技術(shù),2013,32(12):223-226.XIONG Yanwu,YI Haiyan.Cost accouting and optimization ofagricultural produce cold-chain distribution activities based onTDABCJ.Logistics Technology,2013,32(12):223-226.4陳文佳.節(jié)約里程法在生產(chǎn)企業(yè)物流配送中的應(yīng)用J.

17、經(jīng)管空間,2011(11):66.CHEN Wenjia.Save mileage method in the application of themanufacturing enterprise logistics distributionJ.Business Culture,2011(11):66.5周延波,光昕.我國連鎖零售業(yè)物流配送的現(xiàn)狀與對策分析從沃爾瑪物流配送中心的成功經(jīng)驗說起J.對外經(jīng)貿(mào)實務(wù),2011(9):86-89.ZHOU Yanbo,GUANG Xin. Present situation and countermeasures ofChinas chain retail

18、 logistics and distribution analysis,from thesuccessful experience of the wal-mart distribution centerJ.Practicein Foreign Economic Relations and Trade,2011(9):86-89.6葛玉璽.基于CW節(jié)約算法的第三方物流運輸優(yōu)化研究D.贛州:江西理工大學(xué),2011.GE Yuxi.The third party logistics based on the CW saving algorithmoptimization researchD.Gan

19、zhou:Jiangxi University of Science andTechnology,2011.7鄭建輝.第三方配送帶軟時間窗車輛路徑問題的模型與禁忌算法研究D.杭州:杭州電子科技大學(xué),2013.ZHENG Jianhui. Third party distribution with model of vehicle routingproblem with soft time Windows tabu algorithm researchD.Hangzhou:Hangzhou Dianzi University,20138吳宗彥,王景華,張建軍.基于蟻群算法的智能運輸調(diào)度問題的研究J.計算機工程與應(yīng)用,2006(35):11-14.WU Zongy