賈春梅

摘要:車輛路徑問題中,行駛路線往往取決于一系列約束條件,如配送中心個(gè)數(shù),貨物需求量,交發(fā)貨時(shí)間,車輛容量限制等。要想達(dá)到一定的目標(biāo),如路程最短,費(fèi)用最小,時(shí)間盡量少,車輛盡量少等,就得借助于合適的算法去解決實(shí)際的問題。螞蟻算法在解決著名的旅行商(TSP)問題上已取得了很好的成效,目前已陸續(xù)滲透到其他問題的求解上。文章主要針對(duì)多車場(chǎng)多車型車輛路徑問題,用蟻群算法以及蟻群算法的優(yōu)化算法去解決一些實(shí)際問題。

關(guān)鍵詞:車輛路徑問題;螞蟻算法;優(yōu)化算法

中圖分類號(hào):O227文獻(xiàn)標(biāo)識(shí)碼:A

Abstract: In the vehicle routing problem(VRP), the traveling route usually depends on a series of restrictive conditions, such as the number of the distribution centers, the quantity of the demanding freight, the delivery time and the vehicle capacity constraints. To achieve a certain goal, such as the shortest distance, the minimum cost, the least time and the vehicles as few as possible and so on, we have to use appropriate algorithms to solve practical problems. Ant algorithm has achieved a good result in solving the well-known traveling salesman problem(TSP), now it has been infiltrated into the other problems' solving. In this paper, mainly for Multiple-depot and Heterogeneous-vehicle vehicle routing problems, we adopt ant algorithm and its improved method to solve some practical problems.

Key words: VRP; ant algorithm; optimization algorithm

1研究背景

根據(jù)物流管理中對(duì)運(yùn)輸車輛優(yōu)化調(diào)配的要求,1959年,Dantzig和Ramser[1]首先提出了車輛路徑問題(Vehicle Routing Problem,VRP)的數(shù)學(xué)模型。近幾十年來,VRP[2]一直都備受學(xué)術(shù)界關(guān)注。VRP和TSP一脈相承,同屬組合優(yōu)化領(lǐng)域的NP-hard 問題,但因VRP的約束條件眾多,因而其復(fù)雜程度也就遠(yuǎn)遠(yuǎn)高于TSP[3-4]。特別是對(duì)于大規(guī)模的VRP問題,尋找到高效的精確算法的可能性不大,因此,尋求高效近似的優(yōu)化算法是非常必要和現(xiàn)實(shí)的。國(guó)內(nèi)外專家和學(xué)者對(duì)VRP及其求解方法進(jìn)行了大量的研究,提出了許多關(guān)于不同類型VRP的不同的求解算法。但往往是解決單一性問題,對(duì)復(fù)雜問題還缺少深入地研究。

2車輛路徑問題的分類

車輛路徑問題是從任務(wù)目標(biāo)、車輛載貨狀況、車場(chǎng)數(shù)目、車輛類型、車輛對(duì)車場(chǎng)的所屬關(guān)系、是否有時(shí)間限制等多個(gè)方面進(jìn)行分類分析,然而現(xiàn)實(shí)生活中,往往是多個(gè)類型組合的問題。本文結(jié)合不同的分類方式,根據(jù)蟻群算法以及改進(jìn)的蟻群算法求解以下四類車輛路徑問題:(1)裝卸混合問題;(2)多車場(chǎng)多車型路徑問題;(3)開放式車輛路徑問題;(4)帶時(shí)間窗限制的車輛路徑問題。本文重點(diǎn)分析其中的多車場(chǎng)多車型路徑問題。

3螞蟻算法的原理和算法設(shè)計(jì)

螞蟻算法(ant algorithm),是一種源于昆蟲世界的新的仿生類算法,作為通用型隨機(jī)優(yōu)化方法,其思想吸收了自然界螞蟻群體的行為特性,通過其內(nèi)在的搜索機(jī)制,在一些典型的困難組合優(yōu)化問題求解中取得了成效,展現(xiàn)出了廣闊的發(fā)展前景。研究表明,對(duì)于解決有多種約束條件的VRP,螞蟻算法相對(duì)于其它一系列算法,有其更大的優(yōu)勢(shì)。本文側(cè)重于運(yùn)用蟻群算法以及改進(jìn)的蟻群算法去解決存在一系列約束條件的各類車輛路徑問題[5-6]。

3.1螞蟻行為描述

