基于蟻群算法的物流配送中車輛路徑優(yōu)化問題研究

張 偉

（蘭州交通大學(xué) 機(jī)電技術(shù)研究所，甘肅 蘭州 730070）

ZHANG Wei

(Electromechanical Technology Research Institute of Lanzhou Jiaotong University,Lanzhou 730070,China)

0 引言

在經(jīng)濟(jì)全球化的大趨勢下，物流行業(yè)也發(fā)生了一定的變化，已經(jīng)從傳統(tǒng)的運(yùn)輸服務(wù)行業(yè)逐漸向著綜合性物流系統(tǒng)型行業(yè)的模式發(fā)展?，F(xiàn)階段，很多國家及地區(qū)都形成了較為完善的物流理念，擁有著成熟的物流技術(shù)，我國物流行業(yè)發(fā)展雖然緩慢，但是由于我國資源豐富，鐵路、公路等物流基礎(chǔ)設(shè)施建設(shè)比較完善，為物流行業(yè)發(fā)展提供了良好的環(huán)境，使得我國的物流行業(yè)齊頭并進(jìn)，逐漸具備了與國外先進(jìn)物流技術(shù)相媲美的實(shí)力。

現(xiàn)代化物流配送是市場經(jīng)濟(jì)發(fā)展的要求，對促進(jìn)大眾消費(fèi)、優(yōu)化資源配置等方面都具有較大的影響。物流配送方案的好壞，在很大程度上決定了物流配送的效率與成本，同時(shí)也影響著實(shí)現(xiàn)物流服務(wù)行業(yè)的附加價(jià)值。而物流配送車輛路徑優(yōu)化問題，早在1959年就由Dantzig 及Ramser 提出，后來這一說法引起了物流科學(xué)、組合數(shù)學(xué)、應(yīng)用數(shù)學(xué)、運(yùn)籌學(xué)等學(xué)者、專家們的重視，成為組合優(yōu)化領(lǐng)域的熱門話題。關(guān)于物流配送車輛路徑優(yōu)化問題，定義為：對物流貨物裝卸點(diǎn)進(jìn)行有效的組織，安排恰當(dāng)?shù)男熊嚶窂?，保證物流配送車輛能夠有序的通過這些裝卸點(diǎn)，并能夠在一定的交貨時(shí)間、貨物需求量、時(shí)間限制等約束條件下，盡可能實(shí)現(xiàn)用最少車輛、最少時(shí)間、最短行程完成物流配送任務(wù)。

在近幾十年的研究中，有關(guān)配送車輛路徑優(yōu)化算法出現(xiàn)很多，包括精確算法、智能優(yōu)化算法以及啟發(fā)算法等，其中精確算法在路徑優(yōu)化中的應(yīng)用計(jì)算復(fù)雜程度較高，具有一定的局限性；啟發(fā)式算法中包括SWeep 算法以及C-W 算法等，這些算法雖然具有速度快的優(yōu)勢，但是如果客戶數(shù)量過多時(shí)，就會增加算法搜索的難度，不容易找到最優(yōu)路徑；人工智能算法的出現(xiàn)，在一定程度上提高了路徑優(yōu)化的效率，其中神經(jīng)網(wǎng)絡(luò)算法、遺傳算法等都屬于人工智能算法中的一種。然而物流配送車輛路徑優(yōu)化工作是一項(xiàng)復(fù)雜的大規(guī)模工作，有些算法在網(wǎng)絡(luò)結(jié)構(gòu)、參數(shù)確定等方面還存在缺陷，不能同時(shí)滿足時(shí)間、成本、車輛等因素條件。

蟻群算法也屬于智能優(yōu)化算法的一種，主要是利用正反饋并行機(jī)制，并根據(jù)螞蟻之間的相互協(xié)作在最短時(shí)間找到食物與巢穴的最短路徑現(xiàn)象確定的一種算法。蟻群算法具有求解速度快、并行性能力強(qiáng)等優(yōu)勢，近年來在水運(yùn)、鐵路、公路等領(lǐng)域都得到了廣泛的應(yīng)用。本文也將蟻群算法應(yīng)用到物流配送車輛路徑優(yōu)化問題中，通過此原理建立數(shù)學(xué)模型，并通過模型找出路徑優(yōu)化的最優(yōu)解。

1 建立數(shù)學(xué)模型

