求解帶有同時(shí)取送貨和時(shí)間窗的改進(jìn)遺傳算法

1、求解帶有同時(shí)取送貨和時(shí)間窗的改進(jìn)遺傳算法摘要：針對(duì)帶有同時(shí)取送貨需求和時(shí)間窗約束的車(chē)輛路徑問(wèn)題，運(yùn)用改進(jìn)遺傳算法進(jìn)行求解，引入新的交叉算子，增加了種群多樣性；對(duì)變異概率進(jìn)行自適應(yīng)調(diào)整，保留適應(yīng)度較優(yōu)的染色體。以某企業(yè)在天津市的多家社區(qū)連鎖超市為研究對(duì)象，求解出適合該企業(yè)的最優(yōu)路徑。結(jié)果表明：為滿足各超市的時(shí)間窗需求，企業(yè)需改進(jìn)現(xiàn)有配送方案。關(guān)鍵詞：車(chē)輛路徑問(wèn)題同時(shí)取送貨時(shí)間窗改進(jìn)遺傳算法自適應(yīng)調(diào)整中圖分類號(hào)TP301.6文獻(xiàn)標(biāo)識(shí)碼A引言

2、有時(shí)間窗的同時(shí)取送貨的車(chē)輛路徑問(wèn)題（VehicleRoutingProblemofDeliveryPickupwithTimeWindows，VRPDPTW）是VRP的一個(gè)重要擴(kuò)展，對(duì)每一個(gè)客戶點(diǎn)的服務(wù)（取貨和送貨）時(shí)間進(jìn)行了約束[1]。VRPDPTW在現(xiàn)實(shí)中有著廣泛的應(yīng)用。送奶工人送去鮮奶的同時(shí)要取走原先的奶瓶；配送車(chē)輛為超市補(bǔ)充貨源，并取走需要退回的產(chǎn)品或包裝箱等。有時(shí)間窗的同時(shí)取送貨的車(chē)輛路徑問(wèn)題的描述本文VRPDPTW問(wèn)題，涉及

3、一個(gè)配送中心和N個(gè)客戶點(diǎn)，一個(gè)有K輛車(chē)型相同的車(chē)隊(duì)且每個(gè)客戶僅由一輛車(chē)服務(wù)，配送中心是車(chē)輛的始點(diǎn)與終點(diǎn)；配送工作在規(guī)定的時(shí)間窗內(nèi)開(kāi)始；貨物只考慮重量約束，每個(gè)子例?；谒拓浟縿澐殖鲎勇窂剑瑑?yōu)先配送時(shí)間窗下限。（四）算法終止本文采用時(shí)間標(biāo)準(zhǔn)，即當(dāng)進(jìn)化次數(shù)達(dá)到預(yù)先設(shè)定的最大進(jìn)化迭代次數(shù)MAX時(shí)，算法終止。3計(jì)算實(shí)例與結(jié)果分析（一）算法參數(shù)本文對(duì)某公司在天津市內(nèi)6區(qū)的246家社區(qū)連鎖超市進(jìn)行分析。配送中心和超市的坐標(biāo)通過(guò)百度拾取坐標(biāo)系統(tǒng)獲得，

4、測(cè)量比例尺為1：1000000。配送中心與超市之間的距離通過(guò)公式作近似計(jì)算得出。其中N=246，Num=100，MAX=1000，C=30，p=0.6。（二）結(jié)果分析從圖2看出，加入取送貨和時(shí)間窗后，相鄰超市并不是由同一車(chē)輛進(jìn)行配送服務(wù)，這說(shuō)明最佳配送路徑并不是按“服務(wù)臨近區(qū)域”的原則服務(wù)市內(nèi)6區(qū)的超市，所以該公司需要適當(dāng)?shù)馗倪M(jìn)現(xiàn)有配送原則，既可以滿足各超市的時(shí)間需求又可以節(jié)省配送成本。圖2部分超市的配送路徑圖4結(jié)語(yǔ)求解有時(shí)間窗的同時(shí)取