陳其賽，倪靜

基于同時(shí)送取貨多車(chē)型二維矩形裝箱問(wèn)題的優(yōu)化

陳其賽，倪靜

（上海理工大學(xué) 管理學(xué)院，上海 200093）

研究同時(shí)送取貨的二維矩形裝箱問(wèn)題，即在考慮客戶(hù)的送取需求、貨物的尺寸和質(zhì)量，以及多車(chē)型約束下求得車(chē)輛待裝空間最高平均空間利用率。提出含9種適應(yīng)度值的skyline裝箱方案設(shè)計(jì)改進(jìn)的混合禁忌搜索–遺傳優(yōu)化算法來(lái)求解帶同時(shí)送取貨約束的二維矩形裝箱問(wèn)題。通過(guò)仿真檢驗(yàn)，混合算法使車(chē)輛待裝空間平均空間利用率達(dá)到88.04%，并求得了服務(wù)8位客戶(hù)的同時(shí)送取貨裝箱方案?；趲?種適應(yīng)度值skyline裝載方案的混合禁忌搜索–遺傳優(yōu)化算法針對(duì)同時(shí)送取貨模式的二維矩形裝箱問(wèn)題能求得較高的空間利用率，并完善了同時(shí)送取貨模式在裝載方面的研究。

二維裝箱問(wèn)題；同時(shí)送取貨；多車(chē)型；skyline；禁忌搜索?遺傳算法

裝箱問(wèn)題是一個(gè)在物流行業(yè)中經(jīng)常遇到的經(jīng)典問(wèn)題，這類(lèi)問(wèn)題需要將貨物在配送中心通過(guò)合理規(guī)劃裝入配送車(chē)車(chē)廂中，再運(yùn)輸前往不同的客戶(hù)點(diǎn)。根據(jù)貨物的屬性不同，在裝載過(guò)程中往往受到不同的約束，以裝載狀態(tài)為依據(jù)可以將裝箱問(wèn)題劃分為二維裝箱和三維裝箱2種類(lèi)型。二維裝箱約束的車(chē)輛路徑問(wèn)題（Two-Dimensional Loading Capacitated Vehicle Routing Problem, 2L-CVRP）是二維矩形裝箱問(wèn)題（Two-Dimensional Orthogonal Packing Problem, 2-DOP）和帶容量約束的車(chē)輛路徑問(wèn)題（Capacitated Vehicle Routing Problem）的聯(lián)合優(yōu)化問(wèn)題，而學(xué)者們的研究以VRP為主。裝箱問(wèn)題的優(yōu)化也可以在物流作業(yè)中有效降低物流成本，其中，對(duì)于大型企業(yè)、零部件供應(yīng)商等這類(lèi)客戶(hù)群體來(lái)說(shuō)，由于標(biāo)準(zhǔn)化作業(yè)待送貨物均被打包成單層或雙層堆疊從高度考慮剛好放入車(chē)內(nèi)的狀態(tài)。此時(shí)貨物的裝載因素取決于貨物底面是否能裝入車(chē)中，而這一類(lèi)問(wèn)題就屬于2–DOP。此外，在現(xiàn)代物流中，針對(duì)不同的客戶(hù)群體存在不同的運(yùn)輸模式。對(duì)于存在多級(jí)加工工廠、供應(yīng)商的企業(yè)或者超市、便利店等這類(lèi)每日既要進(jìn)貨又有未售罄生鮮需要回收的商戶(hù)來(lái)說(shuō)，同時(shí)送取貨這一更貼近實(shí)際客戶(hù)需要的物流配送模式也正逐漸成為廣大學(xué)者的研究重點(diǎn)，因此，文中以二維矩形裝箱問(wèn)題為核心，針對(duì)實(shí)際物流環(huán)境結(jié)合同時(shí)送取貨配送模式展開(kāi)研究。

