計(jì)三有,王 星

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

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

1 圖書物流車輛路徑規(guī)劃模型

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

1.1 模型描述及優(yōu)化

為簡(jiǎn)化建模過程,優(yōu)化模型結(jié)構(gòu),特對(duì)物流車輛路徑規(guī)劃模型做如下設(shè)定:1)配送中心的圖書儲(chǔ)備量能滿足所有需求點(diǎn)的需求,不存在缺貨情況;2)車輛順序地為需求點(diǎn)提供配送服務(wù),只有卸貨不帶取貨;3)每個(gè)客戶需求點(diǎn)只被一輛車服務(wù)一次;4)配送車輛由配送中心出發(fā),服務(wù)結(jié)束后返回配送中心;

1.2 車輛路徑規(guī)劃模型

根據(jù)模型描述及相關(guān)假設(shè),基于零擔(dān)運(yùn)輸策略的圖書物流車輛規(guī)劃模型建立如下:

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

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

2 最短距離的改進(jìn)

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

城市交通路況比較復(fù)雜,兩點(diǎn)之間的距離并非是直線距離,而是行車路線中各段路程的代數(shù)和,有的時(shí)候?qū)嶋H距離與直線距離相差非常大.

針對(duì)該問題,本文結(jié)合實(shí)例在計(jì)算任意兩個(gè)客戶點(diǎn)之間的最短距離時(shí)采取通過GPS導(dǎo)航系統(tǒng)取得的路程數(shù)據(jù)為基礎(chǔ),進(jìn)行優(yōu)化計(jì)算.

3 蟻群算法

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

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

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

信息素更新規(guī)則如下式所示:

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

4 配送實(shí)例分析

本配送實(shí)例中,相關(guān)配送點(diǎn)數(shù)據(jù)存入matlab工作空間,在算法優(yōu)化過程中調(diào)用.

根據(jù)模型建立蟻群算法程序,參數(shù)設(shè)置為:螞蟻數(shù)m=15,信息素比重α=1,啟發(fā)信息比重β=4,揮發(fā)系數(shù)ρ=0.1,進(jìn)化次數(shù)n gen=100.用matlab7.0編程求解,程序運(yùn)行結(jié)果如圖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.運(yùn)輸總距離為178.9 km.

經(jīng)統(tǒng)計(jì)計(jì)算,該次配送的實(shí)際運(yùn)輸距離為207.0 km.與之相比,經(jīng)過優(yōu)化的配送路徑能減少13%的配送里程.

圖1 程序運(yùn)行結(jié)果

5 結(jié)論

結(jié)合圖書配送的特點(diǎn),在配送車輛裝載容量有限情況下,建立以配送總里程最短為目標(biāo)的圖書物流配送路徑規(guī)劃模型,開發(fā)了符合模型描述的蟻群算法程序.針對(duì)實(shí)例的仿真研究表明,優(yōu)化結(jié)果能降低配送里程,提高配送效率,減少配送決策時(shí)間.

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

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

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

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

[5]陳 昊,寧紅云.基于集合運(yùn)算的最短路徑搜索算法[J].計(jì)算機(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]王 穎,謝劍英.一種自適應(yīng)蟻群算法及其仿真研究[J].系統(tǒng)仿真學(xué)報(bào),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: