王鳳麗　畢　然　王家敏　姜　濱

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

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

王鳳麗畢然王家敏姜濱

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

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

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

Class NumberTP311.52

1引言

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

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

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

2問題描述

圖1　3L-CVRP的示意圖

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

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

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

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

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

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

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

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

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

3模型構(gòu)建

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

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

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

4.1遺傳算法概述

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

4.2遺傳算法設(shè)計

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

4.2.1染色體編碼

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

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

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

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

4.2.3選擇操作

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

(9)

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

PP0=0

(10)

(11)

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

4.2.4遺傳操作

1) 交叉操作:對于3L-CVRP問題,如果單純地使用一般的交叉算子往往會使一些優(yōu)良的子串被破壞,并且在染色體間交叉時,無法產(chǎn)生有效的個體。在此采用一種有效的雙切點交叉算子,對于兩個選定的染色體隨機(jī)選取兩個切點,交換兩個切點間的子串。對于染色體A、B在切點9和14上進(jì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。

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

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

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

5算例仿真

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

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

6結(jié)語

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

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

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

參 考 文 獻(xiàn)

[1] 周向明,錢建平,楊信廷,等.農(nóng)產(chǎn)品物流配送過程信息技術(shù)應(yīng)用研究進(jìn)展[J].中國農(nóng)學(xué)通報,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] 孫棣華,涂平,彭光含,等.基于遺傳算法的單車運輸配載研究[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日

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

作者簡介:王鳳麗,女,碩士,研究方向:農(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)品物流配送管理。

中圖分類號TP311.52

DOI:10.3969/j.issn.1672-9722.2016.06.007