基于混合蟻群的多溫區(qū)冷鏈物流配送路徑優(yōu)化算法

解永亮

(內蒙古工業(yè)大學 航空學院， 呼和浩特 010051)

隨著我國經濟水平的不斷提升，食品品質受到了更多的關注[1-2].新零售概念的出現(xiàn)促進了現(xiàn)代物流行業(yè)的進一步快速發(fā)展，尤其是冷鏈技術與冷鏈物流技術的不斷突破，極大地保障了生鮮電商的長久發(fā)展[3].

冷鏈物流是將冷凍工藝學與物流運輸相結合，利用制冷及保溫等技術手段以達到在低溫或不同溫度環(huán)境下運輸貨物的目的.通常，根據(jù)貨物的種類、數(shù)量及運送距離的不同，冷鏈物流的形式也有所區(qū)別[4-5].在整個冷鏈物流過程中，路徑優(yōu)化問題是影響貨物配送效率的最關鍵問題之一.在多溫區(qū)冷鏈物流配送過程中，車輛路徑的規(guī)劃經常受到多種因素的約束，進而影響了多溫區(qū)冷鏈物流的配送時間、配送成本和配送風險.多溫區(qū)冷鏈物流的車輛路徑規(guī)劃可分為以下兩類：1)僅針對單純送貨或者取貨的車輛路徑規(guī)劃問題；2)送貨、取貨一體化的車輛路徑規(guī)劃問題[6-9].

目前，已有眾多學者針對這一領域研究取得了一定成果.張濟風、康凱、施文嘉等人通過分析我國冷鏈物流企業(yè)現(xiàn)階段管理模式，總結出影響冷鏈物流發(fā)展的因素[10-12].孔志學等[13]利用最優(yōu)分割法來確定第一級配送路徑，從而確定了中轉站的個數(shù)和位置，并在此基礎上得到第二級配送路徑.該方法能得到較高的日均轉載率，但其缺點也較為明顯：單車裝載率較低.姜濤[14]在插入法中融入時差的概念，開展了帶有時間窗約束要求、同時取送貨配送車輛路徑算法的研究.

本文在蟻群算法的基礎上，融入了粒子群算法優(yōu)勢，構建面向多溫區(qū)冷鏈物流的混合蟻群車輛路徑優(yōu)化算法，以此來解決帶時間窗和同時取、送貨的問題.

1 問題描述與建模

送貨、取貨一體化的車輛路徑規(guī)劃問題可簡單理解為：在某個特定的配送中心派出多個配送車輛并為多個目標客戶進行貨物配送服務，且目標客戶均有一定量的送貨與取貨需求.與單純送貨、取貨車輛路徑規(guī)劃問題不同的是，送貨、取貨一體化的車輛路徑規(guī)劃問題還需要考慮任何目標客戶的送貨、取貨綜合需求不能超出該車輛的總運載能力Q.考慮到在實際物流配送過程中，通常受到一定的時間限制，因此帶時間窗的同時取、送貨車輛路徑規(guī)劃問題是更加具有現(xiàn)實意義的研究課題[15].本文采用兩個種群混合策略，并進行線性結合，從而對多溫區(qū)冷鏈物流的車輛路徑優(yōu)化模型構造初始可行解及局部搜索方法.

為了便于問題描述與模型構建，本文假定冷鏈物流過程僅考慮一個配送中心站點.該配送中心站點使用M輛運載能力為Q的配送車來滿足n個客戶的送貨和取貨任務，其中，配送車輛的行駛速度為固定值.帶時間窗的同時取、送貨車輛路徑規(guī)劃問題被描述成如下過程：1)若干輛配送車從配送中心站出發(fā)，完成取貨、送貨后再返回配送中心站；2)每一個客戶均有一個取貨點和送貨點；3)配送車輛需在配送中心站裝好貨物后在規(guī)定的時間窗內將貨物送達，并將客戶的貨物取回；4)車輛路徑規(guī)劃目標為配送站以最小的成本(選擇最少的車輛使用費用、最短的行駛費用以及取貨、送貨服務費用)完成任務.

