基于改進蟻群算法的物流配送車輛路徑優化方法

濮明月，張彥如

(1.安徽新華學院 商學院，安徽 合肥 230088；2.合肥工業大學 機械工程學院，安徽 合肥 230009)

物流配送是物流系統中的重要環節，在企業配送過程選擇一個合理的路徑規劃能夠降低物流成本，提高自身的核心競爭力，尤其是生鮮等容易腐敗產品的運送，冷鏈運輸成本較高，如果路徑規劃不當，會造成很大的貨損和較高的運輸成本，因此對物流配送車輛路徑進行優化十分必要[1-2].

在傳統的路徑優化方法中，僅僅考慮到運輸過程中的成本和損耗，忽略了客戶時間窗約束產生的懲罰成本，導致物流路徑的優化效果并不理想，因此設計一種基于改進蟻群算法的物流配送車輛路徑優化方法.引入時間窗的懲罰機制，科學、合理地解決物流配送路徑優化問題，對物流配送車輛路徑進行合理規劃，盡量減少配送過程中的懲罰成本和貨損成本，壓縮運輸損失.

1 物流配送車輛路徑優化方法

1.1 蟻群算法的改進

蟻群算法實際上是模仿螞蟻的覓食行為來尋找最優路徑，基于蟻群的個體數量龐大，它們之間通過信息素進行溝通，為同伴傳遞信息，大量的螞蟻形成一個反饋系統，因而具有較高的效率和時間復雜度，有效解決了尋找食物的問題[3-4].研究的是物流車輛的路徑優化，主要目標是縮短配送距離，降低成本，為企業創造更高的利潤.蟻群算法是一種基于種群的進化算法，將其應用在路徑優化中，剛開始所有的蟻群會選擇不同的路徑尋找食物，在搜索過程中，蟻群會靠信息素進行溝通，選擇較優的路徑進行二次食物尋找，如此反復迭代，會尋找到一條最優路徑，其路徑搜索過程如圖1所示.

圖1 蟻群覓食路徑擇優過程

蟻群算法具有很好的搜索能力，但是它的初始信息速匱乏，收斂速度比較慢，因此將蟻群算法和遺傳算法相結合，提出改進的混合蟻群算法進行迭代求解.結合蟻群算法，得到路徑優化問題的算法流程，如圖2所示.

圖2 改進蟻群算法流程

以上算法的改進主要體現在信息素的更新步驟上.

主要待解決問題的目標為路徑的最優解.為更新信息素，假定蟻群中的蟻群數量為n，物流配送終點客戶z和x的距離為dzx，且設定為客戶之間的親密程度，即為可見度.在某時刻t的某蟻群到z客戶之間的不可逆移動概率計算公式為：

(1)

公式(1)中，B為蟻群沒有達到的客戶集合，根據這個過程的不斷調整，得到路徑的信息素更新結果為：

(2)

公式(2)中的β為信息殘留程度.

在路徑信息素的更新基礎上，建立在基因編碼上進行遺傳算法的選擇、交叉和編譯3個遺傳操作.采用模仿染色體編碼的方法對配送路徑進行編碼，得到一組自然數組成的配送方案編碼，選擇的核心思想是復制，復制繼承父代中的最優解繼續改進，避免優質解丟失，交叉可以產生新個體，增加多樣性，防止早熟停滯，對最優個體進行變異操作，保存最優解.

1.2 基于改進蟻群算法的物流配送車輛路徑優化建模

路徑優化問題中，主要包括物流配送中心、需求地點、貨物、車輛、約束條件和目標函數等要素構成.在實際的物流配送過程中，會存在一個車輛實際載重問題，假設在一次配送過程中，有K輛車共同配送到N個需求地點，第i個地點對于運送貨物的需求量為mi，每輛車的最大載重設為Q，需求點i到需求點j的距離表示為dij，車輛的平均行駛速度為s，需求點i要求貨物到達的最早時間表示為ai，要求貨物到達的最晚時間表示為bi，第i輛車的配送路線上需求點的數量表示為nk，那么研究問題最優蟻群目標函數可以表示為：

(3)

若第k輛車從需求點i行駛到了到需求點j，那么xijk的值為1，否則為0[5-6].針對上述的目標函數做出假設，設定的配送中心僅有一個且位置確定不變，配備足夠的產品和物流配送車輛，所有的配送車輛都需要送配送中心出發，最后再返回配送中心，方便對物流車輛進行下一次的調度管理，所有的需求點位置已知且固定不變，根據上述條件，能夠得到目標函數的約束條件為：

(4)

公式(4)中L為客戶總數.在配送過程中，若第k輛車完成需求點i的配送服務，那么yik的取值為1，否則為0[7-8].在約束條件中，對配送過程進行相關的配送約束，約束條件中的第1個約束公式表示每個需求點有且僅有1次配送服務，也就是說只能由一輛車進行配送；第2個約束公式表示每輛車的配送路線上所有需求點的貨物需求量總和不能超過車輛的最大載重；第3個公式表示配送車輛的出發地點都必須在配送中心；第4個公式表示配送車輛完成配送后都必須回到配送中心.

