解永亮

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

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

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

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

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

1 問(wèn)題描述與建模

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

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

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

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

(1)

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

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

(2)

(3)

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

(4)

(5)

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

(6)

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

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

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

2.1 蟻群算法的路徑選擇

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

(7)

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

(8)

(9)

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

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

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

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

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

(10)

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

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

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

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

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

(11)

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

測(cè)試實(shí)驗(yàn)增加了不同客戶數(shù)量時(shí)配送總成本的驗(yàn)證.根據(jù)上文的分析，配送總成本包含了配送車(chē)輛使用費(fèi)用、車(chē)輛行駛費(fèi)用以及取貨、送貨服務(wù)費(fèi)用.結(jié)合目標(biāo)函數(shù)表達(dá)式，客戶數(shù)量會(huì)影響到配送車(chē)輛數(shù)量、車(chē)輛行駛距離和服務(wù)時(shí)間的比例系數(shù).在經(jīng)過(guò)混合蟻群算法轉(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}.測(cè)試結(jié)果見(jiàn)圖1所示.

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

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

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

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

4 結(jié) 論

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