關(guān)于裝載問(wèn)題，Wei等[1]針對(duì)二維裝載問(wèn)題，提出了改進(jìn)最佳擬合啟發(fā)式算法并引入適應(yīng)度值去選擇適合裝載的貨物，再使用一種時(shí)間復(fù)雜度為的簡(jiǎn)單局部隨機(jī)搜索算法來(lái)改進(jìn)解；同時(shí)，Wei等[2]針對(duì)長(zhǎng)度不限的帶卸載約束二維裝箱問(wèn)題，引入了開(kāi)放空間的概念，提出了一種基于開(kāi)放空間的首次擬合啟發(fā)式算法來(lái)求解裝箱模式，再通過(guò)無(wú)參數(shù)的局部隨機(jī)搜索算法來(lái)改進(jìn)解；黃子釗等[3]針對(duì)實(shí)際場(chǎng)景下的自動(dòng)化碼頭集裝箱堆場(chǎng)出口箱箱位分配問(wèn)題，開(kāi)發(fā)了一種基于強(qiáng)化學(xué)習(xí)的超啟發(fā)式方法來(lái)提高堆場(chǎng)作業(yè)效率；張長(zhǎng)勇等[4]針對(duì)航空貨運(yùn)背景下流水線上貨物的裝箱問(wèn)題，在考慮一系列現(xiàn)實(shí)約束的條件下設(shè)計(jì)一種擬人啟發(fā)式與遺傳相結(jié)合的組合啟發(fā)式算法，使得貨物垛形規(guī)劃更為緊湊，穩(wěn)定性更高；張煜等[5]考慮堆場(chǎng)派送順序，構(gòu)建了混合目的港貝內(nèi)排箱問(wèn)題的整數(shù)線性規(guī)劃模型，利用改進(jìn)遺傳算法求解最小化船舶貝內(nèi)橫傾力矩；那日薩等[6]針對(duì)7種現(xiàn)實(shí)約束的集裝箱三維多箱異構(gòu)貨物裝載優(yōu)化問(wèn)題，提出了一種基于“塊”和“空間”的啟發(fā)式算法，該算法在時(shí)間效率和體積利用率上均優(yōu)于已有的同類(lèi)研究；李孫寸等[7]利用多元優(yōu)化算法實(shí)現(xiàn)三維裝箱問(wèn)題的求解說(shuō)明用多元優(yōu)化算法實(shí)現(xiàn)三維裝箱問(wèn)題的有效性和可行性；呂雪菊等[8]考慮貨物的穩(wěn)定性、定向性以及完全切割約束，通過(guò)半徑多樣化小生境遺傳算法對(duì)模型進(jìn)行求解使得車(chē)輛空間利用率最大化；Rakotonirainy等[9]研究二維條形裝載問(wèn)題，在給定了1組貨物尺寸固定，待裝空間寬度固定而高度不限的條件下提出了2種改進(jìn)的啟發(fā)式算法，通過(guò)4組測(cè)試問(wèn)題根據(jù)特征說(shuō)明算法比現(xiàn)有文獻(xiàn)的算法更加優(yōu)越；Araya等[10]研究單個(gè)集裝箱裝載問(wèn)題，研究如何使裝載貨物的集裝箱裝滿(mǎn)總體積最大化，通過(guò)提出一個(gè)新的評(píng)價(jià)函數(shù)來(lái)進(jìn)行排名從而確定適合裝載貨物的集裝箱，與其他較先進(jìn)的算法對(duì)比能得到更優(yōu)的結(jié)果。

關(guān)于同時(shí)送取貨問(wèn)題，該研究更貼近于實(shí)際，考慮車(chē)輛在實(shí)際配送任務(wù)中不同客戶(hù)的需求，國(guó)內(nèi)外已有不少學(xué)者研究，但對(duì)于同時(shí)送取貨模式的研究更多的傾向于路徑中，很少有文獻(xiàn)研究配送初期裝載階段。徐小峰等[11]考慮了同時(shí)送取貨需求帶模糊容量限制的動(dòng)態(tài)選址問(wèn)題，通過(guò)改進(jìn)五角模糊數(shù)隸屬度函數(shù)來(lái)表示模糊容量約束，再通過(guò)禁忌搜索與自適應(yīng)大規(guī)模領(lǐng)域搜索算法結(jié)合的混合算法來(lái)求得可行解；王超等[12]首次設(shè)計(jì)了回溯搜索優(yōu)化算法來(lái)解決帶時(shí)間窗同時(shí)送取貨問(wèn)題并證明有效性；Yong等[13]研究了多配送中心同時(shí)送取貨的車(chē)輛路徑問(wèn)題并利用非支配排序遺傳算法求解；周詠等[14]研究冷鏈物流同時(shí)送取貨車(chē)輛路徑優(yōu)化問(wèn)題；譚巍等[15]研究車(chē)輛負(fù)載量的不斷變化情況下引入候選集合的策略,將啟發(fā)因子設(shè)為目標(biāo)函數(shù)值并利用蟻群系統(tǒng)與2-opt結(jié)合的啟發(fā)式算法求解模型；Atefeh等[16]考慮到供應(yīng)鏈管理中殘缺產(chǎn)品庫(kù)存的不確定性，通過(guò)適用于等式約束的魯棒優(yōu)化方法以及改進(jìn)模擬退火算法、遺傳算法求解模型，并分析算法性能。

關(guān)于裝載路徑問(wèn)題，李彤等[17]考慮在不確定需求環(huán)境下，針對(duì)循環(huán)取貨問(wèn)題提出基于VRP與3D–KLP協(xié)同優(yōu)化模型并且設(shè)計(jì)了求解該模型的多階段算法；顏瑞等[18]研究包含時(shí)間窗、多車(chē)場(chǎng)因素的二維裝箱車(chē)輛路徑問(wèn)題并提出了由量子粒子群算法和引導(dǎo)式局部搜索算法組成的混合算法求解該問(wèn)題；尚正陽(yáng)等[19]考慮LIFO裝載約束設(shè)計(jì)了最少剩余開(kāi)放空間的貨物裝載方法并開(kāi)發(fā)了帶有回火過(guò)程模擬退火操作的ISA–LOS算法求解問(wèn)題；李珍萍等[20]考慮互斥產(chǎn)品的裝卸順序、運(yùn)輸時(shí)間等約束設(shè)計(jì)改進(jìn)遺傳算法求解模型；Wei等[21]針對(duì)2L–CVRP問(wèn)題利用變鄰域搜索算法進(jìn)行求解并且對(duì)skyline啟發(fā)式算法進(jìn)行改進(jìn)以適應(yīng)檢查裝載約束；Wei等[22]還針對(duì)2L–CVRP問(wèn)題設(shè)計(jì)了一種具有反復(fù)冷卻和回火機(jī)制的模擬退火算法，采用基于開(kāi)放空間的啟發(fā)式算法求解裝載方案；Corinna等[23]在考慮車(chē)輛裝載路徑問(wèn)題中的軸重問(wèn)題時(shí)車(chē)輛貨位進(jìn)行詳細(xì)的二維或三維規(guī)劃，采用外層為解決路徑問(wèn)題的自適應(yīng)大鄰域搜索算法內(nèi)層為解決裝載問(wèn)題的最深–底層–左填充算法組合的混合算法求解；C?té等[24]研究二維裝載路徑問(wèn)題，提出針對(duì)路徑的多類(lèi)子問(wèn)題量化直接解決此類(lèi)復(fù)雜問(wèn)題而不是以非綜合方式解決單個(gè)問(wèn)題可帶來(lái)的潛在效益。

