基于蟻群算法的圖書物流中心配送路徑規劃

計三有,王 星

(武漢理工大學物流工程學院,湖北 武漢 430063)

車輛路徑問題(Vehicle Routing Problem,VRP)最早由G.Dantzig和 J.Ramser于1959年提出[1].VRP問題已經被證明是NP-Hard問題,針對它的求解算法主要有精確算法和智能算法兩類.由于精確算法在有限的時間內并不是總能得到合適的解,因此,在實際應用中,智能算法要更有效.本文采用一種新型的智能算法——蟻群算法(Ant Colony Optimization,ACO)進行求解.

1 圖書物流車輛路徑規劃模型

圖書因其商品的特殊性質,客戶的需求一般體現為高頻率、小批量的特點.在這種情況下,單個客戶的需求量通常較小,多個客戶需求量之和才能達到一部車輛的有效裝載容量.若仍采用不同客戶需求分車配送的方式,則大大降低了資源利用率.[2-3]

1.1 模型描述及優化

為簡化建模過程,優化模型結構,特對物流車輛路徑規劃模型做如下設定:1)配送中心的圖書儲備量能滿足所有需求點的需求,不存在缺貨情況;2)車輛順序地為需求點提供配送服務,只有卸貨不帶取貨;3)每個客戶需求點只被一輛車服務一次;4)配送車輛由配送中心出發,服務結束后返回配送中心;

1.2 車輛路徑規劃模型

根據模型描述及相關假設,基于零擔運輸策略的圖書物流車輛規劃模型建立如下:

其中:N為客戶需求點總數;k代表車輛編號,且k∈{1,2,…,K};dij為需求點i與j之間的距離,其中,i≠j且i,j∈{1,2,…,N};qi為客戶點i的需求量;Ck為車輛k的最大裝載量;xijk為判斷系數,且

式(1)為優化目標表達式,使配送路徑的總里程數盡可能小;式(2)、(3)表示每一輛參與配送的車輛都從配送中心出發,并最終回到配送中心;式(4)、(5)表示每個需求點被且僅被一輛車服務一次;式(6)表示容量約束,保證每輛車的實際裝載量都不超過其容量.

2 最短距離的改進

目前在VRP問題的研究中,任意兩個客戶點間的最短距離,通常采用兩點間的直線距離.這樣的簡化與實際路程并不吻合[5].

城市交通路況比較復雜,兩點之間的距離并非是直線距離,而是行車路線中各段路程的代數和,有的時候實際距離與直線距離相差非常大.

針對該問題,本文結合實例在計算任意兩個客戶點之間的最短距離時采取通過GPS導航系統取得的路程數據為基礎,進行優化計算.

3 蟻群算法

蟻群算法最早是由Marco Dorigo于1992年在他的博士論文中提出,是一種模仿螞蟻覓食過程的模擬進化算法[6].

為模擬螞蟻選擇路徑及路徑上信息素的更新過程,定義如下符號:m為螞蟻數量;dij為城市i,j之間的距離;ηij是路段(i,j)的能見度,反映由城市i轉移到城市j的啟發程度,ηij=1/dij;τij為t時刻在ij路徑上信息素的殘留量.則螞蟻從城市i轉移到城市j的概率

式中:α和β為兩個參數,分別表示已積累的信息和啟發信息在螞蟻選擇路徑時的相對重要性.tempk(k=1,2,…,m)是為滿足容量約束的配送點的集合,表示在t時刻螞蟻k可選的待訪問點.

信息素更新規則如下式所示:

其中,ρ是為了避免累積的信息素淹沒啟發信息引入的揮發系數,0<ρ<1;Δ τij(t)表示本次循環中(i,j)路段的信息素增量.[7～8]

4 配送實例分析

本配送實例中,相關配送點數據存入matlab工作空間,在算法優化過程中調用.

根據模型建立蟻群算法程序,參數設置為:螞蟻數m=15,信息素比重α=1,啟發信息比重β=4,揮發系數ρ=0.1,進化次數n gen=100.用matlab7.0編程求解,程序運行結果如圖1所示.

最終線路:線路一,1→22→16→13→17→19→14→1;線路二,1→8→2→3→18→4→9→1;線路三,1→10→5→6→12→7→1;線路四,1※21→20→15→11→1.運輸總距離為178.9 km.

經統計計算,該次配送的實際運輸距離為207.0 km.與之相比,經過優化的配送路徑能減少13%的配送里程.

圖1 程序運行結果

5 結論

結合圖書配送的特點,在配送車輛裝載容量有限情況下,建立以配送總里程最短為目標的圖書物流配送路徑規劃模型,開發了符合模型描述的蟻群算法程序.針對實例的仿真研究表明,優化結果能降低配送里程,提高配送效率,減少配送決策時間.

[1]Dantzig G,Ramser J,The trunk dispatching problem[J],Management Science,1959(6):80-91.

[2]張美娟.圖書物流新發展:圖書物流配送[J].出版發行研究,2000(6):43-44.

[3]胡 勇,郁陽剛.關于圖書物流配送的研究[J].商場現代化,2007(35):108.

[4]龔延成,郭曉汾,尤曉鈴,等.基于遺傳算法的物流配送車輛調度間題研究[J].數學的實踐與認識,2004,34(6):93-97.

[5]陳 昊,寧紅云.基于集合運算的最短路徑搜索算法[J].計算機工程,2007,33(20):199-203.

[6]Colorni A,Dorigo M,M aniezzo V,et al.Distributed optimization by ant colonies[C]//Proceedings of the 1st European Conference on Artificial Life,1991:134-142

[7]王 穎,謝劍英.一種自適應蟻群算法及其仿真研究[J].系統仿真學報,2002,14(1):31-33.

[8]Bell E,MeMullen R.Ant colony optimization techniques for the vehicle routing problem[J].Advanced Engincedng Informaties,2004,18:41-44: