羅芃瑜++左敏

摘要：隨著物流事業(yè)的蓬勃發(fā)展，物流運(yùn)輸配送問(wèn)題也不斷增加。路徑優(yōu)化問(wèn)題作為物流運(yùn)輸配送的基礎(chǔ)研究問(wèn)題也一直受到學(xué)者們的重視。單一的智能優(yōu)化算法已經(jīng)不適合解決大規(guī)模，復(fù)雜度高的路徑優(yōu)化問(wèn)題。在現(xiàn)有的混合智能算法中，基于人工魚(yú)群算法與蟻群算法混合的研究相對(duì)來(lái)說(shuō)較少，因此該文對(duì)學(xué)者們提出的混合人工魚(yú)群-蟻群算法進(jìn)行綜合研究分析，對(duì)現(xiàn)實(shí)中路徑優(yōu)化問(wèn)題的求解有較大的理論意義與現(xiàn)實(shí)價(jià)值。

關(guān)鍵詞：VRP；魚(yú)群蟻群算法；智能優(yōu)化算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）11-0156-04

Review of VRP Optimization Based on AFSA-ACO

LUO Peng-yu， ZUO Min

（Depth of Computer and Information Engineering，Beijing Technology and Business University， Beijing 100048 China）

Abstract： With the vigorous development of the logistics industry， logistics distribution problems are increasing too. As the basis of logistics distribution， Path optimization problem have been brought to the attention of the scholars. A single intelligent optimization algorithm is not suitable for solving vehicle routing problems which of large-scale and high complexity. The research of VRP based on AFSA-ACO is relatively less nowadays. So in this paper， the author will research and analyze these optimization algorithms. This can create great theoretical and practical value on solving the vehicle routing problem.

Key words： VRP； AFSA-ACO； Intelligent optimization algorithms

在物流的配送優(yōu)化等問(wèn)題中，常見(jiàn)的問(wèn)題就是：存在一批客戶，并且已知客戶的地理坐標(biāo)，每個(gè)客戶對(duì)貨物的需求量，運(yùn)輸車(chē)輛的最大數(shù)量和運(yùn)載能力等信息。在每輛運(yùn)輸車(chē)都從倉(cāng)庫(kù)出發(fā)，完成部分點(diǎn)的運(yùn)輸任務(wù)后返回倉(cāng)庫(kù)的前提下，尋求以最少車(chē)輛和最短總行程完成物流運(yùn)輸?shù)淖顑?yōu)解。此類問(wèn)題統(tǒng)稱為車(chē)輛運(yùn)輸路徑問(wèn)題，即Vehicle Routing Problem，VRP。

路徑優(yōu)化問(wèn)題是現(xiàn)代物流供應(yīng)鏈優(yōu)化中的關(guān)鍵問(wèn)題，車(chē)輛路徑問(wèn)題的理論與算法依然是學(xué)者們重視的問(wèn)題與研究的重點(diǎn)。對(duì)算法進(jìn)行系統(tǒng)的研究不僅為物流運(yùn)輸優(yōu)化提供更好的思路和方法，更加為構(gòu)建綜合物流系統(tǒng)，發(fā)展智能交通運(yùn)輸系統(tǒng)等打下堅(jiān)實(shí)的理論基礎(chǔ)。

1 車(chē)輛路徑問(wèn)題

1.1 車(chē)輛路徑問(wèn)題分類

車(chē)輛路徑的問(wèn)題隨著相關(guān)學(xué)科的發(fā)展從最初的靜態(tài)的VRP、VRPTW、VRPPD等模型不斷衍生出隨機(jī)車(chē)輛路徑問(wèn)題、模糊車(chē)輛路徑問(wèn)題，到現(xiàn)在的動(dòng)態(tài)車(chē)輛路徑問(wèn)題。所以可以將車(chē)輛路徑問(wèn)題歸為兩大類，一類是一般車(chē)輛路徑問(wèn)題，而另一類則是衍生車(chē)輛路徑問(wèn)題[1]，具體如下圖1所示。