綜上所述，專(zhuān)家學(xué)者們?cè)诂F(xiàn)有文獻(xiàn)中，針對(duì)同時(shí)送取貨模式的研究更多傾向于配送路徑階段，但是裝載加路徑才形成整個(gè)物流配送，而對(duì)于裝載階段的同時(shí)送取貨模式研究較少?；谕瑫r(shí)送取貨的二維矩形裝箱是實(shí)現(xiàn)同時(shí)送取貨配送模式的基礎(chǔ)，建立一個(gè)求解同時(shí)送取貨配送模式的空間利用率數(shù)學(xué)模型，選擇高效合適的裝箱策略有助于提高車(chē)輛的空間利用率，減少車(chē)輛的使用降低成本，具有研究意義。依據(jù)實(shí)際情況，物流企業(yè)往往會(huì)準(zhǔn)備多種車(chē)型的車(chē)輛根據(jù)貨物的數(shù)量大小進(jìn)行選擇匹配，這是節(jié)約成本的一個(gè)直接有效的方法。文中在以上研究基礎(chǔ)上，綜合考慮客戶(hù)同時(shí)送取貨需求、多車(chē)型車(chē)輛以及二維裝箱約束等因素，建立了基于同時(shí)送取貨的多車(chē)型二維矩形裝箱問(wèn)題模型（Two-Dimensional Orthogonal Packing Problem with Simultaneous Delivery-Pickup，2–DOPSPD），引入帶適應(yīng)度值的skyline裝箱策略尋找裝箱方案并設(shè)計(jì)改進(jìn)禁忌搜索–遺傳混合算法求解該問(wèn)題。首先對(duì)研究問(wèn)題進(jìn)行問(wèn)題描述并建立其相應(yīng)模型。其次提出設(shè)定適應(yīng)度值的skyline方法尋找裝箱方案，設(shè)計(jì)禁忌搜索–遺傳混合算法并介紹相關(guān)優(yōu)化策略。接著通過(guò)隨機(jī)生成不同規(guī)模大小的算例與其他啟發(fā)式算法進(jìn)行對(duì)比仿真實(shí)驗(yàn)，再針對(duì)非同時(shí)送取貨模式裝載算例進(jìn)行仿真求解驗(yàn)證算法的穩(wěn)定性與實(shí)用性。最后證明文中所提出的模型和算法解決同時(shí)送取貨問(wèn)題的可行性以及對(duì)未來(lái)的展望。

1 模型建立

1.1 問(wèn)題描述

文中構(gòu)建了基于同時(shí)送取貨的多車(chē)型二維矩形裝箱模型，具體問(wèn)題描述如下：存在一個(gè)容量不限的配送中心，該配送中心服務(wù)多名客戶(hù)，客戶(hù)既有送貨需求也可能存在取貨需求且需求的貨物數(shù)量、重量和尺寸均已知，每位客戶(hù)均只能接受一輛物流配送車(chē)的服務(wù)。配送中心存在多種尺寸不同的車(chē)型，根據(jù)服務(wù)客戶(hù)的需求選擇適宜的車(chē)輛進(jìn)行服務(wù)，每種車(chē)型的可裝載空間尺寸也均已知，可將該空間看成一個(gè)矩形?？蛻?hù)的所有貨物均可看成長(zhǎng)寬已知的矩形，車(chē)輛在服務(wù)過(guò)程中客戶(hù)所有的貨物均需能被裝入車(chē)中且滿(mǎn)足容量、重量約束，貨物在裝載過(guò)程中其中一邊必須與車(chē)輛的邊呈正交或者平行，貨物之間不可重疊，在任何服務(wù)點(diǎn)客戶(hù)待取貨物也需裝入車(chē)內(nèi)且滿(mǎn)足裝載約束，若無(wú)可行裝箱方案則需采用更大尺寸的車(chē)型。

1.2 符號(hào)與決策變量

為了更好地描述2–DOPSPD的數(shù)學(xué)模型，對(duì)文中使用的符號(hào)說(shuō)明如下。

為空間利用率；為客戶(hù)總數(shù)，當(dāng)時(shí)表示配送中心；分別為客戶(hù)的待送、待取貨物總數(shù)；為車(chē)輛種類(lèi)數(shù)；為客戶(hù)第件待送貨物的長(zhǎng)寬；為客戶(hù)第件待取貨物的長(zhǎng)寬；為第種車(chē)裝載區(qū)域的長(zhǎng)寬；為客戶(hù)第件待送貨物的占地面積；為客戶(hù)第件待取貨物的占地面積；表示第種車(chē)的最大可裝載面積；表示客戶(hù)第件待送貨物的質(zhì)量；表示客戶(hù)第件待取貨物的質(zhì)量；表示第種車(chē)的最大載質(zhì)量。為決策變量，分別表示當(dāng)客戶(hù)的第件待送貨物、第件待取貨物由第種車(chē)服務(wù)時(shí)則為1。

