細(xì)菌覓食優(yōu)化算法求解物流配送問題

王 垚，李 珺，屈藝暉

(蘭州交通大學(xué) 電子信息與工程學(xué)院，甘肅 蘭州 730070)

0 引 言

隨著生活質(zhì)量的提高和物流技術(shù)的發(fā)展，以及電商平臺的普及，生鮮食品與消費(fèi)者的聯(lián)系愈加緊密，使得人們對于生鮮的需求越來越大[1]。但是，生鮮需求增大的同時(shí)，生鮮物流配送也存在著問題，例如：配送中心選擇、配送路徑安排的不合理，造成的配送成本高、配送時(shí)間不及時(shí)、消耗時(shí)間長，生鮮損耗高等都制約著生鮮貿(mào)易的發(fā)展[2]。

文獻(xiàn)[3]對產(chǎn)品配送過程中的易腐性進(jìn)行研究，并通過建立一個(gè)多目標(biāo)規(guī)劃模型，實(shí)現(xiàn)對配送過程中成本最小化目標(biāo)及新鮮度最大化目標(biāo)的雙目標(biāo)模型求解。文獻(xiàn)[4]在改進(jìn)的層次分析法基礎(chǔ)上，提出了針對農(nóng)產(chǎn)品物流中心的多準(zhǔn)則選址決策模型，并通過綜合評價(jià)值的最優(yōu)和最劣值，獲取方案的綜合評價(jià)值。文獻(xiàn)[5]通過設(shè)計(jì)一種雙目標(biāo)混合整數(shù)數(shù)學(xué)規(guī)劃方法，用于評估和預(yù)測配送中心中的易變質(zhì)產(chǎn)品，對預(yù)測生鮮貨物量提供了一種思路。文獻(xiàn)[6]針對生鮮產(chǎn)品時(shí)效性特點(diǎn)，應(yīng)用模糊隸屬度函數(shù)表示的時(shí)間窗反映客戶滿意度，綜合考慮系統(tǒng)成本和客戶滿意度的多目標(biāo)模型，同時(shí)加入生鮮度損耗系數(shù)，對帶時(shí)間窗的生鮮物流配送問題進(jìn)行了求解。文獻(xiàn)[7]建立了基于時(shí)間約束的生鮮配送優(yōu)化模型，通過Dijkstra算法和節(jié)約里程法對問題進(jìn)行求解。文獻(xiàn)[8]分析了B2C環(huán)境下生鮮物流配送系統(tǒng)中造成的損耗及客戶滿意度影響，采用多配送中心分區(qū)配送模式，構(gòu)建以物流成本最小及客戶滿意度最大的多目標(biāo)模型，并通過遺傳算法對該問題進(jìn)行求解。

由于生鮮食品的特殊性，在配送上對于時(shí)間方面要求較高。此外，從供應(yīng)商角度出發(fā)，整個(gè)系統(tǒng)的成本也不容忽視。實(shí)際生活中，同時(shí)考量多種因素影響下的優(yōu)化問題，稱之為多目標(biāo)問題(multi-objective optimization problems，MOPs)。對于多目標(biāo)問題，傳統(tǒng)的求解方法有加權(quán)法、約束法、混合法等，這些方法求解思路都是通過將多個(gè)目標(biāo)賦予一定的權(quán)值從而轉(zhuǎn)化為單目標(biāo)問題，再通過傳統(tǒng)單目標(biāo)求解方法對相關(guān)問題進(jìn)行求解，但是這種方法只能求解給定權(quán)值下得到的最優(yōu)問題。近年來，隨著多目標(biāo)問題和智能算法的發(fā)展，越來越多的學(xué)者設(shè)計(jì)了相應(yīng)的多目標(biāo)算法對多目標(biāo)問題進(jìn)行求解。例如，文獻(xiàn)[9]將原有PESA算法進(jìn)行改進(jìn)，設(shè)計(jì)出了PESA-II并提出了區(qū)域選擇的概念；文獻(xiàn)[10]提出了基于非支配解排序的多目標(biāo)遺傳算法NSGA-II。