根據(jù)上述描述過程，使用V={0，1，…，n}來表示客戶和配送站集合，其中，0代表配送中心站.假設U+代表取貨節(jié)點集合，U-代表送貨節(jié)點集合，而U為U+和U-的并集.c={1，2，…，M}表示參與冷鏈運輸任務的車輛集合.分別使用Sij和dij來表示從節(jié)點i到節(jié)點j的行駛費用與行駛距離.節(jié)點i到節(jié)點j既可以表示取貨節(jié)點，也可以表示送貨節(jié)點，因此它們的取值范圍為i=1，2，…，n和j=1，2，…，n.而ti表示在節(jié)點i進行服務所使用的時間，并且t0=0.使用[ei，li]來表示完成節(jié)點i任務的時間窗，其中，ei、li分別代表最早以及最晚開始工作的時刻.使用qi來表示配送車輛在節(jié)點i取完或送完貨后的貨物載重量.

根據(jù)以上假設，目標函數(shù)f被定義為

(1)

式中：表達式第一項為配送車輛的使用費用；第二項為車輛從節(jié)點i到節(jié)點j的行駛費用；第三項為在節(jié)點取貨、送貨的服務費用；a1、a2、a3分別為比例系數(shù)；Zijc為本次研究的決策變量，當某車輛c完成從節(jié)點i運行到節(jié)點j時，令Zijc=1，否則令Zijc=0；ti為配送車輛到達節(jié)點i的時刻.

為了保證配送車輛在指定的送貨、取貨節(jié)點完成先取貨、再送貨的工序，設定約束條件為

(2)

(3)

根據(jù)假設內容，所有車輛統(tǒng)一從配送中心開往客戶地址進行服務，完成客戶的取貨、送貨需求后再返回配送中心，由此得到對站點的約束條件為

(4)

(5)

考慮到配送車在執(zhí)行任務時，受限于每個客戶指定的時間進行送貨、取貨，因此需要增加時間窗對配送車的行為進行約束，即

(6)

式中，Uic、Dic分別為最佳服務時間的下限和上限.

2 同時取、送貨車輛路徑優(yōu)化

由于同時取貨、送貨增加了路徑優(yōu)化問題的求解維度[16]，為得到最優(yōu)解，本文將粒子群算法在多維度搜索空間方面的優(yōu)勢與改進后蟻群算法相結合，以此來構造初始可行解及局部搜索方法.

2.1 蟻群算法的路徑選擇

選擇合適的車輛行駛路徑，即選擇合適的客戶.與客戶之間的距離d和貨物量是約束路徑規(guī)劃的因素，設置變量ηij來表征客戶i、j被同一輛車服務的可能性，ηij被定義為

(7)

由于蟻群算法容易得到局部最優(yōu)解，本文使用多樣性搜索與確定性搜索相結合的方式來規(guī)避蟻群算法正反饋的影響，具體表達式為

(8)

(9)

式中：τij(t)為在t時(i，j)上的信息素；Pijc(t)為螞蟻c從節(jié)點i轉移到節(jié)點j的可能性；α為信息素的啟發(fā)因子；β為某節(jié)點客戶被選中的期望因子；PC為選擇概率，在螞蟻種群迭代過程中該值會發(fā)生改變；γ為縮小車輛行駛距離的必要性；θ為車載量與用戶取貨、送貨匹配程度φij的權重；ρ為趕往下一客戶的緊迫程度Tij的權重；A為可選擇的客戶節(jié)點集合.P處于[0，1]之間且均勻分布，當P≤PC時，為確定性搜索；當P>PC時，則為多樣性搜索.

2.2 帶時間窗的同時取、送貨車輛路徑優(yōu)化算法求解

盡管蟻群算法可作為路徑優(yōu)化算法進行路徑規(guī)劃，但其劣勢也不容忽視：1)在進行可行解優(yōu)化的過程中容易得到局部最優(yōu)解；2)優(yōu)化過程時間較長.針對以上兩個問題，利用粒子群算法尋求最優(yōu)解方面的優(yōu)勢，來減少最優(yōu)解搜索時間，并縮小求解空間以提高算法效率.粒子群算法的核心在于利用粒子的當前位置信息、全局極值以及個體極值，規(guī)劃出粒子下一次迭代后的位置信息.