為了更直觀的表達(dá)出貨物在車(chē)中的放置情況，建立一個(gè)笛卡爾直角坐標(biāo)系。坐標(biāo)系的坐標(biāo)軸分別對(duì)應(yīng)車(chē)廂的長(zhǎng)寬，坐標(biāo)系的原點(diǎn)對(duì)應(yīng)車(chē)廂左上角。貨物的左后下角位置用坐標(biāo)表示，貨物的右前上角位置用坐標(biāo)表示，則有。表示客戶(hù)第件裝入車(chē)輛的待送貨物左后下角點(diǎn)的坐標(biāo)；表示客戶(hù)第件裝入車(chē)輛的待取貨物左后下角點(diǎn)的坐標(biāo)。

1.3 模型

基于以上的參數(shù)定義以及之前的假設(shè)條件，本文在此建立如下數(shù)學(xué)模型：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

其中，目標(biāo)函數(shù)(1)表示最大空間利用率。約束(2)表示車(chē)輛上裝載的貨物總面積不會(huì)超出車(chē)廂最大可裝載面積。約束(3)表示車(chē)輛上裝載的貨物總重量不會(huì)超出車(chē)輛最大載重。約束(4)表示貨物不能超過(guò)車(chē)廂可裝載區(qū)域邊界。約束(5)表示貨物兩兩之間不能相交。約束(6)表示貨物需要和車(chē)廂平行或者正交。約束(7)定義決策變量是0—1變量。

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

2.1 基于skyline的裝箱方案設(shè)計(jì)

求解2–DOPSPD問(wèn)題的關(guān)鍵在于如何涉及一個(gè)高效合理的裝箱方案，文中的GA–TS算法根據(jù)Bottom–Left Fill(BLF)原則見(jiàn)圖1，在skyline中選擇最左下角的線段作為放置貨物的候選區(qū)域。在圖1a中點(diǎn)3所在的線段為裝載區(qū)域中最低位置，從待裝載的貨物中選擇合適的貨物放入該位置，若存在多個(gè)適合放入的貨物則利用適應(yīng)度評(píng)價(jià)函數(shù)選擇最適合的貨物，放入后形成新的裝載區(qū)域如圖1b所示。若此時(shí)剩余待裝貨物中沒(méi)有一個(gè)貨物能放入圖1b中點(diǎn)3所在區(qū)域，即所有待裝貨物的寬度均大于，則將點(diǎn)3所在區(qū)域視為浪費(fèi)空間，將該線段提升至相鄰最低線段的高度并更新skyline，如圖1c所示，浪費(fèi)空間將不會(huì)在后續(xù)中繼續(xù)使用。

2.2 適應(yīng)度取值規(guī)則

2.3 禁忌搜索–遺傳混合算法構(gòu)建

2–DOP是以裝載率最大為目標(biāo)的裝載問(wèn)題，顯然該類(lèi)問(wèn)題屬于經(jīng)典的NP難問(wèn)題，遺傳算法、蟻群算法等元啟發(fā)式算法已被證明能很好的解決此類(lèi)問(wèn)題，其中，遺傳算法是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，該算法通過(guò)數(shù)學(xué)的方式,將問(wèn)題的求解過(guò)程轉(zhuǎn)換成類(lèi)似生物進(jìn)化中的染色體基因的交叉、變異等過(guò)程，可以較快的獲得較好的優(yōu)化結(jié)果，但是當(dāng)求解規(guī)?；驈?fù)雜度增大時(shí)該算法對(duì)新空間的探索能力有限，容易早熟，結(jié)果會(huì)收斂至局部最優(yōu)解。由于同時(shí)送取貨約束、載重約束、裝載約束以及多車(chē)輛等多重約束的制約致使2–DOPSPD問(wèn)題在使用遺傳算法求解過(guò)程中難以跳出局部較優(yōu)解，算法性能因約束較復(fù)雜而受限。為此，文中參考了文獻(xiàn)[9]中將禁忌搜索與自適應(yīng)大規(guī)模領(lǐng)域搜索算法相結(jié)合的方法，將禁忌搜索算法與遺傳算法結(jié)合，有助于算法在求解過(guò)程中增大對(duì)非更優(yōu)解的接受能力，跳出局部尋優(yōu)求得更優(yōu)解。禁忌搜索算法作為一種亞啟發(fā)式隨機(jī)搜索算法，它從一個(gè)初始解出發(fā)，選擇一系列的特定搜索方向作為試探，通過(guò)建立禁忌表選擇實(shí)現(xiàn)讓特定的目標(biāo)函數(shù)值變化最多的移動(dòng)。通過(guò)特赦準(zhǔn)則建立禁忌表可以有效幫助算法跳出局部，增加全局搜索能力這恰好能解決遺傳算法中容易陷入局部尋優(yōu)的不足問(wèn)題。綜上所述，文中通過(guò)結(jié)合2種算法的優(yōu)點(diǎn)設(shè)計(jì)該禁忌搜索–遺傳算法來(lái)解決該問(wèn)題，整體流程圖見(jiàn)圖3。

圖1 skyline示例

表1 skyline評(píng)分規(guī)則

Tab.1 Scoring rule employed in skyline

圖2 skyline評(píng)分規(guī)則示例

