基于改進蟻群的物流配送路徑優(yōu)化調度方法

杜 靜

（晉中職業(yè)技術學院電子信息學院 山西 晉中 030600）

0 引言

物流配送路徑調度是物品配送過程中一個非常重要的環(huán)節(jié)，作用是對物品配送路徑進行合理的規(guī)劃和設計，根據(jù)設計好的路徑將物品配送到目的地。物流配送路徑調度關系到物流配送成本、物品運輸質量、運輸安全以及物流配送服務質量，最理想的物流配送路徑為路程最短、配送時間最短、物品運輸過程中不會發(fā)生損壞、路況最好，要想達到理想的物流配送路徑需要對其進行合理的優(yōu)化調度。目前現(xiàn)行的調度方法是采用傳統(tǒng)蟻群算法對配送信息進行分析，得出優(yōu)化調度策略，該方法在實際應用中求解出的優(yōu)化調度策略并非最優(yōu)解，實施蟻群算法求出的優(yōu)化調度策略后物流配送成本比較高，并且超出物流配送成本預算，為此提出基于改進蟻群的物流配送路徑優(yōu)化調度方法研究[1]。

1 基于改進蟻群的物流配送路徑優(yōu)化調度方法

此次在傳統(tǒng)方法基礎上對蟻群算法進行改進，得到一個新的調度思路，首先建立物流配送路徑調度數(shù)學模型，對物流車輛運輸路徑進行選擇和制定過程進行描述；然后以時間最短、成本最低、運輸車輛行駛安全性越高為目標，建立優(yōu)化目標函數(shù)，對模型進行優(yōu)化；為了便于改進蟻群算法求得最優(yōu)解，對設計的優(yōu)化目標函數(shù)設定約束條件，包括物流配送成本約束、車輛數(shù)量約束，以及車輛行駛距離約束和客戶節(jié)點數(shù)量約束；最后根據(jù)目標點自適應調整啟發(fā)函數(shù)，對蟻群算法進行改進，并利用改進后的蟻群算法對目標函數(shù)進行求解，得出最優(yōu)物流配送路徑優(yōu)化調度策略[2-3]。

1.1 建立物流配送路徑調度數(shù)學模型

物流配送路徑調度是指物品運輸車輛從物流配送區(qū)發(fā)出，將物品運輸?shù)娇蛻糁付ǖ攸c，然后再返回到物流配送區(qū)，這一過程利用數(shù)學模型描述[4]。由于物流配送路徑與物品運輸距離具有一定的線性關系，可以利用這一線性關系得出物流配送最短路徑，以此降低物流運輸成本。客戶對物流配送時間具有一定的要求，其用公式表達為：

公式（1）中，Tis表示物流配送規(guī)定時間窗在配送地點i的起始時間；i表示物流配送路徑終點，即物流配送最終地點；xi表示物流配送終點的決策變量；di表示物流運輸車輛在運輸過程中在某一地點停留或者延誤的時間；Tie表示物流配送規(guī)定時間窗在配送地點i的終止時間，即物流配送最晚規(guī)定時間，上述公式為物流配送路徑調度數(shù)學模型的時間描述[5]。建立物流配送路徑調度數(shù)學模型如下：

式中，F(xiàn)表示物流配送路徑調度數(shù)學模型，k表示物流配送路徑中為多個用戶配送貨物，H表示物流配送路徑路段組成的集合，G表示由交通節(jié)點和用戶節(jié)點組成的網(wǎng)絡路徑節(jié)點集合，J表示物流配送路徑的容積，D表示物流配送路徑規(guī)定貨物載重。該模型為后續(xù)改進蟻群算法求解模型，為優(yōu)化目標函數(shù)和約束條件的設計提供基礎。

1.2 設計優(yōu)化目標函數(shù)

在上述數(shù)學模型基礎上建立優(yōu)化目標函數(shù)，對模型進行優(yōu)化。影響物流配送路徑調度的因素主要為配送時間、安全性、配送成本、路況，根據(jù)物流配送路徑優(yōu)化調度需求，設定3個優(yōu)化目標分別為物流配送時間最短、成本最低、運輸車輛行駛安全性最高，由于在實際中是無法實現(xiàn)物流配送路徑都能滿足以上3個條件，根據(jù)重要性在后續(xù)求解中將物流運輸成本放在第一位，其次是時間最短和運輸車輛行駛安全性最高。

