文/陳宏程 賈江鳴 崔志軍

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

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

隨著物流業(yè)的發(fā)展，貨車裝箱的優(yōu)化問題得到越來越多的重視

一、 問題描述

1.裝載問題描述

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

2.目標函數和約束條件

（1）目標函數

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

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

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

（2）約束條件

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

圖1：笛卡爾坐標系

圖2：子空間劃分示意圖

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

（3）模型假設

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

①車廂與貨物外形均視為規(guī)則矩形；

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

③貨物擠壓不變形；

④貨物無優(yōu)先級；

⑤忽略貨物對車廂穩(wěn)定性影響。

二、模型求解及算法分析

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

1.裝箱規(guī)則

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

（1）定位原則

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

（2）空間分割原則

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

（3）空間合并原則

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

2.多車型裝載算法

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

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

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

本文在裝載算法中添加參數“最優(yōu)性價比”，流程通過“最優(yōu)性價比”對車型進行定量篩選?！白顑?yōu)性價比”公式如下：

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

3.遺傳算法

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

（1） 編碼/解碼

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

（2）適應度函數

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

適應度函數定義如下：

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

圖5：交叉操作

表1：車輛數據表

表2：貨物數據表

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

（3）選擇操作

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

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

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

③重復第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：優(yōu)化結果對比分析表

圖6：多車型優(yōu)化分布表

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

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

（6）逆序操作

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

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

（7）擇優(yōu)保存策略

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

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

三、算例分析

1.案例數據

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

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

2.測試結果

算法的各項參數如下：

群體規(guī)模M 80

遺傳代數GEN 500

交叉概率Pc 0.9

變異概率Pm 0.05

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

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

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

3.優(yōu)化結果分析

本文算法主要優(yōu)勢：

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

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

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

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

四、結語

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