將基于蟻群算法路徑規(guī)劃的4個參數(shù)α、β、ρ、γ作為粒子群的一個粒子，粒子的位置及速度可與參數(shù)相互轉.粒子群算法在優(yōu)化過程中，慣性權重會影響全局搜索的能力.當慣性權重較大時，可增強算法的全局搜索能力.通過粒子位置得到粒子參數(shù)后，初始化螞蟻子群的信息素，并計算相鄰位置節(jié)點之間的距離和車輛行駛時間.當螞蟻經過一條邊時，會更新該條邊上的信息素，具體更新表達式為

τ′ij=(1-ξ)τij+ξτ0

(10)

式中：ξ為信息素揮發(fā)率；τ0為初始信息素.

本文使用插入操作來構建帶時間窗，同時取、送貨車輛路徑問題的弱可行解，即隨機選擇一個客戶作為第一位要服務的目標，在進行第二名客戶服務之前，從滿足服務要求的客戶集合V中隨機挑選一個客戶k插入到正在進行的路徑當中.該客戶的插入，引發(fā)了信息素的變化，并按照車輛已裝載的容量和剩余容量來更新節(jié)點的最大服務量.

為避免蟻群算法因收斂速度過快而得到局部最優(yōu)解，本文使用交叉、反轉來優(yōu)化蟻群個體.在經過交叉、反轉等操作后，求出在滿足時間窗等約束條件下的最優(yōu)路徑方案Lopt.

交叉操作是指隨機選擇可行解中兩條路線r1、r2，將路線重疊的部分連接，保留對路線優(yōu)化有改善效果的交叉組合；而反轉則是調轉車輛的行駛方向，在不改變行駛路線長度的情況下，減少車輛裝載重量.

取Llocal、Lopt兩者最大值作為Llocal最新值，而該子群粒子的適應值被設定為螞蟻子群的最優(yōu)路徑，并更新螞蟻個體自身的最優(yōu)解，進而更新粒子的位置和速度.當所有子群螞蟻均得到局部最優(yōu)解后，信息素更新表達式為

(11)

式中：Cbest、Cworst為子群螞蟻尋找到的最優(yōu)及最差路徑；W為相關系數(shù).在所有子群信息素更新完成后，進行子群之間的信息素矩陣交換，得到交換數(shù)組，并進行交換操作.當滿足終止約束條件時，即得到全局最優(yōu)解.

3 實驗分析

為驗證本文所述方案的有效性和可行性，利用Visual C++6.0、MATLAB 7.0仿真平臺對基于混合蟻群的多溫區(qū)冷鏈物流配送路徑優(yōu)化算法進行驗證.實驗使用大小為200單元×200單元的平面區(qū)域進行路徑規(guī)劃.為比較本文所提算法(M1)的綜合性能，設置對照組進行驗證.對照組為基于改進的遺傳算法的車輛路徑優(yōu)化算法(M2)和基于禁忌搜索算法的車輛路徑優(yōu)化算法(M3).基于改進的遺傳算法車輛路徑優(yōu)化算法將傳統(tǒng)遺傳算法的交叉、變異操作進行改進，根據(jù)目標函數(shù)值的大小來劃分配對的個體；再基于給定的變異率，對個體相應位置的基因進行變異.將變異從交叉操作中分離出來，提高算法的效率.基于禁忌搜索算法的車輛路徑優(yōu)化算法通過試探一系列的特定搜索方向，讓特定的目標函數(shù)值提高到最大的程度，從而避免進入局部最優(yōu)解.

文中所述混合蟻群算法的參數(shù)設置如下：車輛數(shù)目M為20，初始粒子參數(shù)值α、β、ρ、γ分別為1、3、0.2、0.25，θ=1.遺傳算法的基本參數(shù)設置為：種群個體數(shù)量為100，迭代次數(shù)30次.

