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

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

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

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

5、;為配送中心頂點(diǎn)；ai 為第i 個(gè)需求點(diǎn)； 為單位距離所花費(fèi)的運(yùn)輸配送費(fèi)用；M 為客戶數(shù)目的集合；dij 為客戶i 到客戶j 之間的距離；ri 為第i 個(gè)客戶的貨物需求箱數(shù)；K 為配送中心的車(chē)輛數(shù)；bk 為第 k 輛配送車(chē)所裝載的箱數(shù)；sij 為客戶i 和客戶j 之間路程的節(jié)約量；ETi 為允許配送車(chē)輛到達(dá)客戶i 的最早時(shí)間；LTi 為允許配送車(chē)輛到達(dá)客戶i 的最晚時(shí)間；Tij 為配送車(chē)

6、輛從客戶i 到客戶j所用行駛時(shí)間；RTi 為配送車(chē)輛到達(dá)客戶i 的時(shí)間；WTi 為配送車(chē)輛離開(kāi)客戶i 的時(shí)間；UT 為配送車(chē)輛途中貨物卸貨時(shí)間； 為違反客戶所規(guī)定的送貨時(shí)間而產(chǎn)生的單位懲罰成本系數(shù)； 為運(yùn)輸盈利的系數(shù)，元/噸/公里.為了滿足客戶i 對(duì)于配送時(shí)間的約束條件，配送車(chē)輛抵達(dá)客戶的時(shí)間RTi 應(yīng)滿足ETiRTiLTi，那么配送車(chē)輛到達(dá)下一個(gè)客戶j 的時(shí)間即為：RTi=WTi+UT+Tij.如果令CTj 為將客戶i 與客戶j 納入同一配送路徑后，配送

7、車(chē)輛到達(dá)客戶j 的時(shí)間變化量，則CTj=RTi+UT+Tij-RTj，其中RTi=Toi.CTj>0為配送車(chē)輛到達(dá)客戶j 的時(shí)間延后，CTj=0 為配送車(chē)輛抵達(dá)客戶j 的時(shí)間沒(méi)有發(fā)生變化，CTj<0 為配送車(chē)輛提前到達(dá)客戶j.為了方便對(duì)問(wèn)題的描述，設(shè)b 為在同一條線路上客戶j 和客戶j 以后的各個(gè)客戶，j-為配送車(chē)輛到達(dá)客戶j 且均不違反客戶j 后面各客戶時(shí)間約束所允許的最大時(shí)間提前量，j-=minRTb-ETb；j+為配送車(chē)輛到達(dá)客戶j 且客戶j 后面各點(diǎn)的時(shí)間

8、都沒(méi)有超過(guò)最大延遲量，j+=minLTb-RTb.j-定義為線路上客戶j 后各點(diǎn)均不需要等待時(shí)，到達(dá)客戶j的時(shí)間提前量，j-j-；定義j+為線路上客戶j后各點(diǎn)均不違反時(shí)間約束的到達(dá)客戶j 的時(shí)間延遲量，j+j+.為了方便模型的建立，將二進(jìn)制變量作如下定義：上述模型的表述如下，式（1）為目標(biāo)函數(shù)，為配送總費(fèi)用最少，其中第一項(xiàng)為運(yùn)輸成本，第二項(xiàng)為懲罰成本；式（2）為保證配送車(chē)輛的數(shù)量不超過(guò)配送車(chē)輛的總數(shù)量；式（3）為保證每個(gè)客戶的商品需求只能由一臺(tái)配送車(chē)輛滿足；式（4）和式（5）為整數(shù)約束；式（6）為如不能按客戶所要求的時(shí)間送貨而引起的單位時(shí)間懲罰成本的系數(shù)；式（7）保證每條配