細(xì)菌覓食優(yōu)化算法(bacterial foraging optimization algorithm，BFO)，是由Passino[11]于2002年根據(jù)大腸桿菌覓食行為提出的一種啟發(fā)式算法。大腸桿菌會根據(jù)周圍環(huán)境做出如翻轉(zhuǎn)、游動等趨利避害的一系列行為。算法通過趨向性操作模擬大腸桿菌群體隨機(jī)性向富營養(yǎng)區(qū)游動的行為來實(shí)現(xiàn)隨機(jī)搜索的目的；復(fù)制操作則模擬了菌群優(yōu)勢劣汰后進(jìn)行增殖的行為，使得優(yōu)良個(gè)體得以保留；在經(jīng)過趨向性操作和復(fù)制操作以后，菌群個(gè)體進(jìn)行遷徙操作并以一定概率消亡，隨機(jī)在其他位置產(chǎn)生新的個(gè)體，增加種群的多樣性，降低算法陷入局部最優(yōu)的可能。該算法具有收斂速度快、搜索精度高、跳出局部最優(yōu)能力強(qiáng)等特點(diǎn)。在綜合考慮時(shí)間、成本的多目標(biāo)前提下，構(gòu)建相應(yīng)的雙目標(biāo)選址-路徑問題(location routing problem，LRP)[12]模型。根據(jù)Pareto支配關(guān)系[13]對標(biāo)準(zhǔn)BFO進(jìn)行改進(jìn)，設(shè)計(jì)相應(yīng)MOBFO算法(multi-objective bacterial foraging optimization algorithm)，并通過相應(yīng)算例驗(yàn)證該算法的有效性和優(yōu)越性。

1 問題描述

生鮮物流配送問題，實(shí)質(zhì)是選址-路徑問題。LRP問題指的是在一系列潛在設(shè)施點(diǎn)中選擇合適的設(shè)施點(diǎn)，使得各個(gè)設(shè)施點(diǎn)到各個(gè)客戶之間的運(yùn)輸成本最低。該問題可以進(jìn)一步描述為：設(shè)G=(V,E)是一個(gè)連通網(wǎng)絡(luò)，其中V為頂點(diǎn)集合(配送中心和配送點(diǎn))，E為有向邊集合(表示配送路徑)。每個(gè)配送點(diǎn)的需求量已知，要求進(jìn)行配送作業(yè)的車輛到該配送點(diǎn)的時(shí)間一定，即在該點(diǎn)規(guī)定的時(shí)間窗內(nèi)到達(dá)該配送點(diǎn)；在滿足一定約束條件下，從配送中心出發(fā)，有序到達(dá)所有配送點(diǎn)處作業(yè)，最后返回配送中心。

1.1 模型建立及假設(shè)

生鮮物流配送問題可以分為兩個(gè)子問題進(jìn)行求解，即配送中心選址和配送路徑安排。首先對配送點(diǎn)進(jìn)行路徑安排，解決配送路徑安排問題。再通過分配各個(gè)配送中心到每條已規(guī)劃好的路徑，選擇成本最小的配送中心作為一種子方案，從而解決選址的問題。配送路徑安排問題是其核心，實(shí)質(zhì)是帶軟時(shí)間窗的車輛路徑問題(vehicle routing problem with soft time window，VRPSTW)[14]。軟時(shí)間窗問題是指從配送中心出發(fā)的車輛必須在規(guī)定的時(shí)間窗[ETi,LTi]內(nèi)到達(dá)第i個(gè)配送點(diǎn)處進(jìn)行作業(yè)，其中ETi為車輛到達(dá)第i個(gè)配送點(diǎn)處允許的最早時(shí)間，LTi為車輛到達(dá)第i個(gè)配送點(diǎn)處允許的最晚時(shí)間，早于或者晚于到達(dá)時(shí)間窗內(nèi)規(guī)定時(shí)間，都將為配送成本造成一定損失，需要進(jìn)行一定的懲罰。

