基于改進(jìn)蟻群算法的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃方法

曾莎莉

（中國(guó)石油集團(tuán)川慶鉆探工程有限公司重慶運(yùn)輸總公司，重慶 400021）

0 引言

現(xiàn)代物流運(yùn)輸最關(guān)鍵的問(wèn)題就是從始發(fā)地到終點(diǎn)之間路徑的選擇，運(yùn)輸油耗是現(xiàn)代物流運(yùn)輸?shù)闹饕杀尽Ｔ谝?guī)定的時(shí)間內(nèi)選擇路程最短、路況最好的道路作為現(xiàn)代物流運(yùn)輸最優(yōu)路徑，以此將現(xiàn)代物流運(yùn)輸成本降到最低，這樣既能滿足客戶在運(yùn)輸時(shí)間方面的需求，還能使物流企業(yè)利益最大化。近年來(lái)，現(xiàn)代物流運(yùn)輸行業(yè)作為“第三利益源泉”，對(duì)經(jīng)濟(jì)發(fā)展的帶動(dòng)作用逐漸凸顯，物流行業(yè)在市場(chǎng)經(jīng)濟(jì)中的地位也有了明顯提高，如何選出最優(yōu)的物流運(yùn)輸路徑成為現(xiàn)代物流行業(yè)所面臨的重要難題。在最快時(shí)間選出現(xiàn)代物流運(yùn)輸最優(yōu)路徑，對(duì)降低現(xiàn)代物流運(yùn)輸成本、節(jié)省現(xiàn)代物流運(yùn)輸時(shí)間、提高現(xiàn)代物流運(yùn)輸服務(wù)質(zhì)量具有重要作用?，F(xiàn)代物流企業(yè)目前所采用的最優(yōu)路徑規(guī)劃方法在實(shí)際應(yīng)用中物流運(yùn)輸時(shí)間比較長(zhǎng)，尤其是對(duì)于井場(chǎng)貨物運(yùn)輸，運(yùn)輸路程比較長(zhǎng)，經(jīng)過(guò)的運(yùn)輸點(diǎn)比較多，現(xiàn)有的路徑規(guī)劃方法所規(guī)劃的路徑耗時(shí)較長(zhǎng)，無(wú)法滿足井場(chǎng)貨物運(yùn)輸時(shí)間需求。為此，本文提出基于改進(jìn)蟻群算法的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃方法。

1 基于改進(jìn)蟻群算法的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃方法設(shè)計(jì)

1.1 確定現(xiàn)代物流運(yùn)輸路徑?jīng)_突分流點(diǎn)

井場(chǎng)貨物運(yùn)輸過(guò)程中從起發(fā)地點(diǎn)到目的地點(diǎn)中間存在多個(gè)運(yùn)輸節(jié)點(diǎn)，現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃問(wèn)題就是對(duì)物流節(jié)點(diǎn)合理選擇的問(wèn)題，物流節(jié)點(diǎn)的物理屬性需要符合實(shí)際情況，也就是井場(chǎng)貨物運(yùn)輸路徑中所有的路徑節(jié)點(diǎn)不能出現(xiàn)沖突。以有向圖規(guī)劃理論作為理論基礎(chǔ)，對(duì)井場(chǎng)貨物運(yùn)輸路徑中的物理沖突分流點(diǎn)進(jìn)行確定。按照物流運(yùn)輸路徑交叉口到井場(chǎng)貨物運(yùn)輸起點(diǎn)的距離將物流運(yùn)輸節(jié)點(diǎn)進(jìn)行標(biāo)記，并建立井場(chǎng)貨物運(yùn)輸有向圖，在建立的有向圖中選取井場(chǎng)物流運(yùn)輸起點(diǎn)到終點(diǎn)的中間節(jié)點(diǎn)作為核心節(jié)點(diǎn)，用節(jié)點(diǎn)

G