在物流配送工作過程中，其實(shí)就是討論以什么樣的路徑進(jìn)行運(yùn)輸，也就是在已知客戶需求量以及車輛載重量的基礎(chǔ)上，探討怎樣以最短的時(shí)間、最少的成本，縮短配送路程。在尋找最短路徑過程中，還需要滿足以下幾個(gè)條件：第一，所有的物流配送車輛必須將配送中心作為起點(diǎn)和終點(diǎn)，完成一個(gè)配送的循環(huán)；第二，每輛配送車僅能為一條路線服務(wù)，并且每輛配送車僅能訪問一個(gè)客戶；第三，在配送路線上，客戶需求量不能超過車輛配送的載重量總和；第四，車輛的路線不能重復(fù)。

根據(jù)上述的幾個(gè)約束條件，在物流配送車輛路徑優(yōu)化問題上，就是尋找最優(yōu)路徑。我們可以將物流配送中心用v0表示，將配送地點(diǎn)用vi表示，用k 表示配送中心車輛數(shù)目的上限，用Q 表示配送車輛的載重。這樣就能將配送路徑優(yōu)化數(shù)學(xué)模型表示為：

2 關(guān)于蟻群算法的相關(guān)理論

本文中所講的蟻群算法，屬于仿生優(yōu)化算法中的一種，是一種新興的算法工具，主要是通過模仿螞蟻蟻群的行為，得出最優(yōu)解。其實(shí)，蟻群算法主要是模仿螞蟻覓食的過程，將螞蟻覓食的路徑當(dāng)做是物流配送車輛運(yùn)輸?shù)穆窂?，將螞蟻行動的錄像集合作為移動線路，并利用分布式協(xié)作以及正反饋機(jī)制，獲取最優(yōu)解。這種算法魯棒性強(qiáng)，并且具有很快的求解速度，廣泛應(yīng)用于二次分配、作業(yè)調(diào)度、旅行等領(lǐng)域，并具有良好的應(yīng)用效果。

圖1 是蟻群路徑搜索過程圖：

如圖1 所示，用字母A 代表蟻巢，將食物源用字母F 表示，同時(shí)設(shè)置一個(gè)障礙物，用CD 表示。由于存在障礙物，螞蟻在覓食過程中必須穿過障礙物，穿過障礙物的路徑有多種，螞蟻會通過相互之間的合作機(jī)制、信息素更新機(jī)制等，選擇最短的路徑作為覓食路線。

3 基于蟻群算法的物流配送車輛路徑優(yōu)化設(shè)計(jì)

在物流配送車輛路徑優(yōu)化算法設(shè)計(jì)過程中，利用蟻群算法，主要包括確定蟻群數(shù)目、設(shè)定蟻群路徑選擇規(guī)則、信息素更新機(jī)制規(guī)則等幾個(gè)方面：

3.1 確定蟻群數(shù)目。假設(shè)一共有n 個(gè)客戶數(shù)，相應(yīng)的蟻群中就具有m 個(gè)螞蟻數(shù)量，則螞蟻數(shù)量可以用下面的表達(dá)式表示：m其中在時(shí)間t 點(diǎn)，在客戶i 位置上，螞蟻的數(shù)量就表示為bi（t）。

3.2 蟻群路徑選擇規(guī)則。在物流配送車輛路徑優(yōu)化設(shè)計(jì)過程中，基于蟻群算法，螞蟻（k）從一個(gè)客戶到下一個(gè)客戶中間轉(zhuǎn)移的過程中，需要考慮到下一個(gè)客戶路徑中信息素濃度、路徑總長度等問題。我們可以將允許訪問的客戶點(diǎn)用j 表示，將配送中心用o 表示，這樣就能將螞蟻從上一個(gè)客戶點(diǎn)到下一個(gè)客戶點(diǎn)轉(zhuǎn)移路徑的概率用相關(guān)的計(jì)算公式表示出來，具體表示為：

在上式中，權(quán)重系數(shù)用a、b 表示，而螞蟻從上一個(gè)客戶到下一個(gè)客戶所用的時(shí)間用tij表示，將信息啟發(fā)式因子用α 表示，而期望啟發(fā)式因子用β 表示。而兩個(gè)客戶之間路徑關(guān)聯(lián)啟發(fā)式信息值用ηij（t）表示，并且可以將ηij（t）定義為：ηij（t）=1/dij，其中，dij是兩個(gè)客戶自檢的距離。

3.3 信息素更新機(jī)制規(guī)則。利用蟻群算法過程中，為了對循環(huán)最優(yōu)解進(jìn)行充分的利用，并且保證盡快的找到最優(yōu)解，需要在每次循環(huán)后，將每只螞蟻帶來的相關(guān)信息進(jìn)行及時(shí)的更新，同時(shí)在信息素更新過程中還需要遵循一定的規(guī)則。如果將信息素?fù)]發(fā)系數(shù)用ρ 表示，其中ρ 是0 到1 之間的一個(gè)隨機(jī)數(shù)值，將信息素殘留因子用1-ρ 表示；一次循環(huán)中路徑中增加的信息素可以用ΔTij表示，設(shè)ΔTij的初始值為0。那么就能夠?qū)⑿畔⑺馗虏僮鞯囊?guī)則用以下兩個(gè)式子表示出來：