1.3 物流配送成本

在物流配送的過程中，為保證配送物品的新鮮與完整，配送的成本一般包括固定成本和變動成本.固定成本主要是指與車輛有關的購置費、折舊費以及開車司機和裝卸工人的工資等，固定成本是在進行配送服務之前就已經產生了，與后續的配送路程沒有關系，且固定成本是由配送車輛的數目決定的[9-11].變動成本包含的項目比較多，主要包括運輸成本、貨損成本、懲罰成本以及生鮮類商品需要冷鏈運輸的制冷成本[12-13].對物流配送車輛路徑進行優化的主要目的就是要降低變動成本，其中的運輸成本主要是指商品在運輸過程中所產生的費用，包括燃油費以及制冷費等與車輛行駛的距離和時間成正比，可以表示為：

(5)

式(5)中，B代表所有需求點的集合；U代表所有車輛的集合；Ck表示運輸車輛單位里程的運輸成本.當車輛k從需求點i行駛到需求點r時，zirk為1，否則為0,貨損成本可以表示為：

(6)

式(6)中，ρ1表示配送產生的貨損比例；ρ2表示卸貨貨損比例；C0表示單位商品的價值；tirk表示車輛k從需求點i到r的行駛時間.當車輛k完成對需求點r的配送時，yrk為1，否則為0.制冷成本可以表示為[14-15]：

(7)

式(7)中，α0表示車體劣化程度；E為熱傳導率；Sout、Sin分別表示車體的外、內表面積；Tout、Tin分別表示車體的外、內溫度；p為制冷劑價格.運送的懲罰成本可以表示為：

C5=δC0Mi.

(8)

式(8)中，δ為懲罰因子；Mi表示需求點i的缺貨數量.根據上述的成本計算公式，能夠清晰地計算出物流配送過程中的固定成本和變化成本.對于路徑的優化有很好的參考作用.

至此完成基于改進蟻群算法的物流配送車輛路徑優化.

2 算例分析

2.1 數據來源

算例分析以某連鎖生鮮經營企業的物流配送為例，選取生鮮作為算例中的配送產品，由配送中心對編號1-18門店進行冷卻生鮮配送.目標是優化配送中心生鮮的車輛配送路徑，將物流的配送成本降到最低.配送中心以及各個門店的地理位置如圖3所示：

圖3 配送中心和各個門店的地理分布圖

圖3中，標號為0的地標代表配送中心，標號1～18代表18家門店，配送中心在對各個門店進行生鮮產品配送時，要保證在規定時間內送達，且需要保證供應數量，否則會給該門店造成一定損失，配送要受到懲罰.因此在進行路徑規劃時，需要對生鮮商品需求量以及約定的服務時間窗進行設置，如表1所示.

表1 各門店生鮮商品需求量以及時間窗

2.2 實驗結果分析

在分別對算例進行100次求解后，最終得到了傳統文獻[3]方法和所提方法的最優配送路徑，如圖4所示：

(a)文獻[3]方法

(b)所提方法圖4 不同配送路徑對比

圖4(a)為傳統方法最終得到的最優路徑；圖4(b)為所提方法最終得到的最優路徑.對這兩種配送路徑進行成本分析，如表2所示：

表2 路徑成本分析

在路徑分析中，考慮了5種成本進行路徑優化，在實際應用中的約束效果更好，得到的最優路徑能夠明顯的節省運輸成本，提高收益；懲罰成本是從各個門店的視角出發，能夠體現配送滿意度.

在驗證所提方法的成本約束基礎上，為更直觀測試不同方法的物流配送車輛路徑的有效性，以耗時為實驗指標進行實驗結果輸出.假定本次實驗中所有物流運輸車輛的車速一致，其耗時越低，則說明其路徑越短，優化效果越好，具體實驗結果如圖5所示：

待配送門店數量/個圖5 不同方法的路徑耗時對比

由圖5的實驗結果可以看出，隨著待配送門店數量的增多，兩種方法的路徑耗時不斷增加.但是很明顯，所提方法的耗時始終低于文獻[3]方法，且門店數量達到300個以上時，耗時的增量較小.通過以上實驗結果可以得出結論：使用設計的方法對物流配送車輛路徑進行優化，在滿足車輛容量約束、時間窗約束和懲罰約束的情況下，能夠得到總成本最低的物流配送路徑方案.

3 結 論

物流車輛的入境規劃是物流配送的關鍵，基于傳統路徑規劃方法的缺陷，將蟻群算法與遺傳算法進行結合設計了一種新的物流車輛配送路徑優化方法.實驗結果表明，所設計方法對路徑進行優化后，能夠有效地降低變動成本.但是研究還有一些不足之處，建立的模型約束條件相對于實際情況考慮的不夠全面，例如交通方面出現突發狀況時，缺乏實際的調度能動性，在今后的研究中需要進一步解決.