9、送路徑上各客戶的商品需求總數(shù)不超過(guò)配送車(chē)輛最多能夠容納的數(shù)量；式（8）、式（9）為配送車(chē)輛從配送中心出發(fā)最后仍回到配送中心；式（10）為商品在客戶要求的配送時(shí)間約束內(nèi)到達(dá)；式（11）為配送車(chē)輛是否在客戶要求時(shí)間內(nèi)到達(dá)，如不在取1，否則取0；式（12）為當(dāng)商品沒(méi)能按照客戶時(shí)間送達(dá)時(shí)，懲罰成本小于等于其運(yùn)輸成本7-10.2 求解過(guò)程（1）輸入配送中心和各個(gè)客戶之間的距離 dij；（2）將任意兩個(gè)客戶i 和j 連接在一起，利用ij oi oj ij s = d +d  d ，(i, j

10、60;=1, 2,􀀢,m)計(jì)算節(jié)約值，得S =s(i, j)| s(i, j)>0(i, j =1, 2,􀀢,m) .如果有m 個(gè)客戶，則節(jié)約值的個(gè)數(shù)為2mC ；（3）將集合S 中的元素sij 從大到小進(jìn)行排序；（4）若S =  ，則算法結(jié)束，否則考察集合S中的元素sij 是否滿足以下三個(gè)條件之一，若滿足其中任一條件則轉(zhuǎn)步驟（5），否則轉(zhuǎn)步驟（8）； 客戶i，j 均不在已構(gòu)造的線路上；

11、 客戶i，j 有一個(gè)在已構(gòu)造的線路上，一個(gè)不在已經(jīng)構(gòu)造的線路上，在構(gòu)造線路上的客戶是起點(diǎn)或者終點(diǎn)； 客戶i 和客戶j 在已構(gòu)成的不同線路上，且一個(gè)為自身線路中的第一個(gè)客戶，另一個(gè)為自身線路中的最后一個(gè)客戶.（5）計(jì)算連接客戶i 和j 之后，線路上的貨運(yùn)箱數(shù)rij，若,則轉(zhuǎn)為步驟（6），否則轉(zhuǎn)為步驟（8）；（6）計(jì)算客戶i 和j 之后，車(chē)輛到達(dá)客戶j 的時(shí)間變化量 j i ij j CT = RT +UT + T  R

12、T . 如果 = 0 j CT ，即配送車(chē)輛整點(diǎn)到達(dá)，則轉(zhuǎn)為步驟（7）； 如果 < 0 j CT ，即配送車(chē)輛提前到達(dá)，則計(jì)算提前量j ， j j CT 則轉(zhuǎn)為步驟（7），否則轉(zhuǎn)為步驟（8）； 如果 > 0 j CT ，即配送車(chē)輛延遲到達(dá)，則計(jì)算延遲量j +， j j+ CT 則轉(zhuǎn)為步驟（7），否則轉(zhuǎn)為步驟（8）；（7）將客戶

13、i 和客戶j 連接成一條配送線路；（8）刪除集合S 中的元素，且客戶i 和客戶j不能作為配送車(chē)輛的最初或者最終的線路點(diǎn).繼續(xù)搜索其余各點(diǎn)，將全部的2mC 個(gè)節(jié)約值考察完畢，找到最佳的運(yùn)輸路徑.3 實(shí)例分析3.1 基礎(chǔ)數(shù)據(jù)分析A 為阜新市蔬菜批發(fā)中心，和市內(nèi)14 家大型超市簽訂合約，每天早晨根據(jù)前一日訂單及到貨的時(shí)間要求向各家超市配送貨物，蔬菜批發(fā)中心到各超市以及各超市間距離的具體情況見(jiàn)表1._ 不同超市每天的平均需求量和時(shí)間約束的具體情況見(jiàn)表2.表2 不同門(mén)店每天的平均需求量和時(shí)間約束Tab.2

14、 different stores average demand and timeconstraints of each day門(mén)店要求時(shí)間窗/h 編號(hào) 需求量/(箱·天-1)卸貨時(shí)間UT/hETi LTi1 10 0.40 0.40 1.502 8 0.38 0.20 1.503 5 0.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

15、 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配送車(chē)輛在進(jìn)行配送的過(guò)程中，如果配送車(chē)輛從配送中心到達(dá)某個(gè)超市i 的時(shí)間滿足，即配送車(chē)輛按照客戶要求時(shí)間到達(dá)了門(mén)店，則取，若車(chē)輛提前到達(dá)，則取.如果車(chē)輛在配送過(guò)程中沒(méi)能滿足門(mén)店的時(shí)間約束，則設(shè)定懲罰系數(shù) 為無(wú)限大.配送車(chē)輛的平均行駛速度取值為28 km/h.車(chē)輛在完成配送任務(wù)之后返回配送中心，運(yùn)輸過(guò)程中各路段的情況相同，運(yùn)輸盈利系數(shù) 設(shè)為1 元/噸/公里.車(chē)內(nèi)有效裝載面積最佳可容納公司配送過(guò)程中標(biāo)準(zhǔn)尺寸的包

