基于改進(jìn)遺傳算法的連鎖超市配送路線優(yōu)化研究

李小玲

(廣東理工學(xué)院經(jīng)濟(jì)管理學(xué)院,廣東 肇慶 526000)

配送是連鎖超市經(jīng)營(yíng)中的一個(gè)重要環(huán)節(jié),配送包括“配”和“送”2個(gè)內(nèi)容,“配”即對(duì)貨物進(jìn)行合理分配,將其置于不同車(chē)輛,“送”即對(duì)配送路線進(jìn)行合理規(guī)劃,從而提高車(chē)輛的載重和空間利用率,進(jìn)而節(jié)約配送成本,換言之即貨物配載問(wèn)題和車(chē)輛路徑問(wèn)題[1]。

車(chē)輛路徑問(wèn)題(VRP,vehicle routing problem)于1959年由Dantzig等[2]提出,它主要研究在滿(mǎn)足約束條件下最佳的車(chē)輛行駛路線方案。貨物配載問(wèn)題的研究始于國(guó)外,自1939年(Kantorovich)、1940年(Brook)開(kāi)始[3],解決最大化載重和容積利用率使得配送成本降低的問(wèn)題。將這2個(gè)問(wèn)題之間的相關(guān)性考慮在內(nèi),同時(shí)進(jìn)行優(yōu)化,建立模型并設(shè)計(jì)算法進(jìn)行求解,無(wú)論從理論上還是實(shí)際上都有一定的意義。從理論上而言,可以豐富配送路線規(guī)劃理論,從實(shí)際上而言,能夠優(yōu)化配送過(guò)程中資源利用不合理的問(wèn)題[4-8]。

1 模型描述

研究配送路線優(yōu)化問(wèn)題的范圍是:單個(gè)配送中心、多輛車(chē)輛、多品種貨物、路網(wǎng)非對(duì)稱(chēng)、路線閉合型貨物配裝與車(chē)輛路徑優(yōu)化問(wèn)題。

該模型可描述為從配送中心出發(fā),由n輛車(chē)輛完成對(duì)多個(gè)客戶(hù)點(diǎn)的配送,配送中心與客戶(hù)的距離以及任意2個(gè)客戶(hù)之間的路網(wǎng)距離已知,客戶(hù)所需求的貨物品種規(guī)格數(shù)量已知,所用車(chē)輛的載重和容積已知,車(chē)輛有最大行駛距離限制,在多個(gè)約束條件下,要確定車(chē)輛載重和容積利用率最大、投入使用車(chē)輛最少以及車(chē)輛總行駛距離最短的配送方案。

1.1 模型假設(shè)

綜合優(yōu)化模型在以下假設(shè)下建立:①配送為閉合的,且貨物單向流動(dòng);②車(chē)輛為一對(duì)多個(gè)客戶(hù),每輛車(chē)1條線路;③各個(gè)客戶(hù)的需求已知,貨物為紙箱式包裝;④貨物在車(chē)廂內(nèi)可以任意擺放。

1.2 模型參數(shù)及變量定義

對(duì)模型中的參數(shù)和變量定義如下:k表示車(chē)輛編號(hào)(k=1,2,…,n);i,j表示客戶(hù)編號(hào)(i,j=0,1,2,…,n),i,j=0表示配送中心;p表示貨物編號(hào)(p=1,2,…,m);uij表示客戶(hù)點(diǎn)i,j之間的距離;Gk表示車(chē)輛k的額定載重量;vk表示車(chē)輛k的額定容積;gip表示客戶(hù)i的貨物p的重量;vip表示客戶(hù)i的貨物p的體積。

模型中涉及到的變量定義如下:

1.3 模型構(gòu)建

結(jié)合模型描述、模型假設(shè)以及參數(shù)和變量定義,建立配送路線優(yōu)化模型為

(1)

(2)

(3)

(4)

s.t.

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

yik=0或1,i=1,2,…,n,k=1,2,…,l

(14)

(15)

對(duì)模型目標(biāo)函數(shù)解釋如下:式(1)表示車(chē)輛總行駛里程最短;式(2)表示最大化載重利用率;式(3)表示最大化容積利用率;式(4)表示車(chē)輛使用數(shù)量最少;式(5)表示車(chē)輛最大行駛距離限制;式(6)表示車(chē)輛載重量限制;式(7)表示車(chē)輛裝載容積限制;式(8)表示單個(gè)客戶(hù)點(diǎn)貨物應(yīng)裝載在同一輛車(chē)上;式(9)、式(10)表示每個(gè)客戶(hù)只能由1輛車(chē)提供服務(wù);式(11)表示車(chē)輛從配送中心出發(fā)最后返回配送中心;式(12)表示到達(dá)客戶(hù)點(diǎn)i的車(chē)輛數(shù)與從客戶(hù)點(diǎn)i開(kāi)出的車(chē)輛數(shù)一致。式(13)～(15)為決策變量的0、1約束。

1.4 目標(biāo)函數(shù)處理