圖1 車(chē)輛路徑問(wèn)題分類

1.2 車(chē)輛路徑問(wèn)題的一般模型

對(duì)于一般車(chē)輛運(yùn)輸問(wèn)題的優(yōu)化，為方便模型的建立，對(duì)貨物的物流運(yùn)輸作以下幾點(diǎn)假設(shè)：

（1）僅考慮位置已知的一個(gè)倉(cāng)庫(kù)，所有配送車(chē)輛起點(diǎn)和終點(diǎn)均是該倉(cāng)庫(kù)。

（2）只考慮單個(gè)品種貨物的運(yùn)輸，且每個(gè)需求點(diǎn)所需要的貨物劑不超過(guò)車(chē)輛的最大載重量。

（3）每個(gè)需求點(diǎn)的地理坐標(biāo)位置和需求量都已知，其需求有且僅由一輛車(chē)輛一次送貨滿足。

（4）只有一種車(chē)輛，且車(chē)輛的載重量已知。

（5）車(chē)輛對(duì)每個(gè)需求點(diǎn)進(jìn)行服務(wù)，途中只有卸貨而無(wú)裝貨。

（6）車(chē)輛的平均行駛速度已知，并且確定，行駛的路程與車(chē)輛行駛時(shí)間成正比。

以上述假設(shè)為前提，以配送成本最小化為目標(biāo)，構(gòu)造出以下優(yōu)化模型。

[minZ=i=0j=0k=1dij?xijk （1） ]

式中，倉(cāng)庫(kù)的編號(hào)為0，需求點(diǎn)的編號(hào)為[1，2，…，C]，[ xijk=1.0]取整數(shù)約束，1表示點(diǎn)i 到點(diǎn) j由車(chē)輛 k來(lái)完成，否則為0；其中[yijk=1.0]取整數(shù)約束，1表示到點(diǎn)i由車(chē)輛 k來(lái)完成，否則為0。C為需求點(diǎn)的個(gè)數(shù)；m為車(chē)輛數(shù)；[dij（i，j=1，2，…，C）]為需求點(diǎn)i點(diǎn)與需求點(diǎn)j點(diǎn)之間的距離；[ ti]為車(chē)輛實(shí)際到達(dá)需求點(diǎn)的時(shí)間；[gi]為第i個(gè)醫(yī)療機(jī)構(gòu)的需求量； [q]為車(chē)的最大載重量；[k（k=1，2，…，m）]為車(chē)輛的編號(hào)。

約束條件為：

每次為需求點(diǎn)運(yùn)輸貨物的運(yùn)輸量不能超過(guò)車(chē)輛的最大載重量；

[i=0giyki≤qi k∈1，m （2）]

任意需求點(diǎn)只有1輛車(chē)輛來(lái)訪；

[k=1yki =1 i∈0，C，k∈1，m （3）]

[i=0k=1xijk =1 j∈0，C，k∈1，m （4）]

[j=0k=1xijk =1 i∈0，C，k∈1，m （5）]

車(chē)輛行駛路線為閉合線路；

[i=0xijk=yki i∈0，C，k∈1，m （6）]

[j=0xijk=yki j∈0，C，k∈1，m （7）]

2 智能優(yōu)化算法的分類與比較

解決車(chē)輛路徑算法的種類很多從20世紀(jì)50年代起的精確算法開(kāi)始，到之后的啟發(fā)式算法，以及現(xiàn)在學(xué)者們研究的最多的智能優(yōu)化算法。其中精確算法有：分支界定法（Branch and Bound Approach）、割平面法（Cutting Planes Approach）等，啟發(fā)式算法有：節(jié)約算法（C-W）、掃描算法（Sweep Algorithm）等，應(yīng)用最多的智能優(yōu)化算法有：禁忌搜索算法（Tabu Search）、模擬退火算法（Simulated Annealing）、遺傳算法（Genetic Algorithm）、蟻群算法（Ant Colony Optimization）、粒子群算法（Particle Swarm Optimization），另外還有人工魚(yú)群算法（Artificial Fish School Algorithm）、人工神經(jīng)網(wǎng)絡(luò)算法（Artificial Neural Networks）等智能優(yōu)化算法，都在車(chē)輛路徑問(wèn)題的研究中有應(yīng)用。