表示，其代表井場(chǎng)貨物運(yùn)輸最優(yōu)路徑的中央位置。然后，在節(jié)點(diǎn)與節(jié)點(diǎn)之間設(shè)置物流方向，以此突出井場(chǎng)貨物運(yùn)輸路徑的單向性特征。將每個(gè)道路節(jié)點(diǎn)的真實(shí)屬性在有向圖中標(biāo)記，包括道路交叉口坐標(biāo)、交通方向等。最后，在有向圖中井場(chǎng)貨物運(yùn)輸路徑長(zhǎng)度需要與各個(gè)起始節(jié)點(diǎn)距離長(zhǎng)度呈對(duì)應(yīng)關(guān)系。在建立的井場(chǎng)貨物運(yùn)輸?shù)挠邢驁D中確定井場(chǎng)貨物運(yùn)輸路徑的沖突點(diǎn)，并將各個(gè)沖突點(diǎn)用節(jié)點(diǎn)

H

表示，在規(guī)劃井場(chǎng)貨物運(yùn)輸最優(yōu)路徑時(shí)不考慮沖突點(diǎn)作為最優(yōu)路徑節(jié)點(diǎn)，以此確保規(guī)劃的井場(chǎng)貨物運(yùn)輸最優(yōu)路徑中點(diǎn)位均衡，并且沒(méi)有路徑節(jié)點(diǎn)沖突。

1.2 現(xiàn)代物流運(yùn)輸最優(yōu)路徑問(wèn)題描述

井場(chǎng)貨物運(yùn)輸路徑規(guī)劃不僅要考慮到路徑交叉路口物理屬性，還要考慮到井場(chǎng)貨物運(yùn)輸?shù)缆烽L(zhǎng)度、運(yùn)輸時(shí)間、運(yùn)輸路徑路況等運(yùn)輸邏輯屬性。兩個(gè)相鄰的路徑節(jié)點(diǎn)連接形成有向圖節(jié)點(diǎn)路線，將相鄰路徑節(jié)點(diǎn)的距離、道路交通情況、道路運(yùn)輸時(shí)間等節(jié)點(diǎn)屬性值進(jìn)行標(biāo)準(zhǔn)化，以此確定井場(chǎng)貨物運(yùn)輸路線權(quán)值，按照權(quán)值大小將相鄰節(jié)點(diǎn)連接路線進(jìn)行排序，以此將上文建立的井場(chǎng)貨物運(yùn)輸有向圖轉(zhuǎn)化為帶權(quán)有向圖，其用公式（1）表示：

式（1）中，

A

表示井場(chǎng)貨物運(yùn)輸路徑帶權(quán)有向圖，

W

表示井場(chǎng)貨物運(yùn)輸路徑中所包含的路徑節(jié)點(diǎn)集合，[

B

]表示井場(chǎng)貨物運(yùn)輸路徑中所包含的連接兩個(gè)路徑節(jié)點(diǎn)的邊的集合。假設(shè)井場(chǎng)貨物運(yùn)輸路徑中所包含的路徑節(jié)點(diǎn)集合中的起始節(jié)點(diǎn)為

q

，井場(chǎng)貨物運(yùn)輸路徑中所包含的路徑節(jié)點(diǎn)集合中的終點(diǎn)節(jié)點(diǎn)為

p

，則現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃問(wèn)題可以描述為在貨物運(yùn)輸路徑帶權(quán)有向圖

A

中，選擇出從起始節(jié)點(diǎn)

q

到終點(diǎn)節(jié)點(diǎn)

p

的一條權(quán)值最小的路徑，且該路徑中不包含沖突點(diǎn)

H

。

1.3 基于改進(jìn)蟻群算法的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃

井場(chǎng)貨物運(yùn)輸最優(yōu)路徑規(guī)劃的問(wèn)題與蟻群覓食行為相似，因此現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃中常采用蟻群算法，通過(guò)蟻群之間信息傳遞來(lái)規(guī)劃現(xiàn)代物流運(yùn)輸最優(yōu)路徑。但是，蟻群算法所規(guī)劃的路徑在實(shí)際應(yīng)用中常出現(xiàn)道路不通暢的情況，此次對(duì)蟻群算法進(jìn)行改進(jìn)，利用改進(jìn)蟻群算法規(guī)劃現(xiàn)代物流運(yùn)輸最優(yōu)路徑。

將井場(chǎng)貨物運(yùn)輸起點(diǎn)

q