16、裝箱27 個(gè).3.2 Matlab 軟件求解通過(guò)對(duì)車(chē)輛路徑問(wèn)題模型的建立和改進(jìn)節(jié)約算法分析，本文選用Matlab 軟件進(jìn)行配送線路選擇的優(yōu)化求解.節(jié)約里程表和行駛時(shí)間表見(jiàn)表3 和表4. 將相關(guān)數(shù)據(jù)、參數(shù)及編程語(yǔ)言輸入到Matlab 中進(jìn)行求解，即可求得配送路徑的最優(yōu)解.根據(jù)求解結(jié)果，最終得到的配送方案為配送中心向14 個(gè)超市配送的5 條線路，見(jiàn)表5、圖1，優(yōu)化得到的配送方案的總成本598.3 為元，總行駛距離為119.6 km，總配送時(shí)間約為4.27 h.具體信息如下：（1）0-3-2-9-10

17、-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) 行駛時(shí)間/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 15.9 0.57合計(jì) 119.6 4.27圖1 配送路徑Fig.1 distribu

18、tion route picture3.3 結(jié)果分析A 公司在進(jìn)行配送線路優(yōu)化之前主要依靠司機(jī)的配送經(jīng)驗(yàn)進(jìn)行線路選擇，按照順路或者就近的原則將符合條件歸為同一線路，以配送人員在送貨過(guò)程中經(jīng)常采用的一個(gè)配送線路方案為例，對(duì)優(yōu)化前后的配送方案進(jìn)行比較分析，見(jiàn)表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 information of distribution r

19、oute beforeoptimization路線 配送路線 行駛距離/km 行駛時(shí)間/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合計(jì) 147.0 5.24通過(guò)將以上信息與利用改進(jìn)節(jié)約法求得配送線路方案進(jìn)行比較分析，我們可以發(fā)現(xiàn)，改進(jìn)后的車(chē)輛配送路徑方案能夠有效的節(jié)約配送時(shí)間，縮短總配送里程，降低配送成本，提高公司的經(jīng)濟(jì)效益.4 結(jié)論本文提出了有時(shí)間窗約束的改進(jìn)

20、的節(jié)約法，建立了起訖點(diǎn)相同的單車(chē)場(chǎng)、非滿載、有時(shí)間窗約束的車(chē)輛路徑優(yōu)化問(wèn)題模型，以運(yùn)輸成本最小為優(yōu)化目標(biāo)，提出求解方法，并引入A 公司實(shí)例，通過(guò)計(jì)算，證明該方法具有實(shí)際意義.參考文獻(xiàn)：1 成榕,吳先鋒.最小時(shí)間路徑算法模糊結(jié)構(gòu)元改進(jìn)J.遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(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

21、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.中國(guó)管理信息化, 2010,13(23):41-43.ZHENG Ying,MENG Zhiqing.Based on conservation of tobaccologistics distribution route optimization of the algorithmJ.

22、ChinaManagement 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 

23、陳文佳.節(jié)約里程法在生產(chǎn)企業(yè)物流配送中的應(yīng)用J.經(jīng)管空間,2011(11):66.CHEN Wenjia.Save mileage method in the application of themanufacturing enterprise logistics distributionJ.Business Culture,2011(11):66.5 周延波,光昕.我國(guó)連鎖零售業(yè)物流配送的現(xiàn)狀與對(duì)策分析從沃爾瑪物流配送中心的成功經(jīng)驗(yàn)說(shuō)起J.對(duì)外經(jīng)貿(mào)實(shí)務(wù),2011(9):86-89.ZHOU Yanbo,GUANG Xin. Present situation and counter

24、measures ofChina's chain retail 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ùn)輸優(yōu)化研究D.贛州:江西理工大學(xué),2011.GE Yuxi.The third party logistics based on the CW saving algorithmoptimization researchD.Ganzhou:Jiangxi University of Science andTechnology,2011.7 鄭建輝.第三方配送帶軟時(shí)間窗車(chē)輛路徑問(wèn)題的模型與禁忌算法研究D.杭州:杭州電子科技大學(xué),2013.ZHENG Jianhui. Third party distribution with model of vehicle