物流配送過程中的3L-CVRP問題及其遺傳算法研究

王鳳麗　畢　然　王家敏　姜　濱

(山東商業(yè)職業(yè)技術(shù)學(xué)院國(guó)家農(nóng)產(chǎn)品現(xiàn)代物流工程技術(shù)研究中心　濟(jì)南　250103)

物流配送過程中的3L-CVRP問題及其遺傳算法研究

王鳳麗畢然王家敏姜濱

(山東商業(yè)職業(yè)技術(shù)學(xué)院國(guó)家農(nóng)產(chǎn)品現(xiàn)代物流工程技術(shù)研究中心濟(jì)南250103)

摘要針對(duì)物流配送中多種貨物的裝箱及路徑優(yōu)化問題,提出了一種帶有容量約束的三維裝箱和車輛路徑問題的求解方案。在考慮裝箱過程中車輛載重、物品性質(zhì)和體積等約束條件的基礎(chǔ)上進(jìn)行模型構(gòu)建,并采用遺傳算法對(duì)模型進(jìn)行了求解。通過10組實(shí)驗(yàn)數(shù)據(jù)對(duì)所構(gòu)建的模型進(jìn)行測(cè)試分析,其中實(shí)驗(yàn)結(jié)果的最優(yōu)解即目標(biāo)函數(shù)最優(yōu)值是104.195,運(yùn)行時(shí)間為125312ms,測(cè)試結(jié)果表明該模型算法能夠有效提高車輛的使用效率,降低物流配送成本。

關(guān)鍵詞三維裝箱; 路徑選擇; 遺傳算法; 多約束條件

Class NumberTP311.52

1引言

隨著物流系統(tǒng)集約化、一體化發(fā)展,需要將配送作業(yè)的各個(gè)環(huán)節(jié)綜合起來(lái)進(jìn)行系統(tǒng)化考慮[1]。貨物配裝及配送路徑作為配送的基礎(chǔ)重要環(huán)節(jié),在物流成本控制方面起著至關(guān)重要作用。一方面,貨物配裝問題解決得好壞直接關(guān)系到車輛空間、載重利用率,并且貨物配裝問題又是貨物運(yùn)輸中的安全問題之一;另一方面,配送路徑優(yōu)化一直是配送企業(yè)節(jié)約運(yùn)送成本的一個(gè)著眼點(diǎn)。因此,車輛路徑問題(Vehicle Routing Problem,VRP)如何設(shè)計(jì)合理、有效的車輛行駛路線,以達(dá)到減少車輛使用數(shù)量和行駛路線長(zhǎng)度的目的;裝箱問題(Container Loading Problem,CLP)如何設(shè)計(jì)高質(zhì)量的裝箱方案,減少車輛的使用數(shù)量,從而提高運(yùn)輸工具的利用率,都是降低物流成本要考慮的因素。帶有容量約束的三維裝箱和車輛路徑問題(Three-Dimensional Loading Capacitated Vehicle Routing Problem,3L-CVRP)結(jié)合了兩個(gè)著名的NP-hard問題,即車輛路徑問題(Vehicle Routing Problem,VRP)和三維裝箱問題(Three-Dimensional Packing Problem,3DPP),它從系統(tǒng)層面上綜合考慮路徑優(yōu)化和合理裝箱問題,對(duì)降低物流配送成本、提高物流企業(yè)競(jìng)爭(zhēng)力有著重要的意義。