作為蟻群尋找食物起點(diǎn)，即螞蟻巢穴，將井場(chǎng)貨物運(yùn)輸終點(diǎn)

p

作為螞蟻所尋找食物地點(diǎn)，蟻群在尋找事物過(guò)程中根據(jù)自身?xiàng)l件和外部條件的變化隨時(shí)更換路線，假設(shè)螞蟻共有

n

只，每只螞蟻尋找食物的路徑用公式（2）表示：

式（2）中，

h

表示螞蟻尋找食物路徑，

n

表示螞蟻的數(shù)量，

s

表示螞蟻從螞蟻巢穴到節(jié)點(diǎn)

i

之間的距離，

s

表示螞蟻從節(jié)點(diǎn)

i

到食物之間的距離。利用公式（2）表示螞蟻尋找食物的路徑。將運(yùn)輸時(shí)間、運(yùn)輸成本及路暢程度作為約束條件，從眾多螞蟻覓食路徑中選取運(yùn)輸時(shí)間最短、成本最低、路暢最好的路徑作為最優(yōu)路徑，其中運(yùn)輸時(shí)間約束條件用公式（3）表示：

式（3）中，

t

(

j

)表示螞蟻覓食時(shí)間因子，

t

表示螞蟻覓食路徑所需時(shí)間，

t

表示螞蟻覓食過(guò)程中允許的最長(zhǎng)時(shí)間上限。該約束條件中，螞蟻覓食路徑所需時(shí)間

t

不能超過(guò)螞蟻覓食過(guò)程中允許的最長(zhǎng)時(shí)間上限

t

。運(yùn)輸成本約束條件用公式（4）表示：

式（4）中，

l

(

j

)表示螞蟻覓食所消耗體力因子，即經(jīng)常貨物運(yùn)輸成本因子；

f

表示螞蟻覓食路徑所需要消耗的體能，即井場(chǎng)貨物運(yùn)輸所需要的運(yùn)輸成本；

f

表示螞蟻覓食過(guò)程中允許的最大消耗體能，即井場(chǎng)貨物運(yùn)輸最大預(yù)估運(yùn)輸成本。該約束條件中，螞蟻覓食路徑所需要消耗的體能不能超過(guò)螞蟻覓食過(guò)程中允許的最大消耗體能。路暢約束條件用公式（5）表示：

式（5）中，

r

(

j

)表示螞蟻覓食路徑路暢因子；

r

表示螞蟻覓食路徑實(shí)際路暢程度，即井場(chǎng)貨物運(yùn)輸實(shí)際路暢程度；

r

表示螞蟻覓食過(guò)程中路暢最低容忍度，即井場(chǎng)貨物運(yùn)輸所能允許的最差路暢程度。按照以上3 個(gè)約束條件對(duì)每個(gè)螞蟻覓食路徑進(jìn)行約束，選擇出符合上述3 個(gè)約束條件的路徑，在符合條件的路徑中對(duì)每個(gè)路徑的時(shí)間、成本、路暢3 個(gè)指標(biāo)權(quán)重進(jìn)行確定，然后按照權(quán)重從大到小的順序?qū)β窂竭M(jìn)行排序，以權(quán)重最大的路徑作為螞蟻覓食最優(yōu)路徑，以此結(jié)束改進(jìn)蟻群算法運(yùn)算。將計(jì)算到的路徑在上文建立的井場(chǎng)貨物運(yùn)輸有向圖中進(jìn)行標(biāo)識(shí)，作為井場(chǎng)貨物運(yùn)輸最優(yōu)路徑，以此完成基于改進(jìn)蟻群算法的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃。

2 實(shí)驗(yàn)論證分析