4 物流配送中車輛路徑優(yōu)化實(shí)現(xiàn)

在物流配送車輛路徑優(yōu)化問題求解方面，利用蟻群算法，主要是用人代替螞蟻來尋找物流客戶點(diǎn)，如果下一個(gè)客戶服務(wù)點(diǎn)中，車輛總載重量如果被超出，或者是兩者之間的距離比車輛一次行駛的最大距離遠(yuǎn)，這需要配送車輛回到配送中心，同時(shí)也表示該配送車輛完成了這次的配送任務(wù)，該輛配送車就能夠進(jìn)行下一個(gè)服務(wù)站點(diǎn)的任務(wù)，直到有一個(gè)客戶獲得了一次完整的服務(wù)為止，這就說明人工螞蟻完成了一次循環(huán)。在經(jīng)過一個(gè)循環(huán)后，根據(jù)每一個(gè)人工螞蟻在循環(huán)過程中得到的信息，對路徑中的信息素增加量進(jìn)行有效的計(jì)算，同時(shí)進(jìn)行信息素更新操作，這樣重復(fù)的循環(huán)后，就會有大部分人工螞蟻找出相同的路徑，同時(shí)也會找到最短的路徑，這樣就完成了最優(yōu)解的算法設(shè)計(jì)。本文將這個(gè)構(gòu)成步驟整理為以下幾點(diǎn)：

第一步，將參數(shù)進(jìn)行初始化設(shè)置，然后對有需求的客戶進(jìn)行相關(guān)數(shù)據(jù)讀取，之后產(chǎn)生全局最初解。

第二步，在物流配送中心設(shè)置m 個(gè)人工螞蟻，將初始時(shí)間以及迭代次數(shù)都設(shè)置為0，同時(shí)進(jìn)行蟻群禁忌表建立。

第三步，對于每一個(gè)人工螞蟻，需要從列表中查出其沒有到達(dá)過的節(jié)點(diǎn)，同時(shí)根據(jù)上文中提到的轉(zhuǎn)移概率的公式，通過詳細(xì)的計(jì)算、分析，為人工螞蟻選擇合理的下一個(gè)客戶服務(wù)點(diǎn)。

第四步，對兩個(gè)客戶服務(wù)點(diǎn)路徑中的貨運(yùn)總量進(jìn)行計(jì)算，如果路徑中的貨運(yùn)總量比車輛最大載重量大，那么就直接進(jìn)行下一個(gè)步驟；如果沒有超過，就能夠?qū)⒃摴?jié)點(diǎn)作為可行點(diǎn)，并跳轉(zhuǎn)到第六步中。

第五步，對客戶需求點(diǎn)等待的時(shí)間進(jìn)行計(jì)算，如果符合時(shí)間窗的相關(guān)要求，就能在禁忌表中加入該點(diǎn)，同時(shí)計(jì)算兩個(gè)點(diǎn)之間的路徑費(fèi)用、長度等，跳轉(zhuǎn)到第三步進(jìn)行；否則就在可行點(diǎn)集合中加入該點(diǎn)，同時(shí)進(jìn)入下一步。

第六步，統(tǒng)計(jì)車輛的數(shù)目，然后判斷可行點(diǎn)的集合，如果集合為空集，則直接進(jìn)入下一個(gè)步驟。如果集合不是空集，則需要從集合中獲取沒有經(jīng)過搜索的點(diǎn)，同時(shí)將時(shí)間最短的節(jié)點(diǎn)作為起點(diǎn)，跳回到第三步進(jìn)行。

第七步，更新每一個(gè)人工螞蟻帶來的信息素增量。

第八步，搜索人工螞蟻路徑的最短值以及路徑的最短距離，同時(shí)計(jì)算最短路徑對應(yīng)的費(fèi)用，并及時(shí)的更新信息素。在循環(huán)開始時(shí)，對所有的人工螞蟻進(jìn)行迅游，對人工螞蟻搜索過后的邊進(jìn)行信息素更新，不然就進(jìn)行本循環(huán)中找到的最優(yōu)路徑。

第九步，對本次循環(huán)以及所有的路徑最優(yōu)解進(jìn)行比對，如果本次循環(huán)比全局最優(yōu)解路徑更短，就將其作為最優(yōu)解，同時(shí)更新最優(yōu)解列表。