實驗測試對象為裝載量較小、時間窗較窄的冷鏈物流運輸站，分別面向10個客戶、25個客戶以及50個客戶進行取、送貨服務，測試實驗進行兩次，且兩次客戶的坐標不同.

首先針對車載量較少，時間窗較短的配送場景進行試驗.表1分別展示了3種算法在配送車輛NV、路徑規(guī)劃時間CT和配送總距離TD方面的對比.

表1 3種路徑規(guī)劃算法對比Tab.1 Comparison among three path planning algorithms

從表1可以看出，與M2算法及M3算法相比，當客戶數(shù)量為10時，本文所提算法(M1)與另外兩種算法綜合性能相同；而當客戶數(shù)量增長為25和50時，基于混合蟻群算法用于路徑規(guī)劃的平均時間要優(yōu)于對照組，且所派出的車輛數(shù)量較少，配送距離也更短.

測試實驗增加了不同客戶數(shù)量時配送總成本的驗證.根據(jù)上文的分析，配送總成本包含了配送車輛使用費用、車輛行駛費用以及取貨、送貨服務費用.結合目標函數(shù)表達式，客戶數(shù)量會影響到配送車輛數(shù)量、車輛行駛距離和服務時間的比例系數(shù).在經過混合蟻群算法轉化后，最終優(yōu)化參數(shù)為：α∈[1，2]、β∈[3，5]、ρ∈[0.3，0.6]和γ∈[0.1，0.3]，para={α、β、ρ、γ}，且搜索空間的維度為4.粒子下界、上界分別為paramin={1，3，0.3，0.1}、paramax={2，5，0.6，0.3}.測試結果見圖1所示.

圖1 3種優(yōu)化算法在不同客戶數(shù)量下配送總成本對比Fig.1 Comparison of total distribution cost among three optimization algorithms under different customer numbers

圖1中隨著客戶數(shù)量的增加，本文所提算法的配送總成本均低于對照算法.原因在于M2算法中遺傳算法的收斂速度較慢；而M3算法中禁忌搜索算法依靠禁忌表來避免進入局部最優(yōu)解，當客戶數(shù)量較多時，出現(xiàn)循環(huán)求解的幾率也隨之增加.值得注意的是，當客戶數(shù)量從40增加50時，M1算法的配送成本有所增加.因為車輛的裝載量較少，為滿足同時取、送貨的要求，則需更多的車輛來完成配送任務.

圖2展示了3種路徑優(yōu)化算法在客戶數(shù)量一定情況下的總成本與收斂速度.從圖2可以看出，隨著迭代次數(shù)的增加，3種路徑優(yōu)化算法的配送總成本均呈現(xiàn)下降的趨勢.其中，本文所提算法的總成本明顯低于對照算法，收斂速度分別提高了24.3%和18.6%，表明基于混合蟻群的路徑優(yōu)化算法的優(yōu)越性.本文將影響車輛路徑規(guī)劃的α、β、ρ、γ參數(shù)轉化為粒子優(yōu)化算法中的粒子，粒子群優(yōu)化算法的應用增強了螞蟻子群對最優(yōu)解的尋找能力，并在螞蟻子群之間交換信息素可避免子群得到局部最優(yōu)解，同時通過插入的啟發(fā)形式來求解弱可行解，從而增強了算法的性能.

圖2 3種路徑優(yōu)化算法的總成本和收斂速度Fig.2 Total cost and convergence speed of three route optimization algorithms

4 結 論

為滿足同時取、送貨這一復雜的市場需求，在考慮時間窗的情況下，提出了基于混合蟻群的多溫區(qū)冷鏈物流配送路徑優(yōu)化算法.通過將粒子群與蟻群算法相結合，增強螞蟻子群對路徑優(yōu)化最優(yōu)解的探索能力.同時采用基于插入的啟發(fā)式方法構造弱可行解，并以交叉、反轉來提高求解收斂速度.對照實驗表明，該算法有效降低了迭代次數(shù)并提高了收斂速度.