生鮮物流配送問題主要目標(biāo)是解決：(1)在潛在的配送中心處選擇合適的配送中心；(2)對配送點(diǎn)和配送中心規(guī)劃合理路徑。使得系統(tǒng)總成本最小，花費(fèi)時(shí)間最短?；谝陨戏治?，對該問題模型的假設(shè)有：(1)潛在配送中心的平面坐標(biāo)已知，且容量足夠大；(2)每個(gè)配送點(diǎn)的平面坐標(biāo)和需求量已知；(3)每個(gè)配送點(diǎn)有且僅有一輛車進(jìn)行作業(yè)，每輛車固定成本和每公里行駛成本、速度已知，且不受路面、交通、天氣等影響；(4)每輛車必須由配送中心出發(fā)依次在路徑上的各個(gè)配送點(diǎn)進(jìn)行作業(yè)后返回該配送中心；(5)車輛的載貨量已知；(6)每輛車到達(dá)各個(gè)配送點(diǎn)的到達(dá)時(shí)間需要在時(shí)間窗[ETi,LTi]內(nèi)，否則進(jìn)行一定懲罰。

根據(jù)以上分析可知，需要求解的目標(biāo)函數(shù)有2個(gè)：基于選址-路徑問題的成本最小目標(biāo)函數(shù)S1，如式1，以及帶軟時(shí)間窗車輛路徑問題的花費(fèi)時(shí)間最短目標(biāo)函數(shù)S2，如式2。

(1)

(2)

1.2 符號說明

M-備選的配送中心集合；Zi-第i個(gè)配送中心是否被選中；N-配送點(diǎn)集合；V-選中配送中心和配送點(diǎn)集合；K-參與作業(yè)的車輛集合；Q-車輛的最大載貨量；qi-配送點(diǎn)i處需求量；rk-第k輛車負(fù)責(zé)的配送點(diǎn)的總需求；tsi-車輛在配送點(diǎn)i處作業(yè)時(shí)間；[ETi,LTi]-配送點(diǎn)i處軟時(shí)間窗；dij-車輛從配送點(diǎn)i到配送點(diǎn)j間平面坐標(biāo)的歐氏距離；v-車輛的行駛速度；C0-車輛的固定成本；C1-車輛單位距離運(yùn)輸成本；C2-配送中心啟用成本；h1-車輛早于時(shí)間窗到達(dá)所受懲罰因子；h2-車輛晚于時(shí)間窗到達(dá)所受懲罰因子；E-懲罰成本常量；g1(x)-該路線總需求超過車輛限重時(shí)對目標(biāo)進(jìn)行的懲罰；g2(x)-該路線總需求超過車輛限重時(shí)對目標(biāo)進(jìn)行的懲罰；factor-車輛k的載重不能滿足該路線上配送點(diǎn)總需求時(shí)的懲罰因子；H-車輛早于或者晚于時(shí)間窗到達(dá)所造成成本損失的懲罰函數(shù)，具體為式3和式4。

當(dāng)0

Hijk=Eh1(ETi-ti)

(3)

當(dāng)ti>LTi時(shí)

Hijk=Eh2(ti-LTi)

(4)

其中約束條件為

(5)

(6)

(7)

(8)

rk=∑qiYik,i∈V,k∈K

(9)

0≤rk≤Q,k∈K

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

式5～8為0-1約束；式9和式10表示車輛k實(shí)際載重，且不能超重；式11和式12表示車輛k超重時(shí)對目標(biāo)函數(shù)的懲罰；式13表示車輛k從配送中心出發(fā)，作業(yè)完成后再返回該配送中心；式14和式15表示配送點(diǎn)有且只有一輛車進(jìn)行服務(wù)；式16表示每輛車只能被使用一次；式17和式18表示所有配送點(diǎn)都有對應(yīng)的配送中心。

2 算法設(shè)計(jì)

BFO算法主要通過趨向性操作、復(fù)制操作、遷徙操作來模擬大腸桿菌在覓食過程中尋找富營養(yǎng)區(qū)，從而找出問題最優(yōu)解的過程。通過改進(jìn)標(biāo)準(zhǔn)BFO算法已取得了一系列優(yōu)化成果，如文獻(xiàn)[15]中針對趨向性操作，提出自適應(yīng)步長更新公式，根據(jù)算法的迭代次數(shù)動態(tài)地調(diào)整菌群步長，提高算法的求解效率和精度，并通過解決高維問題驗(yàn)證了算法的有效性和優(yōu)越性。但是標(biāo)準(zhǔn)BFO算法適用于求解單目標(biāo)連續(xù)問題，而生鮮物流配送問題即LRP問題是一個(gè)離散問題，加之引入了成本、時(shí)間成為了一個(gè)多目標(biāo)離散問題，因此在使用細(xì)菌覓食優(yōu)化算法對該問題進(jìn)行求解時(shí)需要對算法的編碼方式、趨向性操作、復(fù)制操作、遷徙操作做出相應(yīng)的改進(jìn)。