物流裝載配送過程是通過對(duì)一些大小不同的規(guī)則立方體在三維規(guī)則箱體內(nèi)進(jìn)行合理放置,并在進(jìn)行三維空間位置放置的同時(shí)考慮配送路徑優(yōu)化,從而達(dá)到控制物流配送成本的目的。所以,物流裝箱配送問題是3L-CVRP問題。由于3L-CVRP是NP-Hard問題,國(guó)內(nèi)外學(xué)者大都采用現(xiàn)代啟發(fā)式算法對(duì)其進(jìn)行研究。Michel Gendreau等人提出了采用雙層禁忌搜索算法解決3L-CVRP問題[2];Guenther Fuellerer等提出蟻群算法,使用了一般化了的節(jié)約算法,在節(jié)約算法中引入信息素以及反映裝箱好壞的評(píng)價(jià)函數(shù),再通過局部搜索進(jìn)一步優(yōu)化解[3];David Mester介紹了一種基于多參數(shù)的進(jìn)化算法用于解決3L-CVRP問題,并對(duì)六個(gè)實(shí)際應(yīng)用問題進(jìn)行了測(cè)試[4];Damon、Teodor Gabriel Crainic等人采用現(xiàn)代啟發(fā)式算法對(duì)其進(jìn)行了研究[7,11]。在目前報(bào)道的文獻(xiàn)中,主要集中在對(duì)方法及實(shí)驗(yàn)室數(shù)據(jù)進(jìn)行討論,對(duì)于考慮物品的可選放置方向、重心、承重能力等因素較少。特別是運(yùn)用遺傳算法解決3L-CVRP問題的研究還不多。

本文通過調(diào)研及文獻(xiàn)分析,對(duì)物流配送過程中的3L-CVRP進(jìn)行了描述,分析了影響物流配送過程的影響因素,找出了本研究的主要約束條件,構(gòu)建適用于物流配送過程的3L-CVRP模型,針對(duì)3L-CVRP特點(diǎn),設(shè)計(jì)了自然數(shù)編碼的遺傳算法。最后,結(jié)合實(shí)例驗(yàn)證了模型和算法的可行性。

2問題描述

圖1　3L-CVRP的示意圖

配送成本占物流成本較大的比重,從而盡可能地降低配送成本對(duì)物流企業(yè)增加其競(jìng)爭(zhēng)力有著重要的作用。在配送過程中物流企業(yè)希望找到一種在滿足客戶要求下的有效配送方法。該方法要求車輛在裝卸過程中貨物間沒有浪費(fèi)和倒箱現(xiàn)象;在運(yùn)輸過程中較少存在迂回運(yùn)輸現(xiàn)象。因此,與此相對(duì)應(yīng)的3L-CVRP求解目標(biāo)是找到裝箱和路徑結(jié)合的方案,既要保證車輛裝載率,又要保證配送路程較短,從而盡可能地降低配送成本。在配送過程中,為了保證客戶的需求,要求所有客戶的訂單都要被處理;為了保證客戶交接貨物時(shí)的方便性,要求每個(gè)客戶只由一輛車服務(wù),即由一個(gè)客戶要求的所有物品需要有一輛車來(lái)完成,不能分批配送貨物;當(dāng)貨車按照順序服務(wù)客戶的時(shí)候,必須能夠順利卸下其貨物,不可產(chǎn)生多次裝卸現(xiàn)象,卸貨時(shí)貨物只能向上方向移動(dòng),要卸的貨物不能被其它貨物壓著,其前面不能被其他貨物擋住;為了保證貨物的質(zhì)量及運(yùn)輸安全,需要考慮其容量情況,應(yīng)盡量減小物品在車廂內(nèi)的晃動(dòng);此外,還應(yīng)該考慮產(chǎn)品特性,有些產(chǎn)品不倒置、不側(cè)放、運(yùn)輸車輛需預(yù)留一定的空調(diào)出風(fēng)口。因此,產(chǎn)品的3L-CVRP一般情況下需要滿足以下約束條件:

1) 訂單完整性約束:一個(gè)客戶要求的所有物品需要有一輛車來(lái)完成,不能分批配送貨物;

2) 正交放置:要求物品在車廂內(nèi)正交放置,即物品的邊楞與車的長(zhǎng)寬高方向平行;

3) 容積約束:車中所有放置的物品不能超出車輛邊界,貨物的總體積不能超過車廂的體積;

4) 重量約束:為了保證行車安全,車中所有放置的物品重量不能超過車輛的載重;

5) 旋轉(zhuǎn)約束:考慮到貨物品的特殊性,有些不能倒置只能在水平平面內(nèi)做90°旋轉(zhuǎn);

6) 易碎性約束:如圖3中標(biāo)識(shí)貨物,灰色標(biāo)識(shí)為易碎品,文中1表示是易碎品,0表示非易碎品。易碎物品可放在易碎物品上面,易碎物品可放在非易碎物品上面,但非易碎品不能放在易碎品上面;