上述模型存在多個(gè)目標(biāo)函數(shù),考慮到求解的復(fù)雜度,將多目標(biāo)函數(shù)經(jīng)過(guò)統(tǒng)一量綱處理轉(zhuǎn)換成單目標(biāo)函數(shù),各個(gè)目標(biāo)轉(zhuǎn)換成成本函數(shù)后再進(jìn)行相加,使得模型的求解結(jié)果以配送成本進(jìn)行更為直觀的反應(yīng)。目標(biāo)函數(shù)與成本的轉(zhuǎn)換如圖1所示。

圖1 成本結(jié)構(gòu)Fig.1 The cost structure chart

目標(biāo)函數(shù)轉(zhuǎn)換定義以下幾個(gè)參數(shù):

通過(guò)統(tǒng)一量綱,從總配送成本最小的角度出發(fā),原目標(biāo)函數(shù)可轉(zhuǎn)換為

(16)

(17)

(18)

(19)

其中:式(16)表示車(chē)輛總里程成本最小;式(17)表示占用車(chē)輛產(chǎn)生的固定使用成本最小;式(18)和式(19)表示車(chē)輛空閑載重和容積產(chǎn)生的機(jī)會(huì)成本最小。根據(jù)貨物屬性,同一批貨物選擇一種計(jì)價(jià)方式,因而定義參數(shù)α、β為

其中:α+β=1。

統(tǒng)一量綱后,每個(gè)目標(biāo)函數(shù)都是成本函數(shù),求解時(shí)可將其轉(zhuǎn)換為追求總配送成本最小的單目標(biāo)函數(shù),其表達(dá)式為

(20)

2 改進(jìn)遺傳算法求解

基于基本的遺傳算法[3-6]改進(jìn)求解上述模型,具體的步驟如下。

2.1 整數(shù)編碼

上述配送線路規(guī)劃問(wèn)題是帶有車(chē)輛運(yùn)行和貨物裝載訪問(wèn)次序的問(wèn)題,0-1編碼無(wú)法反映這一特征,因此考慮采用整數(shù)編碼。編碼思路如下:把所有客戶(hù)點(diǎn)當(dāng)作染色體中的各個(gè)基因,基因的排列順序即代表車(chē)輛訪問(wèn)客戶(hù)點(diǎn)和客戶(hù)點(diǎn)貨物裝載的順序。以某配送中心配送路線規(guī)劃為例,假設(shè)該配送中心安排3輛車(chē)出發(fā)對(duì)10個(gè)客戶(hù)點(diǎn)進(jìn)行配送,共規(guī)劃了3條配送路線:路徑1:0-5-2-9-0,路徑2:0-4-3-6-1-0,路徑3:0-7-8-10-0。那么對(duì)于第1條配送路線而言,車(chē)輛配送客戶(hù)的順序即訪問(wèn)順序?yàn)?、2、9,而對(duì)應(yīng)的貨物裝載順序?yàn)?、2、5。

2.2 產(chǎn)生初始化種群

在編碼中隨機(jī)生成了1×10染色體,并重復(fù)N次(N為初始種群的規(guī)模),把中間第i次生成的染色體放到一個(gè)規(guī)模為N×L種群的第i行,那么結(jié)果能帶到含有N個(gè)個(gè)體規(guī)模的初始種群。

2.3 解碼方案及適應(yīng)值函數(shù)確定

采用對(duì)染色體從第1列開(kāi)始進(jìn)行累加求和的方式,計(jì)算對(duì)應(yīng)客戶(hù)點(diǎn)貨物體積和重量的累加和,若到某個(gè)位置重量或容積累加和超過(guò)車(chē)輛額定載重或額定容積,則在該點(diǎn)后面插入0,若容積和載重累加和都未超過(guò),那么計(jì)算出從配送中心到該列對(duì)應(yīng)客戶(hù)點(diǎn),再?gòu)脑擖c(diǎn)返回配送中心這條路線的總距離,判斷是否超過(guò)車(chē)輛總行駛距離限制,若超過(guò)則在該位置插入0,再將貨物總體積和總重量置為0,重復(fù)上述步驟,直至進(jìn)行到最后一列染色體。

研究將目標(biāo)函數(shù)的倒數(shù)定義為適應(yīng)度函數(shù),即fτ=1/f(pi)。

2.4 確定選擇算子

采用輪盤(pán)賭和最優(yōu)串選擇相結(jié)合的方法選擇算子,這種方法既能滿(mǎn)足最優(yōu)遺傳,也能滿(mǎn)足較優(yōu)個(gè)體大概率遺傳到下一代。

2.5 交叉算子

基于兩點(diǎn)交叉算子對(duì)其進(jìn)行改進(jìn),生成兩點(diǎn)交叉變異算子,假設(shè)某個(gè)體有5個(gè)變量:設(shè)個(gè)體P1={1|24|53|},P2={3|51|24|},|為交叉點(diǎn),子個(gè)體分別為C1和C2,取P2處2個(gè)交叉點(diǎn)中的基因放在子代C1對(duì)應(yīng)位置處,而P2中交叉點(diǎn)[5,1]的補(bǔ)集[3,2,4]隨機(jī)排列在C1其他位置,同理取P1交叉點(diǎn)中間的基因放在子代C2對(duì)應(yīng)位置處,而P1中交叉點(diǎn)[2,4]的補(bǔ)集[1,5,3]則隨機(jī)排列在子代C2其他位置。