初始解操作的首要目的是生成一個(gè)滿(mǎn)足問(wèn)題約束的解有利于后續(xù)目標(biāo)優(yōu)化的展開(kāi)，文中采用均勻分布隨機(jī)數(shù)產(chǎn)生特定范圍內(nèi)符合約束條件的初始編碼。編碼方式采用3層編碼，第1層編碼為客戶(hù)的選擇優(yōu)先度編碼，編碼長(zhǎng)度為，范圍是1?的不重復(fù)自然數(shù)；第2層為客戶(hù)待裝貨物數(shù)量編碼，編碼長(zhǎng)度為，范圍是1?的不重復(fù)自然數(shù)；第3層為裝載順序編碼，編碼長(zhǎng)度為，范圍是1?的不重復(fù)自然數(shù)。如果，=[1, 3, 2, 2, 4, 3, 2, 1, 1, 3, 2, 4, 3, 1, 2]則1,3,2為第1層編碼，表示客戶(hù)的服務(wù)順序?yàn)榈?、第3、第2；2, 4, 3為第2層編碼，表示第1、3、2個(gè)客戶(hù)的待裝貨物分別為2、3、4個(gè)；2, 1, 1, 3, 2, 4, 3, 1, 2為第3層編碼，表示第1個(gè)客戶(hù)的裝箱順序?yàn)橄鹊?再第1，第3個(gè)客戶(hù)的裝箱順序?yàn)橄鹊?再第3最后第2，第2個(gè)客戶(hù)的裝箱順序?yàn)橄鹊?其次第3再第1最后第2。

遺傳算法的操作主要涉及輪盤(pán)賭選擇、交叉交換、變異等，文中為進(jìn)一步優(yōu)化算法，主要采用了輪盤(pán)賭選擇和交叉交換策略。輪盤(pán)賭選擇操作是以適應(yīng)度值為選擇標(biāo)準(zhǔn)，文中適應(yīng)度值通過(guò)skyline計(jì)算空間利用率得出，但是輪盤(pán)賭選擇操作具有隨機(jī)性和誤差性，因此子代染色體的5%來(lái)自于精英選擇策略,95%通過(guò)輪盤(pán)賭方法選擇；交叉交換策略為交換客戶(hù)的服務(wù)順序以及貨物的裝載順序。為防止算法過(guò)早陷入局部尋優(yōu)，引入了禁忌表，將局部最優(yōu)解加入至禁忌表中。設(shè)定禁忌長(zhǎng)度以及一個(gè)常數(shù)，在次迭代過(guò)程中禁忌訪問(wèn)，每次迭代后。

圖3 算法流程

3 數(shù)值仿真算例分析

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

為了證明該算法的有效性，現(xiàn)利用數(shù)值仿真實(shí)驗(yàn)對(duì)算法進(jìn)行實(shí)際應(yīng)用。由于目前沒(méi)有與本文問(wèn)題相關(guān)的標(biāo)準(zhǔn)測(cè)試算例，文中的實(shí)驗(yàn)算例由Matlab 9.6.0軟件的函數(shù)隨機(jī)生成。服務(wù)的客戶(hù)數(shù)量、各個(gè)客戶(hù)的待裝、卸貨物的數(shù)量、尺寸以及質(zhì)量分別在[5，15]、[0，6]、[300，1500]、[50，500]區(qū)間隨機(jī)生成，尺寸和質(zhì)量的單位分別為毫米以及千克。設(shè)置車(chē)的種類(lèi)為4種，寬度均為180，長(zhǎng)度分別為420、760、960以及1 280，對(duì)應(yīng)最大載重分別為2 000、5 000、10 000以及20 000。相關(guān)參數(shù)設(shè)置：初始種群為100，交換概率為0.99，迭代次數(shù)為200，禁忌長(zhǎng)度=20，常數(shù)=50。

3.2 算法驗(yàn)證

算法通過(guò)Matlab 9.6.0編程實(shí)現(xiàn)，計(jì)算機(jī)配置為Intel Core i7–9750H、2.60GHz、32GB RAM,在Windows10操作系統(tǒng)下運(yùn)行。文中用GA–TS算法對(duì)隨機(jī)生成的8個(gè)客戶(hù)算例進(jìn)行求解，當(dāng)完成對(duì)所有客戶(hù)的服務(wù)后，車(chē)上待取貨物的裝載示意圖見(jiàn)圖4。

圖4 GA–TS算法求解車(chē)輛裝載示圖

表2 8個(gè)客戶(hù)求解結(jié)果

Tab.2 Solution results of 8 clients

表2為在為隨機(jī)生成的8個(gè)客戶(hù)服務(wù)過(guò)程中車(chē)輛處于每一個(gè)客戶(hù)點(diǎn)時(shí)車(chē)輛的空間利用率和負(fù)載狀態(tài)。由圖4和表2可知，針對(duì)2–DOPSPD問(wèn)題，文中提出的GA–TS算法可以較好地解決。在該算法仿真求解結(jié)果中為成功完成8個(gè)客戶(hù)的裝載配送任務(wù)，選取了長(zhǎng)度為420 cm的車(chē)，平均空間利用率為88.04%，在服務(wù)客戶(hù)4時(shí)的空間利用率最低，但是也有79.08%的空間利用率滿(mǎn)足實(shí)際要求，在服務(wù)完客戶(hù)8時(shí)負(fù)載達(dá)到最大值1 854.54也滿(mǎn)足最大2 000的負(fù)載上限。

3.3 混合算法優(yōu)越性分析