7) 平衡性約束:只有當(dāng)支撐面積與底面積的比值超過一個(gè)給定的閾值比θ時(shí)才允許擺放;

8) 先進(jìn)后出約束:當(dāng)貨車按照順序服務(wù)客戶的時(shí)候,必須能夠順利卸下其貨物,卸貨時(shí)貨物只能延垂直方向移動(dòng),要卸的貨物不能被其它貨物壓著,其前面不能被其他貨物擋住。

3模型構(gòu)建

在物流配送過程中,既要保證滿足客戶的需求又要盡可能地降低成本。本文考慮的配送成本包括車輛的使用成本和車輛的運(yùn)輸成本,總的目標(biāo)是在滿足約束的情況下運(yùn)輸?shù)某杀咀钌佟?L-CVRP是在考慮貨物特性及滿足其上述的約束條件下,從配送成本考慮,將定單匯集起來(lái),通過合理的配載、拼箱,實(shí)現(xiàn)農(nóng)產(chǎn)品的多頻次、少批量的配送服務(wù);同時(shí),應(yīng)減少運(yùn)輸中的不合理現(xiàn)象(迂回運(yùn)輸、重復(fù)運(yùn)輸)。在保證貨物質(zhì)量和運(yùn)輸安全的情況下,客戶需求訂單通過合理的配載使得車輛的使用量和運(yùn)輸距離最短是合理的配送過程。因此,筆者建立了以運(yùn)輸過程中的總成本最少的目標(biāo)的模型:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

xijk∈{0,1}

(8)

其中,α表示配送成本中可變成本的比例系數(shù);P、Q分別表示配送成本中可變成本、固定成本;V表示車輛的容量;D表示車輛的載重;Cij表示從i地到j(luò)地的直線距離;xijk為0-1變量,值為1時(shí)表示車輛k從i地到j(luò)地。

在上述模型中,式(1)為目標(biāo)函數(shù),即要求在配送總成本(車輛的使用固定成本,配送距離產(chǎn)生的可變的成本)最小;式(2)和式(3)為一個(gè)顧客的貨物都是由一輛車來(lái)完成,從而保證了訂單的完整性;式(4)和式(5)為車輛體積約束;式(6)和式(7)為車輛體積約束;式(8)表示車輛k從i地到j(luò)地,則取xijk為1,車輛沒有k從i地到j(luò)地,則取xijk為0。

43L-CVRP模型遺傳算法設(shè)計(jì)

4.1遺傳算法概述

20世紀(jì)60年代,美國(guó)J. Hold教授從生物遺傳學(xué)“物競(jìng)天擇,適者生存”的自然規(guī)律中得到靈感和啟迪,創(chuàng)立了基于自然選擇的編程技術(shù)-遺傳算法(Genetic Algorithms)[12]。遺傳算法是一種迭代搜索算法,通過構(gòu)建染色體、種群選擇、染色體交叉和變異等過程,實(shí)現(xiàn)自適應(yīng)隨機(jī)搜索,具備優(yōu)良的魯棒性和潛在的并行計(jì)算機(jī)制,能夠以很大的概率找到問題的最優(yōu)解,因此,遺傳算法在求解3L-CVRP等NP-hard問題方面具有很大的優(yōu)勢(shì)。

4.2遺傳算法設(shè)計(jì)

遺傳算法是根據(jù)問題的目標(biāo)函數(shù)構(gòu)造一個(gè)適值函數(shù),以群體中所有個(gè)體為操作對(duì)象,對(duì)染色體構(gòu)成的種群進(jìn)行評(píng)價(jià)、遺傳運(yùn)算、選擇經(jīng)過多代繁殖,獲得適應(yīng)值最好的個(gè)體作為問題的最優(yōu)解。因此,需要構(gòu)造染色體色體(解)、確定適應(yīng)度函數(shù)以及主要操作算子,針對(duì)3L-CVRP問題,具體算法設(shè)計(jì)如下。

4.2.1染色體編碼