第十步，找到全局的最優(yōu)解或者迭代次數(shù)達(dá)到上限，就表示該程序完成，否則就需要從第二步驟開始進(jìn)行重復(fù)上述過程。

可以將本步驟用圖2 表示：

5 仿真實(shí)驗(yàn)

假設(shè)一個(gè)物流配送中心一共有30 輛車，每輛車的載重量相等，都為12噸，同時(shí)向30 個(gè)服務(wù)客戶提供物流配送服務(wù)，客戶的坐標(biāo)資料是已知的，每一個(gè)客戶的客戶需求量也是已知的。客戶資料如表1 所示。

采用專業(yè)的仿真計(jì)算機(jī)平臺，平臺主要為3.4GMHz 的CPU、4G 內(nèi)存，Windows2007 操作系統(tǒng)，在VB6.0 語言環(huán)境下進(jìn)行編程實(shí)現(xiàn)。用同時(shí)設(shè)置蟻群算法的相關(guān)參數(shù)，具體設(shè)置如表2 所示。

實(shí)驗(yàn)結(jié)果如下：

當(dāng)?shù)_(dá)到283 次時(shí)，求出了路徑的最優(yōu)解，并且最優(yōu)路徑的長度通過計(jì)算得到為165。

同時(shí)，仿真實(shí)驗(yàn)中還將蟻群算法與遺傳算法、模擬退火算法等進(jìn)行了有效的對比，用每一種算法運(yùn)行10 次，然后通過計(jì)算，對比結(jié)果的平均值，其中遺傳算法找出的最優(yōu)路徑長度為183.2，整個(gè)過程花費(fèi)了50 多秒，成功率為65%；模擬退火算法找出的最優(yōu)路徑的長度為172.4，過程時(shí)間為42 秒，成功率為78%；本文中提到的算法，最優(yōu)路徑長度為165，整個(gè)過程花費(fèi)的時(shí)間為21 秒，成功率高達(dá)98%。這些數(shù)據(jù)說明了蟻群算法在物流配送車輛路徑優(yōu)化中具有獨(dú)特的應(yīng)用優(yōu)勢，能夠在短時(shí)間找出最短路徑，是提高物流配送效率的有效方式。

6 總結(jié)

通過上述分析可知，物流配送中車輛路徑優(yōu)化問題關(guān)系到物流配送的成本、效率等，關(guān)系到客戶的滿意度，是現(xiàn)階段物流行業(yè)關(guān)心的問題之一。本文提出了一種基于蟻群算法的物流配送中車輛路徑優(yōu)化方式，基于蟻群算法的魯棒性、快速性等特點(diǎn)，短時(shí)間找出最短的配送路徑。并且通過仿真實(shí)驗(yàn)證明了，本文提出的優(yōu)化算法有效性極高，值得在物流行業(yè)中大范圍的使用與推廣。

表1

表2

[1]章兢，周泉.基于免疫克隆算法的物流配送車輛路徑優(yōu)化研究[J].湖北大學(xué)學(xué)報(bào)，2012,28(2):114-115.

[2]亓霞，陳森發(fā)，黃鵾.基于免疫算法的物流配送車輛路徑優(yōu)化問題研究[J].土木工程學(xué)報(bào)，2013,26(3):99-100.

[3]尚華艷.物流配送中車輛路徑問題研究[J].武漢理工大學(xué)，2013,14(4):63-64.

[4]荊海霞.物流配送中雙向運(yùn)輸車輛路徑優(yōu)化問題研究[J].武漢大學(xué)學(xué)報(bào)，2013,26(6):54-55.

[5]曹二保.物流配送車輛路徑問題模型及算法研究[J].湖南大學(xué)學(xué)報(bào)，2013,18(9):247-248.

[6]戴錫.車輛路線問題的二階段啟發(fā)式算法及其在現(xiàn)代物流配送中的應(yīng)用[J].復(fù)旦大學(xué)學(xué)報(bào)，2013,28(7):511-512.

[7]元興.物流配送中心車輛路徑優(yōu)化中的幾種算法研究[J].計(jì)算機(jī)仿真，2011,18(7):41-42.

[8]衛(wèi)田，范文慧.基于NSGAⅡ的物流配送中車輛路徑問題研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2013,28(3):110-111.

[9]鐘石泉.物流配送車輛路徑優(yōu)化方法研究[J].天津大學(xué)學(xué)報(bào)，2011,18(8):45-46.

[10]肖健梅，黃有方，李軍軍.基于離散微粒群優(yōu)化的物流配送車輛路徑問題[J].系統(tǒng)工程，2011,17(8):78-79.