根據(jù)仿生學(xué)家的長(zhǎng)期研究發(fā)現(xiàn):螞蟻運(yùn)動(dòng)時(shí)會(huì)通過在路上釋放出一種信息素來尋找路徑。結(jié)合圖1來形象說明:

圖1中,設(shè)A點(diǎn)是蟻巢,E點(diǎn)是食物源。HC為障礙物。一開始從A點(diǎn)到達(dá)E點(diǎn)的路徑選擇是隨機(jī)的,BHD和BCD路徑上都存在數(shù)量相等的螞蟻,顯然螞蟻通過BCD的路徑時(shí)間較短,所以在該路徑上的信息素濃度就相對(duì)比較大,后來的螞蟻就會(huì)選擇信息素濃度較大的路徑。隨著時(shí)間的推移,螞蟻將會(huì)以越來越大的概率選擇路徑BCD,最終將會(huì)完全選擇路徑BCD,從而找到由蟻巢到食物源的最短路徑。螞蟻算法的優(yōu)越性包括:分布式計(jì)算、自組織性、正反饋、啟發(fā)性、較強(qiáng)的魯棒性。

3.2基本螞蟻算法的數(shù)學(xué)模型

假設(shè):有n個(gè)城市點(diǎn)需要訪問,共有m只螞蟻,被放置于倉(cāng)庫(kù)位置,螞蟻k從i點(diǎn)出發(fā)選擇下一個(gè)要到達(dá)的城市j點(diǎn),選擇主要依據(jù)于以下兩點(diǎn):

(1)τt,t時(shí)刻從城市i到j(luò)路徑上殘留的信息素濃度。

(2)η由城市i轉(zhuǎn)移到j(luò)的可見度,又稱啟發(fā)信息。算法給出在t時(shí)刻位于城市i的螞蟻k選擇城市j作為目標(biāo)城市的概率是

Pt=(1)

令tabuk=1,2,…,m為每只螞蟻保存的一個(gè)禁忌列表,用于記錄螞蟻k當(dāng)前已經(jīng)訪問過的城市,而N

=0,1,2,n-1-tabu則用來記錄到目前為止還未被訪問過的城市,α為信息素的相對(duì)重要程度,β為啟發(fā)信息的相對(duì)重要程度。

當(dāng)一只螞蟻完成對(duì)所有城市的訪問后,信息素開始局部更新,公式如下:

τt+1=1-ρτt+τρ(2)

式中τt表示原來i、j之間的路徑上的信息素濃度,τt+1表示經(jīng)過一個(gè)時(shí)間單位后i、j路徑上的信息素濃度,ρ定義為信息素的揮發(fā)度,一般取為0,1,則1-ρ即為信息素的殘留度,τ為路徑上的信息素初始濃度,一般設(shè)定為一個(gè)常數(shù)C。

在m只螞蟻全部完成對(duì)所有n個(gè)城市的訪問后,對(duì)殘留信息進(jìn)行全局更新處理,更新公式如下:

τt+n=1-ρτt+Δτ(3)

式中τt+n表示經(jīng)過n個(gè)時(shí)間單位后,i、j路徑上的信息素濃度,Δτ為螞蟻k在時(shí)間段t 到t+n的過程中在路徑i、j上留下的殘留信息素。

4基于螞蟻算法對(duì)多車場(chǎng)多車型車輛路徑問題(MDMHVRP)的研究

(1)研究現(xiàn)狀

在當(dāng)前物流領(lǐng)域中,對(duì)車輛路徑問題的研究主要集中在單車場(chǎng)問題上,對(duì)多車場(chǎng)車輛路徑問題的研究尚不成熟[7]。由于物流行業(yè)配送貨物的多樣性,在研究單車場(chǎng)問題上也是結(jié)合了多車型的實(shí)際情況。為節(jié)約物流配送費(fèi)用,針對(duì)單車場(chǎng)多車型路徑問題存在的不足,本文試著對(duì)多車場(chǎng)多車型車輛路徑問題(Multi-depots Meta-heuristic Vehicle Routing Problem, MDMHVRP)進(jìn)行了探討,提出運(yùn)用自適應(yīng)最大—最小蟻群算法(adaptive max-min ant colony algorithm, A-MMACA)來解決問題。

(2)MDMHVRP 的數(shù)學(xué)模型

本文著重考慮了多個(gè)車場(chǎng)下運(yùn)用多種車型[8]進(jìn)行配送的運(yùn)輸問題,試建立數(shù)學(xué)模型如下:

配送貨物由H輛車從m個(gè)車場(chǎng)向n個(gè)客戶點(diǎn)配送。配送任務(wù)可用一個(gè)加權(quán)圖GV,E來表示,其中節(jié)點(diǎn)集V