染色體編碼是把物流配送問題的可行解從現(xiàn)實(shí)中轉(zhuǎn)換到遺傳算法所能處理的搜索解空間。在遺傳算法過程中,種群中的每個(gè)個(gè)體都是由基因構(gòu)成的,要染色體與待求解的問題進(jìn)行對(duì)應(yīng),就需要對(duì)基因進(jìn)行正確的編碼。在配送過程中,訂單中的貨物的順序、位置、放置方式和訂單的順序確定了整個(gè)的裝載過程和路徑。故與之相對(duì)應(yīng)3L-CVRP的染色體中應(yīng)包含車輛、訂單、貨物、貨物放置方式信息,宜采用自然數(shù)編碼,我們用集合表示一個(gè)染色體{a1-a2…,b1-b2…,c1-c2…;ck-ck+1…,d1-d2…}。集合中的ai表示代表訂單編號(hào),bi代表ai訂單所在的車輛編號(hào),ci代表所有訂單中貨物順序訂單之間用分號(hào)隔開,di表示與ci位置序號(hào)一致的貨箱的方置方向。如兩輛車配送四個(gè)訂單的染色體為:{1-3-2-4,0-1-1-2,2-1;3-4;5-6;7-8,0-1-2-1-2-3-5-4}。表示1號(hào)訂單中的以2號(hào)貨物以水平側(cè)放,1號(hào)豎直放置裝入0號(hào)車。

4.2.2種群初始化及適應(yīng)度評(píng)價(jià)

種群初始解為隨機(jī)產(chǎn)生的自然數(shù)序列。對(duì)n個(gè)訂單k車的配送過程編碼的過程如下:在ai位置上隨機(jī)產(chǎn)生n個(gè)訂單序列;在bi位置上產(chǎn)生n個(gè)在[1,k](k為車輛的數(shù)目)范圍內(nèi)的隨機(jī)序列;在ci位置上隨機(jī)產(chǎn)生訂單中貨物順序,訂單間用分號(hào)隔開;di位置隨機(jī)產(chǎn)生在[0,5]范圍內(nèi)貨箱的方置方向序列。如此反復(fù),直到產(chǎn)生滿足種群數(shù)目。

適應(yīng)度評(píng)價(jià):在遺傳算法中使用適值函數(shù)來(lái)表征種群中每個(gè)給以對(duì)其生存環(huán)境的適應(yīng)能力,適值函數(shù)的形式直接決定著群體的進(jìn)化行為。配送成本越小越有利于物流企業(yè)控制成本,增強(qiáng)其競(jìng)爭(zhēng)力。為了能夠直接將適值函數(shù)與群體中的個(gè)體優(yōu)劣相聯(lián)系,在此采用適應(yīng)度函數(shù)是目標(biāo)函數(shù)的倒數(shù),由此可見函數(shù)值越小的染色體越優(yōu)良。

4.2.3選擇操作

在遺傳算法中自然選擇規(guī)律的體現(xiàn)就是以適應(yīng)值的大小決定的概率分布進(jìn)行選擇,最常用的選擇策略是正比選擇策略。即每個(gè)個(gè)體被選中進(jìn)行遺傳運(yùn)算的概率為該個(gè)體的適應(yīng)值和群體中所有個(gè)體適應(yīng)值總和的比例。對(duì)于個(gè)體i,設(shè)其目標(biāo)函數(shù)值為Fi,種群規(guī)模為NP,則該個(gè)體被選擇概率Pi可表示為

(9)

得到選擇概率后,采用輪盤賭來(lái)實(shí)現(xiàn)選擇操作。令

PP0=0

(10)

(11)

每次轉(zhuǎn)輪時(shí),隨機(jī)產(chǎn)生ξk∈U(0,1),當(dāng)PPi-1≤ξk≤PPi,則選擇個(gè)體i,共轉(zhuǎn)輪NP次。

4.2.4遺傳操作

1) 交叉操作:對(duì)于3L-CVRP問題,如果單純地使用一般的交叉算子往往會(huì)使一些優(yōu)良的子串被破壞,并且在染色體間交叉時(shí),無(wú)法產(chǎn)生有效的個(gè)體。在此采用一種有效的雙切點(diǎn)交叉算子,對(duì)于兩個(gè)選定的染色體隨機(jī)選取兩個(gè)切點(diǎn),交換兩個(gè)切點(diǎn)間的子串。對(duì)于染色體A、B在切點(diǎn)9和14上進(jìn)行雙切點(diǎn)交叉,得到染色體C、D,如下所示:

A: 1-3-2-4,2-1-0-1,2-1;3-4;

5-6;7-8,0-1-2-1-2-3-5-4;

B:1-3-2-4,0-1-1-2,3-4;2-1;

5-6;7-8,0-1-2-1-2-3-5-4;

C: 1-3-2-4,0-1-1-1,2-1;3-4;

5-6;7-8,0-1-2-1-2-3-5-4;

D: 1-3-2-4,2-1-0-2,3-4;2-1;

5-6;7-8,0-1-2-1-2-3-5-4。

在交叉運(yùn)算過程中會(huì)遇到不合法的編碼,例如選擇的切點(diǎn)為17和21,經(jīng)交叉后,后代的編碼不合法。對(duì)于這種情況,本文采用了部分映射交叉修復(fù)策略。

2) 變異操作:在種群中,變異是按照變異概率任選若干基因位改變其位值改變基因的過程。通過變異,染色體產(chǎn)生隨機(jī)變化,可以提供初始種群中不含有的基因或選擇過程中丟失的基因。可以通過變異操作控制車輛的使用信息。變異概率一般為一個(gè)較小的數(shù),在(0,0.05)范圍內(nèi)。

重復(fù)上述步驟,根據(jù)遺傳算法迭代次數(shù)或種群的收斂停止循環(huán),輸出最終結(jié)果。

5算例仿真

表1　遺傳算法測(cè)試結(jié)果

在Pentium(R)4,CPU2.8GHz,1G內(nèi)存的計(jì)算機(jī)上,WindowsXP系統(tǒng)環(huán)境下采用面向?qū)ο蟮腏AVA語(yǔ)言,對(duì)文章中描述的算法進(jìn)行系統(tǒng)實(shí)現(xiàn)。本文采用http://www.or.deis.unibo.it/research_pages/ORinstances/ORinstances.htm網(wǎng)站中提供的貨物數(shù)據(jù)信息對(duì)算法進(jìn)行測(cè)試模擬。其余數(shù)據(jù)根據(jù)與公司工作人員的討論確定固定成本為30(無(wú)量綱),可變成本為6,兩者間的比例為0.65∶0.35。遺傳算法的種群大小為20,遺傳操作的交叉率為0.85,變異率為0.05,迭代次數(shù)最高限閾值為200次。系統(tǒng)的運(yùn)行時(shí)間閾值為270000ms,對(duì)網(wǎng)站上3L-CVRP數(shù)據(jù)進(jìn)行了10組測(cè)試。測(cè)試結(jié)果如表1所示。經(jīng)過遺傳算法計(jì)算,最優(yōu)目標(biāo)函數(shù)值為104.195,運(yùn)行時(shí)間為125312ms,迭代次數(shù)為35次。平均的目標(biāo)函數(shù)值、系統(tǒng)運(yùn)行時(shí)間及平均迭代次數(shù)分別為123.469、107854ms、24.4次。

6結(jié)語(yǔ)

1) 本文針對(duì)物流配送問題,提出了采用遺傳算法對(duì)貨箱裝載和路徑進(jìn)行優(yōu)化處理的方法,建立了相應(yīng)的數(shù)學(xué)模型并詳細(xì)描述了遺傳算法的構(gòu)造過程。

2) 采用雙切點(diǎn)交叉方式對(duì)配送過程中的染色體進(jìn)行了自然數(shù)編碼,實(shí)現(xiàn)了染色體編碼與現(xiàn)實(shí)配送過程的一一映射,并在交叉過程中對(duì)不合法的染色體進(jìn)行了部分映射交叉修復(fù)。

3) 由于產(chǎn)品物流配送過程中的復(fù)雜性,如何將產(chǎn)品配送過程中其他因素如帶有時(shí)間窗約束的配送問題等將是下一步工作重點(diǎn)。

參 考 文 獻(xiàn)

[1] 周向明,錢建平,楊信廷,等.農(nóng)產(chǎn)品物流配送過程信息技術(shù)應(yīng)用研究進(jìn)展[J].中國(guó)農(nóng)學(xué)通報(bào),2010,26(8):323-327.ZHOU Xiangming, QIAN Jianping, YANG Xinting, et al. Review the application of information technology in agricultural products logistics and distribution[J]. Chinese Agricultural Science Bulletin,2010,26(8):323-327.