2.1 編碼及解碼

對于有N個(gè)配送點(diǎn)、K輛車進(jìn)行作業(yè)的網(wǎng)絡(luò)，對每個(gè)細(xì)菌個(gè)體生成一個(gè)2行N列的數(shù)組，列號作為配送點(diǎn)編號，范圍是[0,N-1]，每個(gè)細(xì)菌個(gè)體代表一種配送方案。

每個(gè)細(xì)菌個(gè)體數(shù)組第一行X1，采用整數(shù)編碼，共N個(gè)數(shù)字，代表該配送點(diǎn)進(jìn)行作業(yè)的車輛編號。初始化時(shí)，隨機(jī)得開放配送中心，根據(jù)就近原則對配送點(diǎn)進(jìn)行分配；數(shù)組第二行X2采用實(shí)數(shù)編碼，表示配送順序權(quán)值，根據(jù)隨機(jī)生成的權(quán)值大小來決定由同路徑上配送點(diǎn)的配送順序，其取值為(0，N)。對于M個(gè)備選配送中心，將其加入到各條路徑中，選擇使得子方案成本最小的配送中心，并將其編號記錄在車輛組的結(jié)構(gòu)體中。

具體某個(gè)細(xì)菌個(gè)體編碼方式如表1所示。

表1 細(xì)菌個(gè)體編碼示意

假設(shè)carc[K]為struct car類型的車輛組，由表1解碼可知，參與配送任務(wù)的車輛編號為：0，1，2；若0號車輛由2號配送中心負(fù)責(zé)，則c[0].flag=2，0號車輛的配送路線為：2-1-4-2；同理，1號車輛的配送路線為：4-5-3-4；2號車輛的配送路線為：1-0-2-1。

2.2 多目標(biāo)趨向性操作

若設(shè)Ox(i,j,k)表示第x個(gè)細(xì)菌在第i次趨向性操作，第j次復(fù)制操作以及第k次遷徙操作后的位置。其在第i+1次趨向性操作，第j次復(fù)制操作以及第k次遷徙操作后的位置調(diào)整為Ox(i+1,j,k)=Ox(i,j,k)+C(i)α(i)。其中C(i)為細(xì)菌個(gè)體移動的步長，α(i)為細(xì)菌個(gè)體移動的方向。在趨向性操作中，針對車輛編號為整數(shù)，配送點(diǎn)權(quán)值為實(shí)數(shù)的問題，采用不同的步長數(shù)組進(jìn)行位置更新。車輛組步長固定為1和-1；配送點(diǎn)權(quán)值組采用步長計(jì)算公式進(jìn)行位置更新，步長計(jì)算公式如下:

C(i)=cos(2*π*(angle/360))*step

(19)

其中，angle為[0，360]上的隨機(jī)數(shù)；step為固定步長。

菌群個(gè)體所代表的每個(gè)方案中每次嘗試對車輛編號及配送點(diǎn)權(quán)值進(jìn)行更新后，都需要比較該個(gè)體更新前后新、舊方案的好壞，如果新方案更好，個(gè)體繼續(xù)向前尋優(yōu)，直到新方案不再優(yōu)于舊方案或者達(dá)到最大嘗試次數(shù)Ns為止。由于多目標(biāo)問題不能通過單目標(biāo)求解方法來考量菌群個(gè)體每次前進(jìn)后新、舊位置的好壞，因此引入Pareto支配關(guān)系進(jìn)行擇優(yōu)。當(dāng)新方案和舊方案存在支配關(guān)系時(shí)，可以根據(jù)Pareto支配關(guān)系判斷新舊方案的好壞；但是當(dāng)新舊方案互不支配時(shí)，需要對其進(jìn)行歸一化統(tǒng)一量綱來比較新舊方案的好壞。

定義1:Pareto占優(yōu)。

假設(shè)有M個(gè)以最小化為目標(biāo)進(jìn)行優(yōu)化的函數(shù)(f1,f2,…,fm)。x,y為其兩組解，對于所有m=1,2,…,M，有fm(x)≤fm(y)，且至少存在一個(gè)n滿足fn(x)