2.6 變異算子

研究選取互換變異,將染色體其中2個(gè)地方的基因當(dāng)作互換變異的點(diǎn)。

3 實(shí)例驗(yàn)證

3.1 案例背景介紹

對(duì)某配送中心直配連鎖超市試運(yùn)營(yíng)項(xiàng)目進(jìn)行實(shí)例研究,該配送中心其中一個(gè)區(qū)域覆蓋30個(gè)連鎖超市門(mén)店。目前,該配送中心所涉及到的貨物品種以油類(lèi)和大米為主,共有15個(gè)品種,這些貨物都采用紙箱包裝,門(mén)店要貨均以箱為單位,門(mén)店對(duì)配送時(shí)間未做要求,只需要配送中心在收到訂單后次日送達(dá)即可。

目前,該配送中心采用新能源車(chē)輛進(jìn)行配送,車(chē)輛相關(guān)信息如表1所列。

表1 車(chē)輛相關(guān)參數(shù)

該配送中心覆蓋的30個(gè)客戶(hù)點(diǎn)位置分布如圖2所示,編號(hào)0代表配送中心,1～30代表各個(gè)連鎖超市門(mén)店。

圖2 30個(gè)網(wǎng)點(diǎn)分布Fig.2 The distibution chart of 30 dots

該配送中心目前按照固定的配送路線進(jìn)行配送,即車(chē)輛每天按固定路線進(jìn)行送貨,現(xiàn)運(yùn)行的有6條固定配送路線,共計(jì)使用6輛車(chē),這種方案下總的配送成本1 655.9元、車(chē)輛總行駛路程318.8 km、載重利用率79.7%、容積利用率79.2%。

3.2 模型及算法應(yīng)用結(jié)果

采用MATLAB編程求解模型。通過(guò)查詢(xún)相關(guān)文獻(xiàn),確定案例初始種群規(guī)模,在50～200之間進(jìn)行取值實(shí)驗(yàn),從實(shí)驗(yàn)結(jié)果中確定本算例初始種群規(guī)模為200,從而生成擁有200個(gè)個(gè)體的染色體第一代。

參考文獻(xiàn)[7-10]進(jìn)行交叉概率和變異概率的選取,通過(guò)反復(fù)實(shí)驗(yàn),確定變異概率為0.01,交叉概率為0.7。

在進(jìn)行迭代時(shí),初步確定迭代次數(shù)為200,若收斂效果不好,再在此基礎(chǔ)上修改后重新運(yùn)行算法。通過(guò)多次實(shí)驗(yàn)取值,運(yùn)行得到的目標(biāo)函數(shù)變化趨勢(shì)如圖3所示。

種群規(guī)模200,交叉概率0.7,變異概率0.01,最大迭代次數(shù)1 000

不同參數(shù)取值對(duì)應(yīng)的目標(biāo)函數(shù)程序運(yùn)行結(jié)果如表2所列。

表2 不同參數(shù)取值對(duì)應(yīng)程序運(yùn)行結(jié)果

程序運(yùn)行后發(fā)現(xiàn),參數(shù)設(shè)定為初始種群規(guī)模200,交叉概率0.7,變異概率0.01,最大迭代次數(shù)1 000時(shí),收斂速度較快,程序總運(yùn)行時(shí)間188.9 s,該運(yùn)行結(jié)果對(duì)應(yīng)5條配送路線及裝載方案,得到5條路線總配送成本1 240.1元,總行駛路程231.1 km,使用5輛車(chē)輛,車(chē)輛平均容積利用率87.82%,平均載重利用率95.36%。

最終配送路線安排如表3所列,從該結(jié)果發(fā)現(xiàn),與優(yōu)化前相比,少占用了1輛車(chē)輛,車(chē)輛載重和容積利用率大大提高,同時(shí)車(chē)輛總行駛距離相比優(yōu)化前縮短了約90 km,最終總配送成本降低了415.8元。

表3 最優(yōu)配裝和車(chē)輛路徑安排方案

4 結(jié)語(yǔ)

從上述算例驗(yàn)證結(jié)果可以看出,研究建立的配送路線優(yōu)化模型以及相應(yīng)的算法能夠解決該配送中心貨物配載與車(chē)輛路線規(guī)劃共同優(yōu)化的問(wèn)題,而且案例中車(chē)輛有行駛距離限制,適用于目前末端配送中廣泛引入新能源車(chē)輛進(jìn)行配送的情況,實(shí)用性很強(qiáng),且模型通過(guò)統(tǒng)一量綱的方式將目標(biāo)轉(zhuǎn)換成配送成本,更能直觀地展現(xiàn)配送中心在配送過(guò)程中的成本消耗。