多車型多車輛貨車裝載算法及應用

文/陳宏程 賈江鳴 崔志軍

隨著物流業發展，貨車裝箱的優化問題得到越來越多的重視。一般情況下，一批貨物訂單生成后，形成一個貨物清單，貨物裝運需按清單順序直接裝車，貨物大小不一，導致車輛空間不能有效使用。裝箱問題是一個著名的多項式復雜程度非確定性（NP-hard）難題，直接求解有相當高的時間復雜度和空間復雜度。啟發式算法是通過特定的搜索規則和搜索策略，在搜索空間中搜索最優解，被大量運用在解決復雜問題優化中。針對裝箱問題的研究，目前大部分將裝箱問題簡化為單車型裝載問題，有些簡化為單車型單車輛裝載問題，因此盡管這些模型取得了較好的理論研究進展，但仍難以適應實際問題中的多車型多車輛裝載環境。

本文在啟發式算法的選擇上，模擬退火算法在解決復雜多目標問題上具有通用性、高效性，但其所得解的好壞受初始狀態、溫度函數等影響較大，降溫快易陷入局部最優，降溫慢則求解過程極其緩慢；蟻群算法缺點同模擬退火算法，求解過程受初始參數影響較大；遺傳算法所得解的好壞，主要依賴于遺傳代數和解組規模，若所得解不能讓人滿意，只需增加解組規模和遺傳代數，與模擬退火算法與蟻群算法相比具有一定優勢。本文選取遺傳算法并對其進行改進，降低了解的不穩定性，利用遺傳算法高效地在解空間中搜索優解序列，通過三空間裝箱原則確定序列可行解，運用python語言實現了多車型多車輛裝箱問題的優化算法。

隨著物流業的發展，貨車裝箱的優化問題得到越來越多的重視

一、 問題描述

1.裝載問題描述

區域物流配送中心的裝載問題可以被描述為：各訂單需求的貨物被裝入一定規格的瓦楞紙箱中，將這些具有不同規格的紙箱按照一定的規則裝入到不同型號且分別具有不同載重和容積限制的貨車內，在滿足車輛運力限制的情況下，選取最優車型裝載貨物，在滿足貨車容積約束的條件下，確定各貨物在車廂內的擺放位置和放置狀態，以使運輸總成本最低。模型具體參數如下：已知有n件紙箱（規格：長li、寬wi、高hi、質量gi，其中i = 1,2, ... ,n）要裝到m輛車內（已知有四種車型，各型號車輛長Lj、寬Wj、高Hj、最高載重Gj、出車費用Sj等為固定值，每種型號的車輛數不限，其中j= 1,2,3,4）。

2.目標函數和約束條件

（1）目標函數

裝載問題的常見目標函數如下：①載重量利用率最大；②空間利用率最大；③面積利用率最大；④運輸總成本最低。

本文目標為多車型多車輛的最優裝載規劃，以上單一目標無法比較不同解的優劣，故以車廂的綜合運輸總成本最低作為目標函數。模型的目標函數為：

式(1)中Sj為j車型出車費用，numj為j車型出車數量。

（2）約束條件

裝載問題常見的約束條件：方向約束、裝配優先級約束、底面積約束、長寬高約束、體積約束、載重約束、承載能力約束和穩定性約束。本例中多為輕小件貨物，故載重、承重能力約束性較弱，因此本文主要考慮約束長、寬、高約束和體積約束等。模型的約束條件為：

圖1：笛卡爾坐標系

圖2：子空間劃分示意圖

式（2）、（3）、（4）表示裝入j車型車廂貨物的長、寬、高均不超過貨車車廂的長、寬、高，式（5）表示裝入j車型車廂的貨物總體積不超過貨車車廂體積。

（3）模型假設

結合本例實際情況給出以下假設：

①車廂與貨物外形均視為規則矩形；

②貨物向上放置，可水平旋轉；

③貨物擠壓不變形；

④貨物無優先級；

⑤忽略貨物對車廂穩定性影響。

二、模型求解及算法分析

在裝箱順序上，許多知名學者進行了深入研究。本文利用改進算子的遺傳算法結合三空間裝箱原則，在裝箱順序和車輛分配維度下求解最優裝載方案。

1.裝箱規則

本文采用笛卡爾坐標系，如圖1。為使裝載率盡可能高，本文考慮定位原則、空間分割與空間合并等幾個啟發式原則。

（1）定位原則

定位原則是貨物采用“金角銀邊草肚皮”的占角策略，貨物以左前下角坐標為基準向坐標原點聚集擺放。

（2）空間分割原則

為了保證貨物在裝載過程中不存在“懸空”現象，本文對空間采用三空間分割法。George和Robinson最先提出了三空間劃分原則，當貨物放入車廂后，該車廂被分割成前、右、上三個子空間。每個子空間在繼續裝填貨物過程中，放入貨物后同樣被分割為三個子空間，如此循環往復直至無法裝下。子空間劃分，如圖2。

（3）空間合并原則

子空間劃分過程中會不斷地出現小空間，過多的小空間不利于貨物的繼續裝載，可通過空間合并形成新的較大空間。合并過程，如圖3 (a)-(c)。

2.多車型裝載算法

圖3：左右/前后/上下空間合并

裝載算法可分為在線和離線兩種：在線算法是先到的箱子先裝箱，而離線算法是在所有物品就緒的情況下再進行裝箱。結合發貨情況，本文采用了離線裝箱中的FFD裝載算法。為使算法適應多車型多車輛裝載模型，本文在FFD裝載算法的基礎上添加了車型的選擇，裝載示意圖，如圖4。

圖4為多車型選擇—裝載過程示意圖。

本文在裝載算法中添加參數“最優性價比”，流程通過“最優性價比”對車型進行定量篩選。“最優性價比”公式如下：

