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

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

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

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

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

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

6、路徑后，配送車輛到達(dá)客戶j的時(shí)間變化量，則CTj=RTi+UT+Tij-RTj，其中RTi=Toi.CTj0為配送車輛到達(dá)客戶j的時(shí)間延后，CTj=0為配送車輛抵達(dá)客戶j的時(shí)間沒有發(fā)生變化，CTj0(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)造的線路上；客戶i，j有一個(gè)在已構(gòu)造的線路上，一個(gè)不在已經(jīng)構(gòu)造的線路上，在構(gòu)造線路上的客戶是起點(diǎn)或者終點(diǎn)；客戶i和客戶j在已構(gòu)成的不同線路

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

8、佳的運(yùn)輸路徑.3實(shí)例分析3.1基礎(chǔ)數(shù)據(jù)分析A為阜新市蔬菜批發(fā)中心，和市內(nèi)14家大型超市簽訂合約，每天早晨根據(jù)前一日訂單及到貨的時(shí)間要求向各家超市配送貨物，蔬菜批發(fā)中心到各超市以及各超市間距離的具體情況見表1._不同超市每天的平均需求量和時(shí)間約束的具體情況見表2.表2 不同門店每天的平均需求量和時(shí)間約束Tab.2 different stores average demand and timeconstraints of each day門店要求時(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.

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配送車輛在進(jìn)行配送的過程中，如果配送車輛從配送中心到達(dá)某個(gè)超市i的時(shí)間滿足，即配送車輛按照客戶要求時(shí)間到達(dá)了門店，則取，若車輛提前到達(dá)，則取.如果車輛在配送過程中

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

11、總成本598.3為元，總行駛距離為119.6 km，總配送時(shí)間約為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)行駛時(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

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

13、 information of distribution route 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通過將以上信息與利用改進(jìn)節(jié)約法求得配送線路方案進(jìn)行比較分析，我們可以發(fā)現(xiàn)，改進(jìn)后的車輛配送路徑方案能夠有效的節(jié)約配送時(shí)間，縮短總配送里程，降低配送成本，提高公司的經(jīng)濟(jì)效益.4結(jié)論本文

14、提出了有時(shí)間窗約束的改進(jìn)的節(jié)約法，建立了起訖點(diǎn)相同的單車場(chǎng)、非滿載、有時(shí)間窗約束的車輛路徑優(yōu)化問題模型，以運(yùn)輸成本最小為優(yōu)化目標(biāo)，提出求解方法，并引入A公司實(shí)例，通過計(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

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)狀與對(duì)策分析從沃爾瑪物流配送中心的成功經(jīng)驗(yàn)說起J.對(duì)外經(jīng)貿(mào)實(shí)務(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ùn)輸優(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鄭建輝.第三方配送帶軟時(shí)間窗車輛路徑問題的模型與禁忌算法研究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吳宗彥,王景華,張建軍.基于蟻群算法的智能運(yùn)輸調(diào)度問題的研究J.計(jì)算機(jī)工程與應(yīng)用,2006(35):11-14.WU Zongy