隨著物流業(yè)的不斷發(fā)展，物流運(yùn)輸配送遇到的問(wèn)題范圍不斷的擴(kuò)大，實(shí)際問(wèn)題的規(guī)模與復(fù)雜性也不斷的增大，僅僅靠單一的算法來(lái)優(yōu)化解決問(wèn)題的效果已經(jīng)越來(lái)越不理想，每個(gè)算法都有各自的缺陷，都面臨著時(shí)間性能和優(yōu)化性能等挑戰(zhàn)。如下表1是目前運(yùn)用最多的智能優(yōu)化算法思想和優(yōu)缺點(diǎn)[2]。

表1 常見(jiàn)智能優(yōu)化算法及其特點(diǎn)

[智能優(yōu)化算法＼&基本思想＼&優(yōu)點(diǎn)＼&缺點(diǎn)＼&禁忌搜索優(yōu)化算法＼&通過(guò)建立Tuba表，記錄選擇已經(jīng)優(yōu)化的過(guò)程，逐步在全局領(lǐng)域內(nèi)尋找最優(yōu)解＼&分別通過(guò)禁忌準(zhǔn)則和特赦準(zhǔn)則避免迂回搜索與赦免部分被禁忌的優(yōu)良狀態(tài)保證搜索多樣性和實(shí)現(xiàn)全局最優(yōu)＼&對(duì)初始解依賴性強(qiáng)，初始解的選定會(huì)影響收斂速度＼&遺傳算法＼&模擬生物界優(yōu)勝劣汰、適者生存的遺傳和變異的進(jìn)化機(jī)制＼&能全局并行搜索，有自適應(yīng)能力，可處理大量信息，對(duì)局部性能高的重點(diǎn)搜索，不易陷入局部最?。?amp;收斂性差，容易“早熟”，處理約束優(yōu)化問(wèn)題較困難＼&模擬退火算法＼&基于物理中固體物質(zhì)退火過(guò)程，從高初溫出發(fā)，伴隨溫度下降，結(jié)合概率突跳特性，隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解＼&簡(jiǎn)單、通用、易實(shí)現(xiàn)、運(yùn)行效率高＼&對(duì)初值有依賴性，搜索速度受串行影響，對(duì)不同狀態(tài)下的抽樣有較高的要求＼&蟻群算法＼&模仿自然界螞蟻群體覓食過(guò)程中螞蟻間互相傳遞信息素在較短的時(shí)間內(nèi)通過(guò)最短的路程找到食物＼&分布式計(jì)算，并行性，全局搜索能力，自組織，正反饋＼&收斂速度慢，易早熟，容易陷入局部最優(yōu)解＼&粒子群算法＼&模仿鳥(niǎo)群捕食的行為，人工建立以有向圖為拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)系統(tǒng)，對(duì)連續(xù)或斷續(xù)的輸入狀態(tài)做狀態(tài)相應(yīng)而進(jìn)行的信息處理＼&操作簡(jiǎn)單，快速收斂，適合實(shí)值型處理＼&容易陷入局部最優(yōu)解＼&人工魚(yú)群算法＼&通過(guò)一片水域中魚(yú)群聚集的數(shù)量判斷食物多少的特點(diǎn)，構(gòu)造人工魚(yú)，模仿魚(yú)群的覓食、聚群、追尾等行為，實(shí)現(xiàn)尋優(yōu)。＼&對(duì)初值敏感性小，并行性，簡(jiǎn)單性，全局性，快速性，跟蹤性＼&計(jì)算量較大，后期收斂逐漸減慢，容易陷入局部最優(yōu)＼&]