?m=1,2,…,Mfm(x)≤fm(y)∧

?n=1,2,…,M

fn(x)≤fn(y)

(20)

定義2:Pareto最優(yōu)解。

若Xf為所有可行解的集合，解x*不被其他可行解支配，則稱之為Pareto最優(yōu)解，即：

(21)

定義3:Pareto最優(yōu)解集。

由所有非支配解構(gòu)成的集合稱之為Pareto最優(yōu)解集p*，即：

p*?{x*|?x∈Xf:x?x*}

(22)

歸一化方法如下：

(23)

其中

gi(xnew)=fi(new)/fi(total)

(24)

gi(xold)=fi(old)/fi(total)

(25)

fi(total)=fi(new)+fi(old)

(26)

2.3 多目標(biāo)復(fù)制操作

MOBFO中通過每種方案之間的Pareto支配關(guān)系，統(tǒng)計(jì)每種方案的被支配次數(shù)，根據(jù)被支配次數(shù)來對菌群個(gè)體進(jìn)行排序。引入外部集用于存放找到的非支配解，以保留尋優(yōu)過程中找到的較優(yōu)方案。具體尋優(yōu)過程如下：

Step1:統(tǒng)計(jì)每種方案的被支配次數(shù)并排序；

Step2:判斷該方案是否為非支配解；

Step3:判斷該方案是否已經(jīng)存在于外部集中，如果是轉(zhuǎn)Step2；否則轉(zhuǎn)Step4；

Step4:判斷外部集中方案個(gè)數(shù)sunny是否等于菌群個(gè)體數(shù)S，如果是轉(zhuǎn)Step5；否則該方案存儲于外部集中，sunny++；

Step5:判斷當(dāng)前找到的非支配解與外部集中的解是否存在支配關(guān)系；如果當(dāng)前方案更好，取代外部集中該解，Step2；如果該方案不優(yōu)于外部集中任一，Step2；如果該方案和外部集中的解存在互不支配關(guān)系，根據(jù)2.2中歸一化方法進(jìn)行擇優(yōu)，Step2。

2.4 多目標(biāo)遷徙操作

遷徙操作中，個(gè)體在滿足了一定的遷徙概率Ped時(shí)，該個(gè)體消亡，但同時(shí)在搜索空間的隨機(jī)位置重新生成新的個(gè)體，相當(dāng)于將原來的細(xì)菌個(gè)體重新進(jìn)行初始化。這一行為大大降低了算法陷入局部最優(yōu)的概率，增加了種群的多樣性，擴(kuò)大了個(gè)體的搜索空間。遷徙次數(shù)的大小影響著算法的時(shí)間復(fù)雜度。隨著遷徙次數(shù)的增加，種群中消亡個(gè)體增加，種群多樣性也隨之增大；反之種群多樣性則降低。

2.5 算法步驟

具體步驟如下：

Step1:初始化，設(shè)定趨向性操作、復(fù)制操作、遷徙操作的次數(shù)Nc、Nr、Ne，趨向性操作最大嘗試次數(shù)Ns，遷徙概率Ped，種群規(guī)模N，外部集個(gè)數(shù)sunny，并將N個(gè)配送點(diǎn)隨機(jī)分配給隨機(jī)開放的配送中心；

Step2:遷徙操作循環(huán)：l=l+1；

Step3:復(fù)制操作循環(huán)：k=k+1；

Step4:趨向性操作循環(huán)：j=j+1；計(jì)算適應(yīng)度S1，S2；對每個(gè)細(xì)菌個(gè)體的X1和X2行進(jìn)行步長更新，計(jì)算新分組后的適應(yīng)度值S1，S2，并按照2.2節(jié)進(jìn)行擇優(yōu)；

Step5:如果j

Step6:根據(jù)2.3節(jié)所述進(jìn)行復(fù)制操作過程，并更新外部集；

Step7:如果k

Step8：根據(jù)2.3節(jié)所述進(jìn)行遷徙操作；