=1,2,…,n, n+1,…,n+m,V的前n個(gè)節(jié)點(diǎn)為客戶點(diǎn),后m個(gè)節(jié)點(diǎn)為車場(chǎng)點(diǎn);E=d|i,j∈V代表從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛路徑集合。λ表示路況對(duì)配送車輛的影響。標(biāo)準(zhǔn)路況下,λ=1,好于標(biāo)準(zhǔn)路況則λ<1,反之則λ>1,路況系數(shù)乘以配送點(diǎn)之間的實(shí)際路徑長(zhǎng)度d,就是考慮了路況影響之后的等價(jià)路徑長(zhǎng)度;L是一條可行路徑,fL表示該路徑對(duì)應(yīng)的總費(fèi)用;客戶i點(diǎn)的需求量為q;Q為車輛h的最大容量;客戶點(diǎn)i的重要性用權(quán)值Φ來表示;客戶i點(diǎn)的時(shí)間窗為a,b;t為車輛h從客戶i點(diǎn)到客戶j點(diǎn)的行駛時(shí)間(或代價(jià));車輛在客戶點(diǎn)i服務(wù)所用時(shí)間s=s+ξqs=0,它包括固定服務(wù)時(shí)間s和可變服務(wù)時(shí)間ξq(用需求量q的系數(shù)倍表示);s是一個(gè)決策變量,表示車輛h到達(dá)客戶點(diǎn)i的時(shí)刻。

(3)求解MDMHVRP的算法

1)多車場(chǎng)多車型的選擇步驟

①把各車場(chǎng)中每輛車的信息(所屬車場(chǎng)、車輛編號(hào)、車輛型號(hào)等)存入一個(gè)結(jié)構(gòu)體,結(jié)構(gòu)體的每一個(gè)數(shù)據(jù)表示車輛所在車場(chǎng)的編號(hào),第二個(gè)數(shù)據(jù)表示車輛在該車場(chǎng)內(nèi)的編號(hào),第三個(gè)數(shù)據(jù)表示車輛型號(hào),不同的型號(hào)代表不同的車輛容量。這樣各車場(chǎng)中的車輛就形成了一個(gè)車輛序列。

②搜索最適合當(dāng)前配送任務(wù)的車場(chǎng)。

③當(dāng)搜索過程選中某一個(gè)車場(chǎng)時(shí),抽出此車場(chǎng)中車輛的序列。

④按車型從小到大順序進(jìn)行排列,小車型優(yōu)先,然后依次派出較大車型。

⑤把車輛序列中車型以約束形式加入路徑,控制路徑的組成。

如果車場(chǎng)2中車輛的型號(hào)為1、2、4,路徑初始解為0—4—5—2—0—1—3—0—7—6—0,則車場(chǎng)0的插入點(diǎn)是在1、2、4這個(gè)序號(hào)順序的車輛的容量限制的影響下產(chǎn)生的,即0—4—5—2—0要滿足車型1的車輛容量要求而路徑0—1—3—0要滿足車型2的車輛容量限制。同樣,其他的性能指標(biāo),如不同車輛的最大運(yùn)行距離、速度大小等都可以以這種形式加入,來影響初始解的產(chǎn)生和優(yōu)化[9]。

2)自適應(yīng)最大—最小蟻群算法應(yīng)用步驟

步驟1以較早的服務(wù)開始時(shí)間優(yōu)先服務(wù)的規(guī)則產(chǎn)生一個(gè)可行解fL。

步驟2根據(jù)公式

(4)

進(jìn)一步確定τ、τ,其中ρ表示信息素的揮發(fā)系數(shù)、fL表示當(dāng)前較好解所對(duì)應(yīng)的費(fèi)用、n表示客戶點(diǎn)(節(jié)點(diǎn))個(gè)數(shù),τ=1nfL且滿足τ≤τ≤τ。此時(shí)Δτ=0, N=0, Lr=0,在接下來的步驟一旦信息素更新后,以公式

(5)

重新確定τ, τ。以便避免過早陷于局部最優(yōu)解。

步驟3將k只螞蟻均勻分布到各客戶點(diǎn)。

步驟4用狀態(tài)轉(zhuǎn)移概率公式(6)計(jì)算螞蟻k的狀態(tài)空間轉(zhuǎn)移概率,選擇下一個(gè)目標(biāo)城市。

P=(6)

步驟5應(yīng)用局部信息素更新式:

(7)