（1）配送成本最低優(yōu)化目標函數(shù)：物流配送成本主要由物流配送距離、物流配送車輛等因素決定，因此該優(yōu)化目標函數(shù)用公式表示為：

公式（3）中，minX表示配送成本最低優(yōu)化目標函數(shù)；X0表示物流配送區(qū)開設費用；Q表示物流配送區(qū)到客戶節(jié)點之間的距離，即配送車輛行駛路程；P表示目前市場上燃油平均價格；R表示物流配送成本與配送車輛行駛路程的轉換矩陣；α表示物流配送交通道路條件對車輛行駛影響而產(chǎn)生的額外費用。

（2）配送時間最短優(yōu)化目標函數(shù)：物流配送時間的長短與車輛行駛速度和路況等因素決定，假設物流配送時間為t，以時間最短建立優(yōu)化目標函數(shù)：

式中，t1表示車輛從物流配送區(qū)到客戶節(jié)點，卸完貨后返回到物流配送區(qū)，兩段行駛路途上所用的總時間；t2表示配送車輛到達客戶節(jié)點卸貨時間。rij表示車輛從物流配送路徑節(jié)點i到節(jié)點j行駛時間；Nij表示決策變量；S表示車輛行駛平均速度；?表示物流配送路徑節(jié)點i到節(jié)點j之間路況條件對車輛正常行駛的影響系數(shù)；qijk表示車輛運輸能力與客戶獲取需求量之間的轉換系數(shù)，通常情況下該系數(shù)取值為1.5[6]。o表示物流配送貨物總量；p表示卸貨工人卸貨效率；z表示卸貨人數(shù)。

（3）配送安全性最高優(yōu)化目標函數(shù)：以車輛行駛安全系數(shù)最高為目標建立函數(shù)如下：

公式（5）中，η表示車輛行駛安全系數(shù)；ψ表示物流配送車輛從節(jié)點i到節(jié)點j安全通過概率；α表示物流配送路徑中各個道路交通事故發(fā)生概率。

1.3 設立約束條件

為了有效控制物流配送成本，物流企業(yè)在對貨物配送之前都需要對物流配送成本進行預算，因此設定的成本約束條件為：物流配送成本不得超過成本預算，用公式表示為：

公式（6）中，X0表示物流配送成本預算。貨物在配送中可以使用一臺車輛為多個客戶進行貨物配送，如果配送貨物量比較多，可以由多臺車輛對貨物進行配送，但是不能超過物流配送區(qū)未配送車輛數(shù)量，即：

公式（7）中，k表示貨物配送客戶數(shù)量；yk表示客戶貨物由y輛車完成配送任務；y0表示物流配送區(qū)未配送車輛數(shù)量；yp表示物流配送需要使用的車輛數(shù)量。運輸車輛從物流配送區(qū)出發(fā)達到客戶節(jié)點，沒完成一次物流配送任務，參與到物流配送活動中的車輛行駛距離不能超出物流配送最大路徑，即：

公式（8）中，L表示物流配送最大路徑；fi表示車輛從物流配送區(qū)中心到第一個客戶節(jié)點的距離；ai表示物流配送路徑上兩個相鄰客戶節(jié)點的距離。對于物流配送客戶數(shù)量的約束為：物流配送路徑上客戶節(jié)點數(shù)量不能超過總的客戶數(shù)量，同時每輛車負責的客戶數(shù)量不能小于總的客戶數(shù)量即：

公式（9）中，κ*表示物流配送路徑上客戶節(jié)點數(shù)量；κ表示物流配送總的客戶數(shù)量；κ0表示每輛車負責的客戶數(shù)量。利用上述約束條件對優(yōu)化目標函數(shù)進行約束。

1.4 基于改進蟻群的目標函數(shù)求解

根據(jù)設定的約束條件對上文設計的優(yōu)化目標函數(shù)進行求解，可以得出多個物流配送路徑優(yōu)化調度策略，建立解集Y，利用改進蟻群算法對解集Y中所有優(yōu)化調度策略進行分析，求出最優(yōu)解輸出。