基于上述現(xiàn)象及出發(fā)點(diǎn)，可將各種單一的算法取長(zhǎng)補(bǔ)短，利用各算法的優(yōu)勢(shì)進(jìn)行融合，構(gòu)造出新的優(yōu)化效率更高的混合算法。

3 魚(yú)群-蟻群算法

3.1 人工魚(yú)群算法

人工魚(yú)群算法（AFSA）是基于模仿魚(yú)群覓食、聚群和追尾等行為而衍生出的一種較新型智能優(yōu)化算法。這種算法具有并行性、快速性、較強(qiáng)的搜索全局性等特點(diǎn)。在人工魚(yú)群算法中，設(shè)人工魚(yú)當(dāng)前所在的位置是[Xi=xi1，xi2，…，xiN]，[Xv=xv1，xv2，…，xvN]，其中N表示維數(shù)，Visual表示人工魚(yú)的視野范圍，[Xv]表示視野范圍內(nèi)的一個(gè)狀態(tài)。人工魚(yú)的步長(zhǎng)用Step表示，人工魚(yú)要從當(dāng)前狀態(tài)到一個(gè)更優(yōu)的狀態(tài)過(guò)程可以表示為：

[Xv=Xi+Visual*rand（）] （8）

[Xnext=Xv-XiXv-Xi*Step*rand（）] （9）

人工魚(yú)群算法還包括了一下幾個(gè)行為：（1）覓食行為。在人工魚(yú)的視野范圍內(nèi)選擇位置[Xv]，若[Xv]的適應(yīng)度[Yv]大于[Xi]的適應(yīng)度[Yi]，則該人工魚(yú)向[Xv]的方向移動(dòng)一步，反之，則從新選擇一個(gè)位置。（2）聚群行為。在避免擁擠和逐步中心的規(guī)則下，執(zhí)行覓食行為或隨機(jī)游動(dòng)。其中一個(gè)重要的參數(shù)叫做擁擠因子，用[σ表示]。

若[Ycnf>σYi]（其中），表示中心食物較多且不擁擠，人工魚(yú)向[Xc]方向移動(dòng)一步，反之，則執(zhí)行覓食行為或隨機(jī)游動(dòng)。（3）追尾行為。在優(yōu)化過(guò)程中，若[Yvnf>σYi]，表示在視野范圍內(nèi)，最優(yōu)狀態(tài)的伙伴位置為[Xv]，且食物濃度高，不擁擠，則[Xi]向[Xv]的方向移動(dòng)一步，反之，則執(zhí)行覓食行為。（4）隨機(jī)移動(dòng)。即人工魚(yú)在其視野范圍內(nèi)隨機(jī)移動(dòng)一步。人工魚(yú)群算法的基本流程如下圖2所示。

圖2 人工魚(yú)群算法的基本流程

3.2 蟻群算法

蟻群算法（ACO）是一種在圖中尋找優(yōu)化路徑的隨機(jī)搜索型算法。它最開(kāi)始是由Marco Dorigo于1992年提出的，后來(lái)由Bernd Bullnheimer等[3]率先應(yīng)用于解決VRP問(wèn)題，即先通過(guò)蟻群算法搜索最優(yōu)路徑，再運(yùn)用2-Opt法對(duì)其進(jìn)行優(yōu)化，最后找出最優(yōu)解。蟻群算法的基本思想是模仿螞蟻覓食發(fā)現(xiàn)最優(yōu)路徑的行為，并以下面三個(gè)假設(shè)為前提：（1）螞蟻之間通過(guò)產(chǎn)生信息素進(jìn)行相互通信；（2）螞蟻對(duì)環(huán)境的反應(yīng)由內(nèi)部的模式?jīng)Q定；（3）每只螞蟻的行為是隨機(jī)的且僅依照環(huán)境做獨(dú)立選擇，蟻群可以通過(guò)自組織形成高度有序的群體行為。