進(jìn)行信息更新,探索子路徑。其中,Y表示第k只螞蟻到達(dá)節(jié)點(diǎn)i之前已有Y只螞蟻經(jīng)過i點(diǎn),有y只螞蟻選擇了有向弧段i,j,yY表示有向弧段i,j的螞蟻吸引力,Q表示螞蟻每次釋放的信息量。

步驟6判斷Lr

步驟7輸出當(dāng)前所有螞蟻的路徑,更新禁忌表,保留最優(yōu)解。

步驟8判斷是否遍歷所有節(jié)點(diǎn),是就繼續(xù)步驟9,否則返回步驟4。

步驟9以信息素水平更新式

τ=1-ρτ+w-μ+1Δτ+wΔτρ∈0,1 (8)

對(duì)最好螞蟻進(jìn)行全局更新,保留全局最優(yōu)解,禁忌表清空。其中,w表示k只螞蟻在一個(gè)循環(huán)旅行之后,根據(jù)旅行總費(fèi)用按遞增升序排列,排名前w位的精英螞蟻數(shù)量,一般取3～6之間的整數(shù),只有路徑i,j被排名第μ1≤μ≤w的最好螞蟻利用時(shí),其信息才增加w-μ+1Δτ,而Δτ=1fL, fL為第μ最好解的路徑費(fèi)用。此時(shí)所有當(dāng)前最好路徑上的信息素都被加強(qiáng)wΔτ, Δτ=1fL, L為全局最優(yōu)解對(duì)應(yīng)的長(zhǎng)度。

步驟10判斷N=N是否成立,成立則輸出最優(yōu)解并結(jié)束,否則返回步驟3進(jìn)行第N+1次的循環(huán)。

5總結(jié)及展望

當(dāng)前,物流業(yè)正朝著全球化、信息化、一體化發(fā)展,正積極融入到國(guó)民經(jīng)濟(jì)的各個(gè)產(chǎn)業(yè)鏈中,物流系統(tǒng)中的配送,也顯示出了越來越重要的作用,而其中的車輛路徑問題隨之成為了物流配送中的核心問題。本文的重點(diǎn)是根據(jù)車輛路徑問題的不同方面和側(cè)重點(diǎn)進(jìn)行分類,在前人的研究基礎(chǔ)上對(duì)四類車輛路徑問題中的多車場(chǎng)多車型問題進(jìn)行了深入的研究,并用改進(jìn)的蟻群算法進(jìn)行求解。蟻群算法雖作為一種全新的仿生優(yōu)化算法,但研究中更多是依靠試驗(yàn)和經(jīng)驗(yàn),而沒有定理來確定,因此在改進(jìn)方法上仍有很大的空間等待完善,比如關(guān)于參數(shù)的設(shè)置等。另外,文中所考慮的實(shí)際的隨機(jī)不確定性因素很少,今后要進(jìn)一步加強(qiáng)對(duì)隨機(jī)不確定性條件下的車輛路徑優(yōu)化的研究,綜合盡可能多的實(shí)際因素去考慮最優(yōu)車輛路徑的選擇問題。只要積極朝著關(guān)鍵性的問題進(jìn)行突破,相信螞蟻算法會(huì)有更加廣闊的發(fā)展空間。

參考文獻(xiàn):

[1] Dantzig G B, Ramser K B. The Truck Dispatch Problem[J]. Operation Research, 1959,6:81-89.

[2] 李相勇. 車輛路徑問題模型及算法研究[D]. 上海:上海交通大學(xué),2007.

[3] 齊少安,宋齊軍. 基于TSP模型的物流配送中心車輛路徑優(yōu)化[J]. 郵電設(shè)計(jì)技術(shù),2006(6):62-64.

[4]M Dorigo and L M Gambardella. Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem [J]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.

[5] Reimann M, Doerner K, Hartl RF. D-Ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem[J]. Computers & Operations Research, 2004,31(4):563-591.

[6] 郭倩倩. 蟻群算法的改進(jìn)及其在車輛路徑問題中的應(yīng)用[D]. 成都:西南交通大學(xué),2007.

[7] 章琦. 蟻群算法在車輛路徑問題中的研究[D]. 學(xué)位論文,2006.

[8] 葉志堅(jiān),葉懷珍,周道平,等. 多車型車輛路徑問題的算法[J]. 公路交通科技,2005,22(5):147-151.

[9] 劉敏. 多目標(biāo)遺傳算法在車輛路徑優(yōu)化中的應(yīng)用研究[D]. 湘潭:湘潭大學(xué),2006.