求解帶有同時取送貨和時間窗的改進遺傳算法

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

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

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

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