李小玲

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

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

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

1 模型描述

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

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

1.1 模型假設(shè)

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

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

對模型中的參數(shù)和變量定義如下:k表示車輛編號(k=1,2,…,n);i,j表示客戶編號(i,j=0,1,2,…,n),i,j=0表示配送中心;p表示貨物編號(p=1,2,…,m);uij表示客戶點i,j之間的距離;Gk表示車輛k的額定載重量;vk表示車輛k的額定容積;gip表示客戶i的貨物p的重量;vip表示客戶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)

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

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

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

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

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

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

(16)

(17)

(18)

(19)

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

其中:α+β=1。

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

(20)

2 改進遺傳算法求解

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

2.1 整數(shù)編碼

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

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

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

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

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

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

2.4 確定選擇算子

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

2.5 交叉算子

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

2.6 變異算子

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

3 實例驗證

3.1 案例背景介紹

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

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

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

該配送中心覆蓋的30個客戶點位置分布如圖2所示,編號0代表配送中心,1～30代表各個連鎖超市門店。

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

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

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

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

參考文獻[7-10]進行交叉概率和變異概率的選取,通過反復(fù)實驗,確定變異概率為0.01,交叉概率為0.7。

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

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

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

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

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

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

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

4 結(jié)語

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