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

解永亮

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

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

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

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

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

1 問題描述與建模

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

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

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

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

(1)

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

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

(2)

(3)

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

(4)

(5)

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

(6)

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

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

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

2.1 蟻群算法的路徑選擇

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

(7)

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

(8)

(9)

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

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

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

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

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

(10)

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

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

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

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

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

(11)

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

3 實驗分析

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

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

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

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

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

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

測試實驗增加了不同客戶數(shù)量時配送總成本的驗證.根據(jù)上文的分析，配送總成本包含了配送車輛使用費用、車輛行駛費用以及取貨、送貨服務(wù)費用.結(jié)合目標(biāo)函數(shù)表達式，客戶數(shù)量會影響到配送車輛數(shù)量、車輛行駛距離和服務(wù)時間的比例系數(shù).在經(jīng)過混合蟻群算法轉(zhuǎn)化后，最終優(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}.測試結(jié)果見圖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)解，當(dāng)客戶數(shù)量較多時，出現(xiàn)循環(huán)求解的幾率也隨之增加.值得注意的是，當(dāng)客戶數(shù)量從40增加50時，M1算法的配送成本有所增加.因為車輛的裝載量較少，為滿足同時取、送貨的要求，則需更多的車輛來完成配送任務(wù).

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

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

4 結(jié) 論

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