從京東的物流配送談車輛路徑選擇問題

#/88該點(diǎn)時(shí)的取貨總量之差;等式（2。6）表示送貨量等于到達(dá)該點(diǎn)時(shí)的送貨總量與離開該點(diǎn)時(shí)的送貨總量之差;約束（2.7）為每條路徑客戶間的容量約束：約朿（2.8）是每輛車的行駛距離約束，L是每輛車的最大行駛距藹;約束（2。9）為決策變量屬性。2.5算例分析實(shí)驗(yàn)1考慮客戶數(shù)目較少的情形。1個(gè)配送中心給8個(gè)客戶同時(shí)送貨和取貨,各客戶的送貨M（id）和取貨量為（ip）（單位:噸）由表2o1給岀。這些客戶由容量為8噸的3車倆完成配送,汽車的行駛速度設(shè)為50km/h,配送中心與各客戶間的距離（單位：公里）由表2.2給出。要求合理安排車輛的行駛路線，使總的路徑最短.表2.1任務(wù)的特征及需求客戶/12345678送貨吊21.54.531.542.53収貨彊31223A1.53表2.2配送中心與各客戶之間的距離><0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150（續(xù)農(nóng)）490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000表2.3 10次實(shí)驗(yàn)的平均計(jì)算結(jié)果使用乍輛數(shù)（輛〉總路徑長度〈km）路徑長度的標(biāo)準(zhǔn)差（km）配?遼5案程序運(yùn)行時(shí)間（秒）379000-3-5-1-0：0-8-4-0：0-6-7-2-0：1.5160設(shè)置差分進(jìn)化算法的種群規(guī)模NP為40,最大交叉概率maxCR為0°9,最小交叉槪率minCR為0o3,每輛車的最大行駛距離L為400,最大迭代次數(shù)為200次，將上述改進(jìn)的差分進(jìn)化算法運(yùn)用MATLAB7.0進(jìn)行編程，使用Pentiuml、3.06GHz微機(jī)運(yùn)行程序，進(jìn)行10次實(shí)驗(yàn)的平均結(jié)果如表2.3,進(jìn)化結(jié)果如圖2.1所示。

11OO1050?Chcin^ooroptimumwxmo

Clggwof vRhie1CCC050900S5O800750204060801OO120Haration11OO1050?Chcin^ooroptimumwxmo

Clggwof vRhie1CCC050900S5O800750204060801OO120Haration140ieo180200圖2.1經(jīng)過200次迭代后的運(yùn)行結(jié)果運(yùn)行200次迭代的程序，10次實(shí)驗(yàn)中，10次得到40條染色體表現(xiàn)為相同的配送方案，100%達(dá)到最優(yōu)結(jié)果，最終結(jié)果為:總的路徑長度為790km.使用3倆車完成配送任務(wù)，英中第一倆車的配送線路為:0-3-5-1-0,離開配送中心時(shí)的實(shí)際裝載量為8噸，實(shí)現(xiàn)滿載，回到配送中心時(shí)的裝載量為8噸，路徑長度為215km.第二輛車的配送線路為:0-6-7-2-0,離開配送中心時(shí)的實(shí)際裝載量為8噸，滿載率為100%,回到配送中心時(shí)的裝載量為6。5噸，路徑長度為305km。第三輛車的配送線路為:0-8-4-0,離開配送中心時(shí)的實(shí)際裝載屋為6噸，滿載率為75%,回到配送中心時(shí)的裝載量為5噸，路徑長度為270km.4小結(jié)隨著綠色物流興起和人們環(huán)保意識(shí)的提高，為了提高售后服務(wù)質(zhì)疑、保護(hù)環(huán)境、降低物流成本，前向物流和逆向物流的整合必然會(huì)變得越來越重要。VRP—SDP有效地整合了前向物流和逆向物流的車輛路徑問題，結(jié)合VRP-SDP的特征提出其整數(shù)規(guī)劃數(shù)學(xué)模型，該模型體現(xiàn)了VRP-SDP與VRP之間的理論聯(lián)系，通過設(shè)置不同的參數(shù)可以將英轉(zhuǎn)化為VRP.在介紹差分進(jìn)化算法基本理論的基礎(chǔ)上，根據(jù)所研究問題的特征,設(shè)計(jì)一種改進(jìn)的差分進(jìn)化算法求解VRP-SDP,這是進(jìn)化算法在車輛路徑問題中的首次應(yīng)用，改進(jìn)的差分進(jìn)化算法采用序數(shù)編碼，變異操作后采用基于整數(shù)序規(guī)劃的輔助算子,有效解決了變異問題，使變異操作后得到的染色體基因均為序數(shù),能直接進(jìn)行剩余的其它差分操作，這是設(shè)計(jì)改進(jìn)差分進(jìn)化算法最核心的部分，若采用苴它的取整方法如：四舍五入，向下取整或者向上取整都不能使染色體的所有基因值為序數(shù)，即不能得到有效合法的染色體。在交叉操作中設(shè)計(jì)交叉率隨進(jìn)化代數(shù)自動(dòng)更新的交叉算子，使算法在進(jìn)化的初始階段，能提髙算法的全局搜索能力,在進(jìn)化的后期，能提髙算法的局部搜索能力。最后的算例分析表明，該算法可以在較短的時(shí)間內(nèi)獲得該問題的最優(yōu)解或滿意解。由2。3肖可知，通常的(經(jīng)典的)車輛路徑問題比同時(shí)送貨和取貨車輛路徑問題簡單，故該改進(jìn)的差分進(jìn)化算法也能求解其它車輛路徑問題。參考文獻(xiàn)：|1］劉波，王凌.金以悲。差分進(jìn)化算法研究進(jìn)展［J］.控制與決策。2007(07)［2］劉云忠，宜慧玉. 乍輛路徑問題的模型及算法研究綜述［J］.管理工程學(xué)報(bào).2005(01)|3］張建勇，李軍。具有同時(shí)配送和回收需求的車輛路徑問題的混合遺傳算法［J］。中國公路學(xué)報(bào).2006(04)［4］方強(qiáng)。 基于優(yōu)進(jìn)策賂的差分進(jìn)化算法及其化匸應(yīng)用［D］<,浙江大學(xué).2004［5］曹二保.物流配送年輛路徑問題模型及算法研尤［D|.湖南大學(xué)。2008|6］瑰瓊杰，袁翊茗.