為了體現(xiàn)算法在加入了禁忌搜索算法之后，加強(qiáng)了全局尋優(yōu)能力，文中同時(shí)設(shè)計(jì)了遺傳算法作為對(duì)比算法進(jìn)行仿真實(shí)驗(yàn)。由于文中研究問(wèn)題的特殊性，總貨物的數(shù)量是有限的，若貨物量過(guò)少時(shí)，2種算法均能在同樣尺寸的車(chē)中尋找到裝箱策略，無(wú)法體現(xiàn)文中GA–TS算法的優(yōu)勢(shì)，而由3.2節(jié)隨機(jī)生成的算例仿真實(shí)驗(yàn)中可知，用長(zhǎng)度為420 cm的車(chē)進(jìn)行裝載任務(wù)時(shí)空間利用率已接近完全滿(mǎn)載狀態(tài)，因此文中認(rèn)為3.1節(jié)隨機(jī)生成的算例適合作為算法對(duì)比的算例，用遺傳算法對(duì)該算例求解后所有待取貨物的裝載狀態(tài)見(jiàn)圖5。

由圖5可知，遺傳算法在對(duì)該算例求解過(guò)程中未能在長(zhǎng)度為420的車(chē)上求得適合的裝箱方案，因此只能選擇尺寸更大的車(chē)輛，選擇長(zhǎng)度為760的車(chē)之后平均空間利用率為48.65%。由此說(shuō)明，加入了禁忌搜索算法形成的GA–TS算法在解決帶同時(shí)送取貨約束的二維矩形裝箱問(wèn)題中具有優(yōu)越性。

圖5 GA算法求解車(chē)輛裝載示圖

3.4 混合算法有效性分析

為了進(jìn)一步驗(yàn)證混合算法的有效性，再分別隨機(jī)生成10、20、30、40個(gè)客戶(hù)的算例，進(jìn)行多種規(guī)模實(shí)驗(yàn)分析，考慮到貼近實(shí)際，將貨物尺寸種類(lèi)最多為10種，4種規(guī)模算例空間利用率比較結(jié)果和求解時(shí)間見(jiàn)表3。

從表3可以看出，在解決不同數(shù)量客戶(hù)的裝載需求時(shí)，文中提出的GA–TS算法均能較好的在合理的時(shí)間范圍內(nèi)得到空間率較高的裝載方案，合理的利用空間，而GA算法求解性能較差，當(dāng)貨物數(shù)量接近車(chē)空間的臨界值時(shí)很難求得裝箱方案，從而需要采用空間更大的車(chē)型。在隨機(jī)生成10個(gè)和30個(gè)客戶(hù)的算例中，盡管與文中所提出的GA–TS算法一樣采用了相同尺寸的車(chē)，但是GA算法求解所需的時(shí)間比文中所提的GA–TS更長(zhǎng)。當(dāng)客戶(hù)達(dá)到40個(gè)時(shí)，由于文中設(shè)定的車(chē)輛最大尺寸為1 280，GA算法即使使用最大尺寸的車(chē)也無(wú)法在適合的時(shí)間內(nèi)求得可行的裝箱方案，這也反應(yīng)GA算法針對(duì)復(fù)雜算例的求解效率低下，進(jìn)一步說(shuō)明文中提出的GA–TS算法實(shí)用性好、效率較高，能較好地求解同時(shí)送取貨的多車(chē)型二維矩形裝箱問(wèn)題，圖6為40個(gè)客戶(hù)160件待送取貨物算例下文中算法求解得到的最終裝載示意圖，其中待取貨物有88件。

表3 多規(guī)模算法求解結(jié)果對(duì)比

Tab.3 Comparison of multi scale algorithm results

圖6 40個(gè)客戶(hù)求解車(chē)輛裝載示圖

4 結(jié)語(yǔ)

二維裝箱問(wèn)題是典型的NP難問(wèn)題，文中為了更貼近實(shí)際物流的配送情景，以二維矩形裝箱作為研究對(duì)象，考慮了在同時(shí)送取貨約束下設(shè)置目標(biāo)函數(shù)，建立貨物裝載優(yōu)化模型。針對(duì)貨物的放置方式，設(shè)計(jì)了基于skyline的裝箱方案，同時(shí)根據(jù)貨物放入的狀態(tài)給待裝貨物設(shè)置了9種適應(yīng)度值保證待裝區(qū)域空間的最大限度利用。針對(duì)問(wèn)題的性質(zhì)，提出了一種混合算法，將遺傳算法和禁忌搜索算法相結(jié)合。以遺傳算法為基礎(chǔ)引入禁忌表，增強(qiáng)算法全局搜索能力，降低陷入局部最優(yōu)的可能，最終求得滿(mǎn)意解。通過(guò)文中仿真實(shí)驗(yàn)表明，基于帶適應(yīng)度值的skyline裝箱方案以及所提算法能有效利用空間，空間利用率較其他算法有明顯的優(yōu)勢(shì)。在貨物裝載過(guò)程中還可以考慮基于同時(shí)送取貨的三維裝載問(wèn)題，結(jié)合車(chē)輛路徑問(wèn)題等方面作進(jìn)一步拓展。

[1] WEI Li-jun, HU Qian, LEUNG S C, et al. An Improved Skyline Based Heuristic for the 2D Strip Packing Problem and Its Efficient Implementation[J]. Computers and Operations Research, 2017, 80: 113-127.

[2] WEI Li-jun, WANG Yong-sheng, CHENG Hui-bing, et al. An Open Space Based Heuristic for the 2D Strip Packing Problem with Unloading Constraints[J]. Applied Mathematical Modelling, 2019, 70: 67-81.

[3] 黃子釗, 莊子龍, 滕浩, 等. 自動(dòng)化碼頭出口箱箱位分配優(yōu)化超啟發(fā)式算法[J/OL]. 計(jì)算機(jī)集成制造系統(tǒng), 1-26[2021-05-23]. http://kns.cnki.net/ kcms/ detail/ 11. 5946.TP. 20210105. 1515.030. html.

