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

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

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

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

5、;為配送中心頂點；ai 為第i 個需求點； 為單位距離所花費的運輸配送費用；M 為客戶數目的集合；dij 為客戶i 到客戶j 之間的距離；ri 為第i 個客戶的貨物需求箱數；K 為配送中心的車輛數；bk 為第 k 輛配送車所裝載的箱數；sij 為客戶i 和客戶j 之間路程的節約量；ETi 為允許配送車輛到達客戶i 的最早時間；LTi 為允許配送車輛到達客戶i 的最晚時間；Tij 為配送車

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

7、車輛到達客戶j 的時間變化量，則CTj=RTi+UT+Tij-RTj，其中RTi=Toi.CTj>0為配送車輛到達客戶j 的時間延后，CTj=0 為配送車輛抵達客戶j 的時間沒有發生變化，CTj<0 為配送車輛提前到達客戶j.為了方便對問題的描述，設b 為在同一條線路上客戶j 和客戶j 以后的各個客戶，j-為配送車輛到達客戶j 且均不違反客戶j 后面各客戶時間約束所允許的最大時間提前量，j-=minRTb-ETb；j+為配送車輛到達客戶j 且客戶j 后面各點的時間

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

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

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

11、 客戶i，j 有一個在已構造的線路上，一個不在已經構造的線路上，在構造線路上的客戶是起點或者終點； 客戶i 和客戶j 在已構成的不同線路上，且一個為自身線路中的第一個客戶，另一個為自身線路中的最后一個客戶.（5）計算連接客戶i 和j 之后，線路上的貨運箱數rij，若,則轉為步驟（6），否則轉為步驟（8）；（6）計算客戶i 和j 之后，車輛到達客戶j 的時間變化量 j i ij j CT = RT +UT + T  R

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

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

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

16、裝箱27 個.3.2 Matlab 軟件求解通過對車輛路徑問題模型的建立和改進節約算法分析，本文選用Matlab 軟件進行配送線路選擇的優化求解.節約里程表和行駛時間表見表3 和表4. 將相關數據、參數及編程語言輸入到Matlab 中進行求解，即可求得配送路徑的最優解.根據求解結果，最終得到的配送方案為配送中心向14 個超市配送的5 條線路，見表5、圖1，優化得到的配送方案的總成本598.3 為元，總行駛距離為119.6 km，總配送時間約為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 優化后配送路線信息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 15.9 0.57合計 119.6 4.27圖1 配送路徑Fig.1 distribu

18、tion route picture3.3 結果分析A 公司在進行配送線路優化之前主要依靠司機的配送經驗進行線路選擇，按照順路或者就近的原則將符合條件歸為同一線路，以配送人員在送貨過程中經常采用的一個配送線路方案為例，對優化前后的配送方案進行比較分析，見表6.優化前常采用的配送線路方案：（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 優化前配送路線信息Tab.6 information of distribution r

19、oute 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通過將以上信息與利用改進節約法求得配送線路方案進行比較分析，我們可以發現，改進后的車輛配送路徑方案能夠有效的節約配送時間，縮短總配送里程，降低配送成本，提高公司的經濟效益.4 結論本文提出了有時間窗約束的改進

20、的節約法，建立了起訖點相同的單車場、非滿載、有時間窗約束的車輛路徑優化問題模型，以運輸成本最小為優化目標，提出求解方法，并引入A 公司實例，通過計算，證明該方法具有實際意義.參考文獻：1 成榕,吳先鋒.最小時間路徑算法模糊結構元改進J.遼寧工程技術大學學報(自然科學版),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 鄭英,孟志青.基于節約算法的煙草物流配送線路優化J.中國管理信息化, 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 的農產品冷鏈配送作業成本核算與優化J.物流技術,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、陳文佳.節約里程法在生產企業物流配送中的應用J.經管空間,2011(11):66.CHEN Wenjia.Save mileage method in the application of themanufacturing enterprise logistics distributionJ.Business Culture,2011(11):66.5 周延波,光昕.我國連鎖零售業物流配送的現狀與對策分析從沃爾瑪物流配送中心的成功經驗說起J.對外經貿實務,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節約算法的第三方物流運輸優化研究D.贛州:江西理工大學,2011.GE Yuxi.The third party logistics based on the CW saving algorithmoptimization researchD.Ganzhou:Jiangxi University of Science andTechnology,2011.7 鄭建輝.第三方配送帶軟時間窗車輛路徑問題的模型與禁忌算法研究D.杭州:杭州電子科技大學,2013.ZHENG Jianhui. Third party distribution with model of vehicle