[2] Michel Gendreau, Manuel Iori, Gilbert Laporte, S.M. A Tabu Search Algorithm for a Routing and Container Loading Problem[J]. Transportation Science,2006,40(3):342-350.

[3] Guenther Fuellerer, Karl F. Doerner, Richard F. Hartl, M.I. metaheuristics for vehicle routing problems with three-dimensional loading constraints[J]. European Journal of Operational Research,2001(201):751-759.

[4] David Mester, Olli Braysy, W.D. a multi-parametric evolution strategies algorithm for vehicle routing problems[J]. Expert Systems with Applications,2007(32):508-517.

[5] Damon, E.W. the split delivery vehicle routing problem with minimum delivery amounts[J]. Transportation Research Part E,2010:1-5.

[6] Teodor Gabriel Crainic, Guido Perboli, Roberto Tadei. ts2pack: a two-level tabu search for the three-dimensional bin packing problem[J]. European Journal of Operational Research,2009(195):744-760.

[7] Bortfeldt A. A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints[J]. Computers & Operations Research,2012,39(9):2248-2257.

[8] Zhu Wenbin, Qin Hu, et al. A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP[J]. Computers & Operations Research,2012,39(9):2178-2195.

[9] Junqueira L, Oliveira J F, Carravilla M A, et al. An optimization model for the vehicle routing problem with practical three-dimensional loading constraints[J]. International Transactions in Operational Research,2013,20(5):645-666.

[10] Ruan Qingfang, Zhang Zhengqian, Miao Lixin, et al. A hybrid approach for the vehicle routing problem with three-dimensional loading constraints[J]. Computers & Operations Research,2013,40(6):1579-1589.

[11] Tao Yi, Wang Fang. An effective tabu search approach with improved loading algorithms for the 3L-CVRP[J]. Computers & Operations Research,2015,55:127-140.

[12] 孫棣華,涂平,彭光含,等.基于遺傳算法的單車運(yùn)輸配載研究[J].計(jì)算機(jī)仿真,2008,25(3):285-288.

SUN Dihua, TU Ping, PENG Guanghan, et al. Study on Single Truck Loading of Transportation Based on Genetic Algorithm[J]. Computer Simulation,2008,25(3):285-288.

Genetic Algorithm for Three Dimensional Loading Capacitated Vehicle Routing Problem in Logistics Distribution

WANG FengliBI RanWANG JiaminJIANG Bin

(National Agricultural Modern Logistics Engineering Technology Research Center,Shandong Institute of Commerce and Technology, Jinan250103)

AbstractIn order to optimize product distribution and save logistics cost, this paper addresses an approach for three-dimensional loading capacitated vehicle routing problem including three-dimensional loading problem and vehicle routing problem. Given the multiple constraints, such as vehicle weight, item properties, item volume, etc, the model is built based on genetic algorithm. The algorithm is experimentally evaluated on instances adopted from 10 instances. It can be seen from the running result that the running time is 125312ms and the best value of objective function is 104.195 which indicates that the algorithm can effectively optimize logistics cost.

Key Wordsthree dimensional loading, vehicle routing, genetic algorithm, multi-constraint

收稿日期:2015年12月7日,修回日期:2016年1月19日

基金項(xiàng)目:山東省自主創(chuàng)新專項(xiàng)-黃河三角洲特色農(nóng)產(chǎn)品電子商務(wù)平臺(tái)建設(shè)與示范(編號(hào):2013CXC90303)資助。

作者簡(jiǎn)介:王鳳麗,女,碩士,研究方向:農(nóng)產(chǎn)品物流配送。畢然,男,碩士,工程師,研究方向:農(nóng)業(yè)信息化關(guān)鍵技術(shù)。王家敏,男,碩士,副教授,研究方向:農(nóng)業(yè)信息化及農(nóng)產(chǎn)品質(zhì)量安全控制。姜濱,男,助理工程師,研究方向:農(nóng)業(yè)信息化及農(nóng)產(chǎn)品物流配送管理。

中圖分類號(hào)TP311.52

DOI:10.3969/j.issn.1672-9722.2016.06.007