Step9:如果l

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法的有效性，數(shù)據(jù)采用Augeral等共享的有約束的車輛路徑問題(capacitated vehicle routing problem，CVRP)數(shù)據(jù)庫中A-n36-k5.vrp文件的實(shí)例。其中共有30個(gè)配送點(diǎn)，6個(gè)備選配送中心，具體參數(shù)見表2和表3。其他參數(shù)如下：Q=80，v=50，E=100，h1=0.1，h2=0.2，C0=30，C1=5。

表2 配送中心參數(shù)

表3 配送點(diǎn)參數(shù)

續(xù)表3 配送點(diǎn)參數(shù)

3.1 參數(shù)設(shè)置

算法相關(guān)參數(shù)設(shè)置如下：S=20，Nc=30，Nr=50，Ne=5，Ped=0.2，Ns=10，F(xiàn)1=F2=0.5。實(shí)驗(yàn)基于Win10操作系統(tǒng)，通過C語言編程，在VC++6.0平臺進(jìn)行仿真。重復(fù)運(yùn)行程序50次，取每次運(yùn)行結(jié)果中的最優(yōu)解，最終確定方案如表4所示。

表4 實(shí)驗(yàn)結(jié)果

本算例最終選擇開放三個(gè)配送中心，由計(jì)算結(jié)果可知，系統(tǒng)總成本為5 895.268。該次方案的拓?fù)淙鐖D1所示。

圖1 方案拓?fù)?/p>

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

為了驗(yàn)證MOBFO的有效性和優(yōu)劣性，通過與文獻(xiàn)[16]和Liu&Lin[16]提出的啟發(fā)式算法進(jìn)行對比，具體結(jié)果如表5所示。

表5 算法結(jié)果對比

由表5可知，MOBFO所求得方案在總成本上優(yōu)于另兩種算法所得結(jié)果。但由于文中涉及多目標(biāo)問題，因此還需比較MOBFO所得最佳方案與文獻(xiàn)[16]中最佳方案在配送時(shí)間與路程長短上的優(yōu)劣。由于配送車輛進(jìn)行配送任務(wù)的同時(shí)性，配送時(shí)間的判斷可根據(jù)最長路徑所花費(fèi)的時(shí)間來衡量。

表6 配送時(shí)間、總路程長度比較

由表6可知，MOBFO所得最佳方案在配送總路程長度上要優(yōu)于文獻(xiàn)[16]中的最佳方案，配送時(shí)間與文獻(xiàn)[16]中相當(dāng)。但在實(shí)際生活中，配送時(shí)間和距離長度也會受到一些如路況、氣候等因素的影響，從而直接或者間接地影響到方案總成本。決策者的決策情況也會對方案成本等產(chǎn)生一定約束。例如：在配送過程中，決策者為了盡可能地保證生鮮的新鮮度，而忽略在成本上的耗費(fèi)。由表5和表6表明，MOBFO在求解這一類問題上具有一定的優(yōu)越性，同時(shí)在對于多個(gè)目標(biāo)的優(yōu)化問題上也具有一定的優(yōu)勢。

4 結(jié)束語

以成本最低和配送時(shí)間最短為目標(biāo)，針對生鮮物流配送問題構(gòu)建了相應(yīng)的LRP問題模型，根據(jù)Pareto支配關(guān)系設(shè)計(jì)相應(yīng)的多目標(biāo)細(xì)菌覓食優(yōu)化算法，在個(gè)體互不支配時(shí)采用歸一化方法進(jìn)行擇優(yōu)處理，通過引入懲罰函數(shù)限制車輛所服務(wù)客戶點(diǎn)的需求，使得每一條路線上的配送點(diǎn)需求都可以被滿足。對該問題進(jìn)行求解，通過算例對比驗(yàn)證了算法的有效性和優(yōu)劣性，對于LRP問題提供了一定的參考。但還有一些約束沒有考慮充分，如配送中心庫存問題，交通路況對于車輛行駛速度的影響。而且生鮮物流系統(tǒng)也具有很多不確定性，主要體現(xiàn)在生鮮產(chǎn)品對時(shí)間的要求。同時(shí)也缺少相應(yīng)的實(shí)際案例，對具體問題進(jìn)行模擬規(guī)劃。因此，下一步研究工作可以考慮引入庫存問題，解決選址-路徑-庫存這一集成問題，同時(shí)添加隨機(jī)變量，使得模型更加符合實(shí)際情況。