蟻群算法中關(guān)鍵的因素有以下幾個(gè)：

（1）信息素用[τijt]表示t時(shí)刻路徑上信息素的含量，隨著時(shí)間的推移信息素的含量不斷應(yīng)新舊信息素的加入和揮發(fā)而改變，當(dāng)時(shí)刻變?yōu)閠+n后，各個(gè)路徑上的信息素變?yōu)椋海ㄆ渲衃ρ]信息素的揮發(fā)系數(shù)）

[τijt+n=1-ρ?τijt+?τijt （10）]

[τijt=k=1m?τijt （11）]

（2）啟發(fā)函數(shù)用來(lái)表示螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度，其計(jì)算公式為：

[ηijt=1dij （12）]

（3）狀態(tài)轉(zhuǎn)移概率，這里以[Pkijt]表示，其計(jì)算公式為：（其中[α]為啟發(fā)因子表示螞蟻在路徑中積累的信息的作用，值越大則意味著螞蟻間的協(xié)作性越強(qiáng)。[β]為期望啟發(fā)因子表示啟發(fā)信息在螞蟻路徑選擇中的重要程度，值越大則意味著該狀態(tài)下的轉(zhuǎn)移率越接近貪心規(guī)則。）

[Pkijt=τijtα?ηiktβs?allowedkτijtα?ηiktβ，若j∈allowedk0，若j?allowedk （13）]

蟻群算法求解VRP的基本流程，如下圖所示：

圖3 蟻群算法求解VRP基本流程

3.3 魚(yú)群蟻群混合算法

在解決VRP問(wèn)題中，對(duì)魚(yú)群蟻群混合算法的研究還不是很多，現(xiàn)有的兩種算法可結(jié)合的方法主要分為加入改變擁擠因子，改變信息素更新機(jī)制兩種形式：

（1）改變擁擠因子。文獻(xiàn)[4]在研究特殊醫(yī)療器械物流配送路徑優(yōu)化時(shí)，將魚(yú)群算法與基本蟻群算法相結(jié)合，把魚(yú)群算法中的擁擠因子概念引入到基本蟻群算法中，是算法整體增強(qiáng)尋優(yōu)能力，減少基本蟻群算法陷入局部最優(yōu)的可能性。其中設(shè)擁擠因子[σij]和擁擠度門(mén)限[δt]的計(jì)算公式分別如式（14）和式（15），其中[γ]為極值接近水平，[b]為閾值變化系數(shù)。其改進(jìn)方法可以控制螞蟻集數(shù)量的多少，以此抑制螞蟻過(guò)早的聚集在高信息素的路徑上，從而減少早熟現(xiàn)象的發(fā)生幾率。但是該方法也存在不足，特別是在算法的后期會(huì)影響收斂速度。

[σijt=1-τijti≠jτij （14）]

[δt=γe-bt （15）]

文獻(xiàn)[5][6]也是研究人工魚(yú)群算法擁擠度的引入。部分區(qū)別在于擁擠因子的設(shè)置上如式（16）所示。同樣在算法的初期設(shè)置較強(qiáng)的門(mén)限，但是隨著迭代次數(shù)的增加，擁擠度閾值逐漸增大，信息素的濃度在指導(dǎo)蟻群選擇路徑的作用逐漸增強(qiáng)，最后蟻群完全由信息素和啟發(fā)因子來(lái)指導(dǎo)尋優(yōu)從而保證了算法能夠快速地收斂到最優(yōu)解上。

[σijt=2τijti≠jτijt （16）]