實(shí)驗(yàn)以某井場(chǎng)貨物作為實(shí)驗(yàn)對(duì)象，將井場(chǎng)貨物從井場(chǎng)分別運(yùn)輸?shù)紸、B、C、D、E、F、G、H 8 個(gè)地點(diǎn)，利用此次設(shè)計(jì)方法與傳統(tǒng)方法對(duì)該井場(chǎng)貨物運(yùn)輸最優(yōu)路徑進(jìn)行規(guī)劃。建立了8 個(gè)井場(chǎng)貨物運(yùn)輸有向圖，節(jié)點(diǎn)數(shù)量分別為11 個(gè)、14 個(gè)、16 個(gè)、15 個(gè)、18 個(gè)、19個(gè)、18 個(gè)、21 個(gè)，沖突節(jié)點(diǎn)數(shù)量分別為3 個(gè)、2 個(gè)、6個(gè)、4 個(gè)、3 個(gè)、1 個(gè)、2 個(gè)、4 個(gè)，利用公式（2）對(duì)每個(gè)井場(chǎng)貨物運(yùn)輸路徑進(jìn)行確定，再利用約束條件對(duì)路徑進(jìn)行約束，根據(jù)實(shí)際情況確定每個(gè)路徑的權(quán)值，最終選擇了最優(yōu)路徑，具體情況如表1 所示。

表1 井場(chǎng)貨物運(yùn)輸最優(yōu)路徑

按照規(guī)劃的物流運(yùn)輸路徑對(duì)井場(chǎng)貨物進(jìn)行運(yùn)輸，對(duì)兩種方法規(guī)劃路徑的實(shí)際運(yùn)輸時(shí)間進(jìn)行記錄，將其作為實(shí)驗(yàn)數(shù)據(jù)，對(duì)兩種方法的可靠性和有效性進(jìn)行評(píng)價(jià)，實(shí)驗(yàn)結(jié)果如表2 所示。

表2 兩種方法應(yīng)用下物流運(yùn)輸時(shí)間對(duì)比

從表2 的數(shù)據(jù)中可以看出，車輛按照此次設(shè)計(jì)方法規(guī)劃的物流運(yùn)輸路徑所花費(fèi)的運(yùn)輸時(shí)間比較短，可以在規(guī)定時(shí)間內(nèi)將貨物運(yùn)輸?shù)街付ǖ攸c(diǎn)，最快的貨物運(yùn)輸時(shí)間提前了43 min；車輛按照傳統(tǒng)方法規(guī)劃的物流運(yùn)輸路徑所花費(fèi)的運(yùn)輸時(shí)間遠(yuǎn)遠(yuǎn)長(zhǎng)于設(shè)計(jì)方法，并且沒(méi)有在規(guī)定時(shí)間內(nèi)將貨物運(yùn)輸?shù)街付ǖ攸c(diǎn)，超時(shí)的最長(zhǎng)時(shí)間為117 min。這是因?yàn)楸疚奶岢龅幕诟倪M(jìn)蟻群算法的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃方法在考慮到路徑問(wèn)題的同時(shí)還考慮了物流運(yùn)輸路況問(wèn)題，因此實(shí)驗(yàn)證明了此次設(shè)計(jì)方法能夠準(zhǔn)確規(guī)劃出現(xiàn)代物流運(yùn)輸最優(yōu)路徑，相較于傳統(tǒng)方法，基于改進(jìn)蟻群算法的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃方法的可靠性和有效性更好。

3 結(jié)語(yǔ)

此次利用改進(jìn)蟻群算法設(shè)計(jì)了一種新的現(xiàn)代物流運(yùn)輸最優(yōu)路徑規(guī)劃方法，對(duì)井場(chǎng)運(yùn)輸時(shí)間、成本及路況進(jìn)行約束，尋找出路徑最短、路況最好、成本最低的路徑作為物流運(yùn)輸最優(yōu)路徑，有助于降低現(xiàn)代物流運(yùn)輸成本，縮短井場(chǎng)貨物運(yùn)輸時(shí)間，實(shí)現(xiàn)在規(guī)定時(shí)間內(nèi)將貨物運(yùn)輸?shù)揭?guī)定地點(diǎn)。由于個(gè)人水平有限，本文提出的規(guī)劃方法尚未在現(xiàn)代物流運(yùn)輸路徑規(guī)劃中進(jìn)行大量實(shí)踐應(yīng)用，對(duì)于改進(jìn)的蟻群算法可能存在不足之處，今后仍會(huì)在該方面進(jìn)行深入研究，為現(xiàn)代物流運(yùn)輸行業(yè)發(fā)展提供可靠的理論支撐。