基于同時送取貨多車型二維矩形裝箱問題的優(yōu)化

陳其賽，倪靜

基于同時送取貨多車型二維矩形裝箱問題的優(yōu)化

陳其賽，倪靜

（上海理工大學 管理學院，上海 200093）

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

二維裝箱問題；同時送取貨；多車型；skyline；禁忌搜索?遺傳算法

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

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

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

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

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

1 模型建立

1.1 問題描述

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

1.2 符號與決策變量

為了更好地描述2–DOPSPD的數(shù)學模型，對文中使用的符號說明如下。

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

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

1.3 模型

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

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

2 算法設(shè)計

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

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

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

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

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

圖1 skyline示例

表1 skyline評分規(guī)則

Tab.1 Scoring rule employed in skyline

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

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

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

圖3 算法流程

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

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

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

3.2 算法驗證

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

圖4 GA–TS算法求解車輛裝載示圖

表2 8個客戶求解結(jié)果

Tab.2 Solution results of 8 clients

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

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

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

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

圖5 GA算法求解車輛裝載示圖

3.4 混合算法有效性分析

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

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

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

Tab.3 Comparison of multi scale algorithm results

圖6 40個客戶求解車輛裝載示圖

4 結(jié)語

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

[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] 黃子釗, 莊子龍, 滕浩, 等. 自動化碼頭出口箱箱位分配優(yōu)化超啟發(fā)式算法[J/OL]. 計算機集成制造系統(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] 張長勇, 翟一鳴, 張倩倩, 等. 考慮裝載順序約束的航空貨物裝箱問題研究[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] 張煜, 程惠敏, 徐進, 等. 考慮堆場派送順序的混合目的港貝內(nèi)排箱及其仿真優(yōu)化[J]. 系統(tǒng)仿真學報, 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]. 運籌與管理, 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)化算法的三維裝箱問題的研究[J]. 自動化學報, 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)空間劃分策略的三維裝箱問題[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è)施動態(tài)選址問題[J]. 系統(tǒng)工程理論與實踐, 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ōu)化算法求解帶時間窗和同時送取貨的車輛路徑問題[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] 周詠, 計瑩峰, 楊華龍, 等. 冷鏈物流同時送取貨車輛路徑優(yōu)化[J]. 數(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方法求解同時送取貨車輛路徑VRPSPD問題[J]. 數(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)工程理論與實踐, 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] 顏瑞, 朱曉寧, 張群, 等. 考慮二維裝箱約束的多車場帶時間窗的車輛路徑問題模型及算法研究[J]. 中國管理科學, 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] 尚正陽, 顧寄南, 潘家保. 考慮LIFO裝載約束的2L-CVRP車輛路徑優(yōu)化問題[J/OL]. 計算機集成制造系統(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)工程理論與實踐, 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

教育部人文社會科學基金項目（19YJAZH064）

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

倪靜（1972—），女，博士，副教授，主要研究方向為智能算法、在線社會網(wǎng)絡(luò)、企業(yè)信息化。

責任編輯：曾鈺嬋