（2）改變信息素更新機(jī)制。文獻(xiàn)[7]在運(yùn)用魚(yú)群蟻群混合算法解決模塊化產(chǎn)品配置問(wèn)題中，提出了兩種算法動(dòng)態(tài)融合策略。不是通過(guò)改變擁擠因子來(lái)進(jìn)行優(yōu)化，而是通過(guò)設(shè)置魚(yú)群算法的迭代范圍，統(tǒng)計(jì)滿意的更新率，選擇魚(yú)群與蟻群融合的最佳轉(zhuǎn)換時(shí)機(jī)來(lái)進(jìn)行尋優(yōu)。當(dāng)人工魚(yú)群算法的優(yōu)化速度明顯減慢時(shí)便終止人工魚(yú)群算法，開(kāi)始蟻群算法。同時(shí)文獻(xiàn)中改變了蟻群算法的信息素更新方程，將基本方程如式（10）改為式（16）。方程中[τijtmin]，[τijtmax]分別為信息素強(qiáng)度的上下限，尋求最優(yōu)解。

[τijt+n=τijtmax ，若τijt>τijtmax1-ρ?+?τijt，若τijtmin≤τijt≤τijtmin，若τijt>τijtmin τijtmax（17）]

文獻(xiàn)[8] 應(yīng)用人工魚(yú)群算法的追尾行為對(duì)蟻群在可行域上搜索到的可行解進(jìn)行改進(jìn)，將微分進(jìn)化算法引入信息素的更新機(jī)制中，改變?nèi)斯~(yú)群算法的追尾公式，如式（18），其中[Xbest]表示當(dāng)前最優(yōu)解，[Xki]表示螞蟻k的狀態(tài)[Xk]的第i個(gè)元素。之后再對(duì)修改過(guò)的新解進(jìn)行信息素更新，從而加快收斂速度，快速達(dá)到全局最優(yōu)。

[Xnewkj=Xkj+randStepXbest-Xki/Xbest-Xk] （18）

4 結(jié)束語(yǔ)

本文總結(jié)了在物流業(yè)發(fā)展的大背景下，不斷衍生出的一系列路徑優(yōu)化問(wèn)題，比較了各種智能優(yōu)化算法的優(yōu)缺點(diǎn)，得出改進(jìn)單一智能優(yōu)化算法的重要性。進(jìn)而研究了現(xiàn)今學(xué)者們?cè)谌斯~(yú)群蟻群混合算法求解VRP問(wèn)題時(shí)的思路與方法。對(duì)混合魚(yú)群蟻群算法進(jìn)行了整理歸類，對(duì)于完善路徑優(yōu)化問(wèn)題的求解算法具有重要意義。

參考文獻(xiàn)：

[1] 吳斌. 物流配送車(chē)輛路徑問(wèn)題及其智能優(yōu)化算法[M]. 北京：經(jīng)濟(jì)管理出版社，2013.

[2] 張建林. MATLAB&Excel定量預(yù)測(cè)與決策：運(yùn)作案例精編[M]. 北京：電子工業(yè)出版社，2012.

[3] B. Bullnheimer，R.F. Hartl，C. Strauss. An improved Ant System algorithm for theVehicle Routing Problem[J]. Annals of Operations Research，1999，890.

[4] 費(fèi)騰. 基于蟻群算法的醫(yī)療器械物流配送路徑優(yōu)化算法研究[D].太原：太原理工大學(xué)，2010.

[5] 修春波，張雨虹. 基于蟻群與魚(yú)群的混合優(yōu)化算法[J]. 計(jì)算機(jī)工程，2008，14：206-207，218.

[6] 鄒挺. 基于蟻群和人工魚(yú)群混合群智能算法在物流配送路徑優(yōu)化問(wèn)題中的應(yīng)用研究[D].蘇州：蘇州大學(xué)，2011.

[7] 高德芳，趙勇，郭楊，趙海濤. 基于混合魚(yú)群-蟻群算法的模塊化產(chǎn)品配置設(shè)計(jì)[J]. 機(jī)械，2007（1）：7-10.

[8] 韓芳，邢曉哲，方婷婷，王成儒. 融合魚(yú)群和微分進(jìn)化的蟻群算法的無(wú)功優(yōu)化[J]. 黑龍江電力，2011（2）：125-128.