式中ξ為“最優性價比”，λ為車輛裝載率，Sj為j車型的固定出車費用，Vj為j車型的車廂體積。

3.遺傳算法

遺傳算法GA是模擬生物進化汰弱留強過程的一種搜索最優解的進化算法。編碼P對應貨車裝載問題中的一種裝載方案，群體M為裝載方案的集合。適應度函數對應裝載問題中的優化目標，個體適應值越高，其編碼的裝載方案越優秀，被保留下來的幾率越大。

（1） 編碼/解碼

待裝貨物的裝載順序是由啟發式原則確定的，直接采用裝箱順序作為個體P的編碼。初始編碼順序由程序隨機得到。

（2）適應度函數

適應度函數為目標函數運輸總成本的倒數。為了更好地表達解的優劣，添加最后一輛車的空間裝載率最低（折算成車輛使用費用）來輔助表示適應度函數。首先，在裝載結果中，方案顯示車型與車輛數目都相同時，僅車型費用乘以車輛數目無法準確表達裝箱排序的優劣，增加將最后一輛車的空間裝載率最低作為指標以輔助判別最優方案，可以加快算法的收斂；其次，最后一輛車空間利用率最低可以為臨時/緊急訂單貨物的裝載提供便利，該類貨物可不通過計算直接置于最后一輛車，節省計算時間。

適應度函數定義如下：

圖4：多車型選擇—裝載過程示意圖

圖5：交叉操作

表1：車輛數據表

表2：貨物數據表

式中Vlast為最后一輛車裝載貨物總體積，Vlast為最后一輛車裝載體積。

（3）選擇操作

本文采用輪盤賭作為選擇方法。群體M中父代群體為{P1，P2，P3，…，PM}。選擇操作步驟如下：

①計算個體被選擇的概率，并計算出個體的累積概率；

②生成一個0～1隨機數，若隨機數在個體累積概率區間之間，則該個體被選中；

③重復第a、b步，得到M個個體組成新群體{P’1，P’2，P’3，…，P’M}。

（4）交叉操作

交叉概率為Pc，交叉群體為{P’1，P’2，P’3，…，P’M}。交叉步驟如下：

①選擇相鄰父代P’1、P’2進行交叉，生成一個0～1隨機數，若隨機數大于Pc，則不交叉；若隨機數小于等于Pc，則對P’1、P’2進行交叉操作；

②在[1，n]之間生成2個隨機整數a和b（a＜b）作為交叉點，交換P’1、P’2位于a和b之間的基因段，如圖5。

③重復a、b步驟直至個體交叉結束，得到新群體{P’’1，P’’2，P’’3，…，P’’M}。

（5）變異操作

變異概率為Pm，變異群體為變異步驟如下：

表3：優化結果對比分析表

圖6：多車型優化分布表

①選擇父代P’’1進行變異，生成一個0～1隨機數，若隨機數大于Pm，則不變異。若隨機數小于等于Pm，則對P(2)1進行變異操作；

②在[1，n]之間生成2個隨機整數a和b（a＜b）作為交叉點，交換P’’1位于a和b上的基因；

（6）逆序操作

逆序概率為1，即所有個體都進行逆序操作。逆序操作會對比逆序前后適應度函數，若逆序后適應度比逆序前適應度更優，則保存該逆序操作結果，否則仍保存原先序列。具體操作步驟如下：

①在[1，n]之間生成2個隨機整數a和b（a＜b）作為逆序點，將P(4)1位于a和b上的基因逆轉排序；

（7）擇優保存策略

擇優保存策略是為了避免父代中的優秀個體在遺傳迭代的過程中消失。其步驟為：

①計算父代群體{P1，P2，P3，…，PM}中所有個體的適應值，找出父代中適應值最高的那個個體，即最優父代（其適應度值為Fmax）；計算子代群體中所有的個體適應值，找出子代中適應值最小的那個個體，即最劣子代（其適應度值為F(4)min）；

三、算例分析

1.案例數據

為更好地對比算法優劣，本文選用行業內的一些基礎數據，在保證數據量基本相等的前提下，把貨物尺寸進行改動，以適應實際裝載問題；其中，第一輛車的大小與原對比數據中的車型大小一致。具體數據如下：見表1、表2。

表中出車費用單位為元/輛，長、寬、高單位為mm，貨物數量單位為件。

2.測試結果

算法的各項參數如下：

群體規模M 80

遺傳代數GEN 500

交叉概率Pc 0.9

變異概率Pm 0.05

對上述案例數據以及各項參數進行算法求解，得到結果，如下表3。

運用多車型多車輛算法優化模型得到12組解，結果分布，如圖6。

如圖6試驗數據表明，本算法的空間利用率平均分布在88.53%～93.33%之間，空間裝載率可到93.33%。

3.優化結果分析

本文算法主要優勢：

（1）本文提出的多車型、多車輛裝載算法更適合應用于實際場景；

（2）本文的算法空間利用率可達到93.33%，與同類研究文獻比較，本文的算法在空間利用率上存在一定優勢；

（3）裝載率只是評價裝載方案優劣的一種指標，本文給出的綜合運輸成本指標更適合用于評價實際裝載方案的優劣。

綜上所述，本文裝箱算法在空間利用率以及綜合成本上均具有一定優勢。

四、結語

本文對某區域物流配送中心運輸問題的貨車裝箱方案進行了優化，給出了裝箱優化算法，并進行了實例研究，通過實例數據對比結果可知，本文的裝箱算法具有一定的成本和裝載率優勢。本文研究模型不足之處在于：該模型主要針對區域物流配送中心，運用范圍較為局限，后期將對該模型進行改進，使其能夠適應更多領域。