HUANG Zi-zhao, ZHUANG Zi-long, TENG Hao, et al. Optimization of Outbound Container Space Assignment in Automated Container Terminals Based on Hyper-heuristic [J/OL]. Computer Integrated Manufacturing Systems, 1-26 [2021-05-23]. http://kns.cnki.net/kcms/detail/11.5946. TP. 20210105. 1515.030.html.

[4] 張長(zhǎng)勇, 翟一鳴, 張倩倩, 等. 考慮裝載順序約束的航空貨物裝箱問(wèn)題研究[J]. 包裝工程, 2021, 42(1): 150-156.

ZHANG Chang-yong, ZHAI Yi-ming, ZHANG Qian-qian, et al. Air Cargo Packing Considering Loading Order Constraints[J]. Packaging Engineering, 2021, 42(1): 150-156.

[5] 張煜, 程惠敏, 徐進(jìn), 等. 考慮堆場(chǎng)派送順序的混合目的港貝內(nèi)排箱及其仿真優(yōu)化[J]. 系統(tǒng)仿真學(xué)報(bào), 2018, 30(3): 831-839.

ZHANG Yu, CHENG Hui-min, XU Jin, et al. Simulation Optimization on Multi-Ports Slot Plan Problem Considering Dispatching Sequence of Containers in Yard[J]. Journal of System Simulation, 2018, 30(3): 831-839.

[6] 那日薩, 韓琪瑋, 林正奎. 三維多箱異構(gòu)貨物裝載優(yōu)化及其可視化[J]. 運(yùn)籌與管理, 2015, 24(4): 76-82.

(NA/NUO) Ri-sa, HAN Qi-wei, LIN Zheng-kui. Optimization and Visualization of Multiple 3D Container Loading Problem with Non-Identical Items[J]. Operations Research and Management Science, 2015, 24(4): 76-82.

[7] 李孫寸, 施心陵, 張松海, 等. 基于多元優(yōu)化算法的三維裝箱問(wèn)題的研究[J]. 自動(dòng)化學(xué)報(bào), 2018, 44(1): 106-115.

LI Sun-cun, SHI Xin-ling, ZHANG Song-hai, et al. Multi-Variant Optimization Algorithm for Three Dimensional Container Loading Problem[J]. Acta Automatica Sinica, 2018, 44(1): 106-115.

[8] 呂雪菊, 倪靜. 基于自適應(yīng)空間劃分策略的三維裝箱問(wèn)題[J]. 系統(tǒng)工程, 2020, 38(4): 95-102.

LYU Xue-ju, NI Jing. Three Dimensional Container Loading Problem Based on Adaptive Spatial Partition Strategy[J]. Systems Engineering, 2020, 38(4): 95-102.

[9] RAKOTONIRAINY R G, VAN VUUREN J H. Improved Metaheuristics for the Two-Dimensional Strip Packing Problem[J]. Applied Soft Computing Journal, 2020, 92: 106268.

[10] ARAYA I, GUERRERO K, NU?EZ E. VCS: A New Heuristic Function for Selecting Boxes in the Single Container Loading Problem[J]. Computers and Operations Research, 2017, 82: 27-35.

[11] 徐小峰, 鄭瑤, 鄧憶瑞. 考慮同時(shí)取送貨需求帶模糊容量限制的在線設(shè)施動(dòng)態(tài)選址問(wèn)題[J]. 系統(tǒng)工程理論與實(shí)踐, 2020, 40(9): 2438-2449.

XU Xiao-feng, ZHENG Yao, DENG Yi-rui. Fuzzy Capacitated Online Facility Dynamic Location Problem with Simultaneous Pickup and Delivery[J]. Systems Engineering-Theory & Practice, 2020, 40(9): 2438-2449.

