張 偉

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

ZHANG Wei

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

0 引言

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

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

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

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

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

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

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

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

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

圖1 是蟻群路徑搜索過(guò)程圖：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

采用專(zhuān)業(yè)的仿真計(jì)算機(jī)平臺(tái)，平臺(tái)主要為3.4GMHz 的CPU、4G 內(nèi)存，Windows2007 操作系統(tǒng)，在VB6.0 語(yǔ)言環(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)路徑的長(zhǎng)度通過(guò)計(jì)算得到為165。

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

6 總結(jié)

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

表1

表2

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

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

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

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

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

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

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

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

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

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