基于遺傳算法的服裝連鎖業(yè)車輛調度問題研究

[摘 要] 結合服裝業(yè)流行性強，顧客對產品個性化明顯等特點，本文建立車輛調度模型，修改傳統(tǒng)的僅考慮成本因素的決策指標；注重考慮配送服務水平；最后應用遺傳算法求解。

[關鍵詞] 服裝 連鎖經營 車輛調度問題 遺傳算法

一、模型描述和建立

服裝業(yè)行業(yè)特點為：潮流性強，配送服務要求高。中國連鎖經營協會對國內連鎖零售業(yè)調查顯示: 缺貨是該行業(yè)配送的重要癥結。故本文考慮缺貨成本，多品種問題和車輛時間價值建立車輛調度模型，允許對實際配送量決策。研究范圍：單配送中心、單周期、非滿載、多品種、多車型、允許對配送量決策、允許租車、帶軟時間窗的車輛調度問題。連鎖總部配送中心為N個門店配送W種服裝，自有車輛數為nk，能租到車輛數mk， k為車輛型號，車型總數為K，車輛編號為1；門店i對第w種服裝需求量為giw， 對門店i實際決策配送量為riw ；決策變量xijk1為1表示k型號編號為l的車輛從點i行駛到j，否則用0表示；ti表示從點i出發(fā)時間，t0=0表示從配送中心出發(fā)時間，tij表示從點i到點j的行駛時間， si表示對門店i的服務時間。 dij表示從點i到點j的行駛距離；qk表示k型車容量，由于貨物是服裝，故這里選容積，忽略重量影響；cw表示每單位第w種貨物占用的容積；Vk表示k型車單位距離行駛成本；φw表示第w種貨物的單位配送量成本；Fk表示自有的k型車出車固定成本; Ek示租用的k型車出車固定成本；[ei，li]表示點i的時間窗，其中[e0，10]=[0，∞];ai表示對配送點i配送時提前到達的單位時間成本bi表示對配送點i配送時單位遲到時間成本；αk表示k型車單位行駛時間的成本；βw表示第w種貨物每一單位的缺貨成本；Ri表示是否對配送點進行服務，為1表示配送，否則為0；pk1表示k型，編號為1的車是否參加配送，為1表示參加，否則為0。模型表達式：

二、遺傳算法求解

據文獻[1]采用基于客戶的編碼方式以適應不確定車輛數要求。 采用傳統(tǒng)適應函數易造成適應度選擇集中或分散，本文[2]中以目標函數值作為適應度，并配以隨機聯賽選擇策略可以規(guī)避此問題。本文采取最佳保留策略結合隨機聯賽選擇策略作為選擇策略，采用常見的兩點交叉和擴展的單點變異：區(qū)別在變異時按照初始化中重新對染色體賦值方法進行賦值。由于所得解均為只有車輛容量約束不滿足的半可行解，故采用懲罰法調整適應值。算例如下：設配送點數為8，車輛類型為2，每型號3輛車，其中1型3號，2型3號為可租車輛，貨種為2，1型車容量為15，2型車容量為20。總目標中各成本系數為：出車固定成本系數，自有車輛為{100，120}，租用車輛為{180，200}；距離成本系數為{0.5，0.7}；時間成本系數為{10，15}；配送量成本系數為{2，4}；早到懲罰成本系數為{40，30，25，20，30，35，10，20}；遲到懲罰成本系數為{100，120，160，130，100，95，120，140}；缺貨成本系數為{80，100}；超載懲罰系數為4000。將文獻中數據進行調整加入如下配送點的品種需求：

由實驗得本問題取種群規(guī)模100，交叉率為0.8，變異率為0.15，迭代500代為宜。進行獨立實驗50次得滿意解：目標函數值為1039，對應的配送方案為出車3輛，1型1號車配送路線0～8～2～7～0，1型2號車配送路線0～6～4～0，2型2號車配送路線0～3～1～5～0。

參考文獻:

[1]鄒 彤:不確定車輛數有時間窗車輛路徑問題的遺傳算法[J].系統(tǒng)工程理論與實踐，2004.6(6):134～138

[2]占書芳:并行遺傳算法在帶軟時間窗車輛路徑問題中的研究[D].武漢理工大學，2005