假設路徑上每個配送車輛為一個蟻群，將蟻群尋找食物的路徑定義為物流配送路徑，路徑上每個客戶階段為蟻群覓食的食物節(jié)點，蟻群按照每個策略中物流配送路徑進行覓食運動。螞蟻在某一時刻從節(jié)點i到節(jié)點j移動的概率定義為：

公式（10）中，Pij(t)表示螞蟻在某一時刻從節(jié)點i到節(jié)點j移動的概率；ξij表示在時刻t時路徑從節(jié)點i到節(jié)點j上殘留的信息素濃度；υij表示螞蟻后續(xù)移動節(jié)點的啟發(fā)函數(shù)；α表示啟發(fā)函數(shù)對螞蟻移動方向改變概率的影響權值；β表示蟻群移動路徑上信息素濃度對移動方向改變概率的影響權值[7]。在傳統(tǒng)螞蟻算法中螞蟻移動路徑上兩個相鄰節(jié)點的啟發(fā)權值差異不明顯，導致傳統(tǒng)蟻群算法搜索效率比較低?？紤]到該問題對螞蟻算法進行改進，已知螞蟻最終移動節(jié)點位置，得到路徑上其他節(jié)點到目的節(jié)點的距離f，按照f值大小對路徑節(jié)點的啟發(fā)權值進行自適應調整，以此提高螞蟻算法的搜索效率[8]。每條覓食路徑上都含有一定的信息素，信息素被限定在特定區(qū)間內(nèi)，每條路徑上的信息素初始化為區(qū)間上限τmax，通過對路徑上的信息素進行不斷更新，淘汰掉信息素較少的路徑，其更新規(guī)則為：

公式（11）中，M表示路徑上蟻群數(shù)量；χ表示路徑節(jié)點的啟發(fā)權值；δ表示路徑信息素揮發(fā)系數(shù)；?τBEST表示蟻群在該路徑中遍歷食物節(jié)點后所經(jīng)路徑的總長。利用上述公式對路徑上信息素進行更新，按照更新后信息素的多少對路徑進行排序，去除掉排在最后一個路徑。然后再用上述公式對路徑信息素進行更新，直到路徑列表中只剩下一條路徑為止[9]。

2 實驗論證分析

實驗以某物流公司為實驗對象，該物流公司配送區(qū)域共8個，并且包含7個銷售點。此次實驗收集了上個月1000多條配送信息，信息內(nèi)容包括配送區(qū)中心位置、銷售點位置、配送量、配送時間、配送車輛數(shù)量、配送車輛行駛速度等，具體數(shù)據(jù)見表1。

表1 物流配送信息表

以表1中數(shù)據(jù)作為物流配送路徑優(yōu)化調度計算依據(jù)，得出每次配送路徑優(yōu)化調度策略。此次實驗分8次完成，將每次優(yōu)化調度后物流配送成本進行記錄，將其作為檢驗此次設計方法有效性的指標，并將其與成本預算和傳統(tǒng)方法配送成本進行對比分析，見表2。

表2 兩種方法應用下物流配送成本對比 單位：元

從表2中數(shù)據(jù)分析可以得出以下結論：應用此次設計方法物流運輸成本沒有超出成本預算，可以將物流配送成本控制在預算之內(nèi)，最低配送成本低于預算26.45%，這是因為此次設計方法，是在原有的物流配送路徑調度模型基礎上，以成本最低為目標建立優(yōu)化目標函數(shù)，并利用約束條件對目標函數(shù)求解進行約束，最后使用改進后的蟻群算法求出最優(yōu)策略，使物流配送成本得到有效控制。而應用傳統(tǒng)方法得出的優(yōu)化調度策略的實施，物流配送成本遠遠超出成本預算，最高超出成本預算46.15%，相比較設計方法物流配送成本偏高。

3 結語

此次利用改進后的蟻群算法對物流配送路徑優(yōu)化調度進行計算分析，形成一套新的調度方法，實現(xiàn)了對傳統(tǒng)方法的優(yōu)化和創(chuàng)新，通過實驗論證了該方法可以有效將配送成本控制在預算之內(nèi)，對降低物流企業(yè)配送成本，保證物流配送安全性以及提高物流配送服務水平具有一定的現(xiàn)實意義。