[12] 王超, 高揚(yáng), 劉超, 等. 基于回溯搜索優(yōu)化算法求解帶時(shí)間窗和同時(shí)送取貨的車(chē)輛路徑問(wèn)題[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2019, 25(9): 2237-2247.

WANG Chao, GAO Yang, LIU Chao, et al. Vehicle Routing Problem with Simultaneous Delivery and Pickup Problem Solving by Backtracking Search Optimization Algorithm[J]. Computer Integrated Manufacturing Systems, 2019, 25(9): 2237-2247.

[13] WANG Yong, ZHANG Jie, ASSOGBA K, et al. Collaboration and Transportation Resource Sharing in Multiple Centers Vehicle Routing Optimization with Delivery and Pickup[J]. Knowledge-Based Systems, 2018, 160: 296-310.

[14] 周詠, 計(jì)瑩峰, 楊華龍, 等. 冷鏈物流同時(shí)送取貨車(chē)輛路徑優(yōu)化[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2016, 46(20): 18-26.

ZHOU Yong, JI Ying-feng, YANG Hua-long, et al. Optimization of Vehicle Routing Problem with Simultaneous Delivery and Pickup for Cold-Chain Logistics[J]. Mathematics in Practice and Theory, 2016, 46(20): 18-26.

[15] 譚巍, 文慶. 基于蟻群系統(tǒng)和2-opt方法求解同時(shí)送取貨車(chē)輛路徑VRPSPD問(wèn)題[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2015, 45(24): 235-242.

TAN Wei, WEN Qing. To Solve the Pickup Delivery Vehicle Routing VRPSPD Problem Based on Ant System and 2-Opt Method[J]. Mathematics in Practice and Theory, 2015, 45(24): 235-242.

[16] GOLSEFIDI A H, JOKAR M R A. A Robust Optimization Approach for the Production-Inventory-Routing Problem with Simultaneous Pickup and Delivery[J]. Computers & Industrial Engineering, 2020, 143: 106388.

[17] 李彤, 崔晶. 不確定需求環(huán)境下的路徑-裝載協(xié)同優(yōu)化研究[J/OL]. 系統(tǒng)工程理論與實(shí)踐, 1-29[2021-05-23]. http://kns.cnki.net/kcms/detail/ 11.2267.N. 20210203.1445. 008.html.

LI Tong, CUI Jing. Research on Route-Load Cooperative Optimization under Uncertain Demand Environment[J/OL]. Systems Engineering-Theory & Practice: 1-29[2021-05-23]. http://kns.cnki.net/ kcms/detail/ 11.2267. N. 20210203. 1445. 008.html.

[18] 顏瑞, 朱曉寧, 張群, 等. 考慮二維裝箱約束的多車(chē)場(chǎng)帶時(shí)間窗的車(chē)輛路徑問(wèn)題模型及算法研究[J]. 中國(guó)管理科學(xué), 2017(7): 67-77.

YAN Rui, ZHU Xiao-ning, ZHANG Qun, et al. Research Ofthe Model and Algorithm for Two-Dimensional Multi-Depots Capacitated Vehicle Routing Problem with Time Window Constrain[J]. Chinese Journal of Management Science, 2017(7): 67-77.

[19] 尚正陽(yáng), 顧寄南, 潘家保. 考慮LIFO裝載約束的2L-CVRP車(chē)輛路徑優(yōu)化問(wèn)題[J/OL]. 計(jì)算機(jī)集成制造系統(tǒng), 1-22[2021-05-23]. http://kns.cnki. net/kcms/ detail/11.5946. TP.20201202.1710.003.html.

SHANG Zheng-yang, GU Ji-nan, PAN Jia-bao. 2L-CVRP Vehicle Routing Problem with Lifo Loading Constraint[J/OL]. Computer Integrated Manufacturing Systems, 1-22[2021-05-23]. http://kns.cnki.net/kcms/ detail/11.5946.TP.20201202.1710.003.html.

[20] 李珍萍, 劉洪偉, 周文峰, 等. 帶裝卸順序約束的裝載配送聯(lián)合優(yōu)化算法研究[J]. 系統(tǒng)工程理論與實(shí)踐, 2019, 39(12): 3097-3110.

LI Zhen-ping, LIU Hong-wei, ZHOU Wen-feng, et al. Study on Joint Optimization Algorithm for Loading and Distribution with Loading and Unloading Sequence Constraints[J]. Systems Engineering-Theory & Practice, 2019, 39(12): 3097-3110.

[21] WEI Li-jun, ZHANG Zhen-zhen, ZHANG De-fu, et al. A Variable Neighborhood Search for the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints[J]. European Journal of Operational Research, 2015, 243(3): 798-814.

[22] WEI Li-jun, ZHANG Zhen-zhen, ZHANG De-fu, et al. A Simulated Annealing Algorithm for the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints[J]. European Journal of Operational Research, 2018, 265(3): 843-859.

[23] CORINNA K, FABIAN E J. Axle Weights in Combined Vehicle Routing and Container Loading Problems[J]. EURO Journal on Transportation and Logistics, 2021, 10: 100043.

[24] C?Té J, GUASTAROBA G, SPERANZA M. The Value of Integrating Loading and Routing[J]. European Journal of Operational Research, 2017, 257(1): 89-105.

Optimization of a Two-dimensional Rectangular Packing Problem Based on Simultaneous Delivery and Pickup of Multiple Vehicle Models

CHEN Qi-sai, NI Jing

(Business School, University of Shanghai for Science and Technology, Shanghai 200093, China)

The work aims to study the two-dimensional orthogonal packing problem with simultaneous delivery and pickup, to obtain the maximum average space utilization in the vehicle with consideration of the customers’ demands on the delivery and pickup, the dimension, weight of cargo and multiple vehicles. The hybrid tabu search genetic algorithm (TS-GA) for skyline packing scheme design with nine fitness values was proposed to solve the two-dimensional rectangular packing problem with simultaneous delivery and pickup. During the simulation test, mixing algorithm made the average space utilization in vehicles going to be loaded reach 88.04%, and the packing scheme for simultaneous delivery and pickup of 8 clients was acquired. Based on the hybrid tabu search genetic algorithm (TS-GA) for skyline packing scheme design with nine fitness values, a high space utilization for the two-dimensional rectangular packing problem with simultaneous delivery and pickup is acquired, and at the same time, the research on loading of simultaneous delivery and pickup is improved.

two-dimensional rectangular packing problem; simultaneous delivery and pickup; multiple vehicle models; skyline; hybrid tabu search genetic algorithm

U691+.34

A

1001-3563(2022)19-0226-09

10.19554/j.cnki.1001-3563.2022.19.026

2021–08–27

教育部人文社會(huì)科學(xué)基金項(xiàng)目（19YJAZH064）

陳其賽（1997—），男，碩士生，主攻智能算法、裝載路徑。

倪靜（1972—），女，博士，副教授，主要研究方向?yàn)橹悄芩惴?、在線社會(huì)網(wǎng)絡(luò)、企業(yè)信息化。

責(zé)任編輯：曾鈺嬋