多車型多車輛貨車裝載算法及應(yīng)用

文/陳宏程 賈江鳴 崔志軍

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

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

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

一、 問(wèn)題描述

1.裝載問(wèn)題描述

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

2.目標(biāo)函數(shù)和約束條件

（1）目標(biāo)函數(shù)

裝載問(wèn)題的常見目標(biāo)函數(shù)如下：①載重量利用率最大；②空間利用率最大；③面積利用率最大；④運(yùn)輸總成本最低。

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

式(1)中Sj為j車型出車費(fèi)用，numj為j車型出車數(shù)量。

（2）約束條件

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

圖1：笛卡爾坐標(biāo)系

圖2：子空間劃分示意圖

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

（3）模型假設(shè)

結(jié)合本例實(shí)際情況給出以下假設(shè)：

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

②貨物向上放置，可水平旋轉(zhuǎn)；

③貨物擠壓不變形；

④貨物無(wú)優(yōu)先級(jí)；

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

二、模型求解及算法分析

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

1.裝箱規(guī)則

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

（1）定位原則

定位原則是貨物采用“金角銀邊草肚皮”的占角策略，貨物以左前下角坐標(biāo)為基準(zhǔn)向坐標(biāo)原點(diǎn)聚集擺放。

（2）空間分割原則

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

（3）空間合并原則

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

2.多車型裝載算法

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

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

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

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

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

3.遺傳算法

遺傳算法GA是模擬生物進(jìn)化汰弱留強(qiáng)過(guò)程的一種搜索最優(yōu)解的進(jìn)化算法。編碼P對(duì)應(yīng)貨車裝載問(wèn)題中的一種裝載方案，群體M為裝載方案的集合。適應(yīng)度函數(shù)對(duì)應(yīng)裝載問(wèn)題中的優(yōu)化目標(biāo)，個(gè)體適應(yīng)值越高，其編碼的裝載方案越優(yōu)秀，被保留下來(lái)的幾率越大。

（1） 編碼/解碼

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

（2）適應(yīng)度函數(shù)

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

適應(yīng)度函數(shù)定義如下：

圖4：多車型選擇—裝載過(guò)程示意圖

圖5：交叉操作

表1：車輛數(shù)據(jù)表

表2：貨物數(shù)據(jù)表

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

（3）選擇操作

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

①計(jì)算個(gè)體被選擇的概率，并計(jì)算出個(gè)體的累積概率；

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

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

（4）交叉操作

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

①選擇相鄰父代P’1、P’2進(jìn)行交叉，生成一個(gè)0～1隨機(jī)數(shù)，若隨機(jī)數(shù)大于Pc，則不交叉；若隨機(jī)數(shù)小于等于Pc，則對(duì)P’1、P’2進(jìn)行交叉操作；

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

③重復(fù)a、b步驟直至個(gè)體交叉結(jié)束，得到新群體{P’’1，P’’2，P’’3，…，P’’M}。

（5）變異操作

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

表3：優(yōu)化結(jié)果對(duì)比分析表

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

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

②在[1，n]之間生成2個(gè)隨機(jī)整數(shù)a和b（a＜b）作為交叉點(diǎn)，交換P’’1位于a和b上的基因；

（6）逆序操作

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

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

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

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

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

三、算例分析

1.案例數(shù)據(jù)

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

表中出車費(fèi)用單位為元/輛，長(zhǎng)、寬、高單位為mm，貨物數(shù)量單位為件。

2.測(cè)試結(jié)果

算法的各項(xiàng)參數(shù)如下：

群體規(guī)模M 80

遺傳代數(shù)GEN 500

交叉概率Pc 0.9

變異概率Pm 0.05

對(duì)上述案例數(shù)據(jù)以及各項(xiàng)參數(shù)進(jìn)行算法求解，得到結(jié)果，如下表3。

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

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

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

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

（1）本文提出的多車型、多車輛裝載算法更適合應(yīng)用于實(shí)際場(chǎng)景；

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

（3）裝載率只是評(píng)價(jià)裝載方案優(yōu)劣的一種指標(biāo)，本文給出的綜合運(yùn)輸成本指標(biāo)更適合用于評(píng)價(jià)實(shí)際裝載方案的優(yōu)劣。

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

四、結(jié)語(yǔ)

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