劉永，岳志城，王勇

(重慶交通大學(xué)，a.經(jīng)濟(jì)與管理學(xué)院；b.智能物流網(wǎng)絡(luò)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400074)

0 引言

隨著全球電子商務(wù)的快速發(fā)展，快遞配送問(wèn)題經(jīng)常被推上新聞，貨物堆積如山，碼放不規(guī)整造成快遞配送效率低，裝卸不靈活，貨損率高的問(wèn)題，影響著快遞服務(wù)質(zhì)量。三維裝載方案作為一種車(chē)輛空間規(guī)劃的方法，可以提高車(chē)廂容積的利用率，降低不合理運(yùn)輸。而配送車(chē)輛路徑優(yōu)化可以?xún)?yōu)化配送線(xiàn)路，降低配送成本。在上述背景下，采用三維裝載約束下帶時(shí)間窗的配送車(chē)輛路徑問(wèn)題(Three-Dimensional Loading Constrain with Vehicle Routing Problem,3LCVRP)顯得日益重要。

三維裝箱問(wèn)題(Three-Dimensional Bin Packing Problem,3DBPP)是在三維空間內(nèi)，對(duì)內(nèi)部貨物進(jìn)行規(guī)則和有序的排列與堆積，以求得最佳擺放方式提高空間內(nèi)的利用率。三維裝箱屬于NP 難題，國(guó)內(nèi)外學(xué)者對(duì)此展開(kāi)許多由淺及深，由單一變復(fù)雜的一系列研究。其中，GEORGE等[1]最早提出一種基于“層”或“墻”的高裝載率裝箱方案，求得集裝箱內(nèi)空間的充分利用。隨后，崔會(huì)芬等[2]和EL 等[3]考慮裝載容積和貨物放置方向等約束，提高裝載過(guò)程的合理性。李俊等[4]使用貝內(nèi)排箱的方式，將貨物堆積的不同塊再進(jìn)行塊堆積，進(jìn)一步提高集裝箱裝載率。在容器選擇中，GZARA等[5]提出采用層級(jí)理論結(jié)合搜索樹(shù)算法，基于層的列生成方法解決了將貨物碼放到托盤(pán)中的問(wèn)題，卻沒(méi)有繼續(xù)完成車(chē)輛裝載部分。楊玉冰等[6]將包裝半成品裝入集裝箱的兩階段二次裝箱問(wèn)題，為二維切割和裝箱組合問(wèn)題的求解提供了有效途徑。三維裝箱的相關(guān)理論研究已取得較為豐富的研究成果，但在三維模型與方法的實(shí)際操作便利性和需求客戶(hù)點(diǎn)的貨物高效區(qū)分等實(shí)際應(yīng)用方面還存在一些待完善的問(wèn)題。為此，在GZARA等[5]和楊玉冰等[6]研究的基礎(chǔ)上，本文提出采用托盤(pán)進(jìn)行兩階段二次裝箱的思路，以解決貨物裝卸靈活性問(wèn)題。

在三維裝載與路徑優(yōu)化結(jié)合考慮的問(wèn)題上，GENDREAU 等[7]提出3LCVRP模型。根據(jù)GENDREAU等使用的示例，CHEN等[8]設(shè)計(jì)禁忌搜索算法，綜合考慮客戶(hù)對(duì)服務(wù)時(shí)間的要求，最終產(chǎn)生了更為高質(zhì)量的解決方案。BORTFELDT等[9]建立混合整數(shù)規(guī)劃模型，考慮三維裝箱約束和車(chē)輛的分配使用，并改進(jìn)遺傳算法進(jìn)行求解，該研究對(duì)三維裝載車(chē)輛調(diào)度問(wèn)題的推進(jìn)具有推動(dòng)作用。杜博文等[10]針對(duì)少量的貨物類(lèi)型，提供一種帶三維裝載的一對(duì)一配送路徑優(yōu)化。王勇等[11]對(duì)三維裝載約束下4種貨物類(lèi)型求解車(chē)輛路徑優(yōu)化方案，并與經(jīng)典的啟發(fā)式算法結(jié)果進(jìn)行對(duì)比。但三維裝載與路徑結(jié)合考慮的難度較大，目前，研究?jī)H考慮了較少的貨物類(lèi)型，現(xiàn)實(shí)快遞行業(yè)中存在著諸多不同大小的包裝。

綜上所述，快遞配送過(guò)程中采用三維裝箱可提高貨物裝卸效率和車(chē)輛裝載率，且配送路徑優(yōu)化也可節(jié)約時(shí)間成本和縮短運(yùn)輸距離。為此，充分考慮快遞貨物在配送裝箱過(guò)程中因貨箱種類(lèi)眾多帶來(lái)的裝卸作業(yè)復(fù)雜和不靈活等問(wèn)題，本文引入可伸縮高度的托盤(pán)作為貨物碼放載體，擴(kuò)展了貨物類(lèi)型，探索托盤(pán)三維裝載方案對(duì)配送成本的影響，并結(jié)合“砌墻”理論構(gòu)建基于托盤(pán)三維裝載約束下帶時(shí)間窗的配送車(chē)輛路徑問(wèn)題3DPP-VRP (Three Dimensional Packing of Pallet-Vehicle Routing Problem)模型，依照貨物體積生成三維裝載初始解，通過(guò)時(shí)空聚類(lèi)生成路徑初始解，結(jié)合啟發(fā)式求解方法完成對(duì)托盤(pán)裝載、車(chē)輛裝載和配送路徑的求解過(guò)程。

1 問(wèn)題描述

本文引入可伸縮支撐結(jié)構(gòu)托盤(pán)作為快遞貨物裝卸載體，并設(shè)計(jì)三維裝載規(guī)則集中碼放各個(gè)配送站點(diǎn)的貨物，這種統(tǒng)一有序的操作既有利于提高站點(diǎn)的裝卸速度，節(jié)約貨物配送時(shí)間，又能保證貨物在配送過(guò)程中規(guī)整有序，提高物流服務(wù)質(zhì)量。

托盤(pán)可調(diào)節(jié)高度的支撐結(jié)構(gòu)有利于根據(jù)貨物量靈活調(diào)整高度并進(jìn)行堆疊規(guī)則碼放，利用三維裝載約束算法也可進(jìn)一步優(yōu)化托盤(pán)與車(chē)輛的空間利用率，如圖1 所示。具體做法是，根據(jù)不同客戶(hù)點(diǎn)用托盤(pán)進(jìn)行區(qū)分，當(dāng)貨物過(guò)多導(dǎo)致碼放高度超過(guò)最大高度限制(即車(chē)廂高度)時(shí)，采用下一個(gè)托盤(pán)進(jìn)行貨物裝載，直至該客戶(hù)點(diǎn)的貨物碼放完成。

圖1 可伸縮立體式托盤(pán)Fig.1 Diagram of retractable three-dimensional pallet

為充分發(fā)揮物流資源的利用效率，提高車(chē)輛裝載率，對(duì)配送車(chē)輛裝載的三維空間進(jìn)行優(yōu)化設(shè)計(jì)調(diào)整，本文引入托盤(pán)三維裝載和客戶(hù)服務(wù)時(shí)間窗等約束，構(gòu)建配送車(chē)輛裝載率最大和物流運(yùn)營(yíng)總成本最小的雙目標(biāo)車(chē)輛路徑優(yōu)化模型。傳統(tǒng)三維裝載方案與本文方案對(duì)比如圖2所示。

圖2 傳統(tǒng)方案與托盤(pán)方案對(duì)比Fig.2 Comparison between traditional scheme and pallet scheme

圖2 中，優(yōu)化前為傳統(tǒng)三維裝載方案，該方案以容積裝載率最大為優(yōu)化目標(biāo)，在實(shí)際配送過(guò)程中存在區(qū)分貨物困難的情況，以及卸載貨物效率低下的問(wèn)題。通過(guò)使用托盤(pán)三維裝載方案優(yōu)化后，貨物通過(guò)三維裝載算法裝載入托盤(pán)，根據(jù)實(shí)際貨物量確定托盤(pán)高度，再將不同高度托盤(pán)視作長(zhǎng)寬相同，高度不同的長(zhǎng)方體裝載入車(chē)廂。

托盤(pán)三維裝載約束下配送車(chē)輛路徑優(yōu)化方案如圖3所示。首先，將不同高度的托盤(pán)通過(guò)三維裝載優(yōu)化裝入車(chē)廂，得到該車(chē)廂內(nèi)所有托盤(pán)的客戶(hù)點(diǎn)編號(hào)、位置信息及服務(wù)時(shí)間窗等；其次，依據(jù)該車(chē)輛服務(wù)的客戶(hù)點(diǎn)，進(jìn)行配送路徑優(yōu)化；最終，得到托盤(pán)三維裝載下的配送方案最優(yōu)解。在整個(gè)配送過(guò)程中，由于托盤(pán)的使用，可以以托盤(pán)為單位進(jìn)行裝卸工作，提高裝卸效率，降低因裝卸過(guò)程導(dǎo)致的時(shí)間成本。

圖3 托盤(pán)三維裝載下的配送方案Fig.3 Distribution scheme under three-dimensional pallet loading

2 模型建立

2.1 研究假設(shè)

為便于研究，本文基于如下假設(shè)：

(1) 快遞貨物包裝均為形狀規(guī)則的長(zhǎng)方體盒狀，本文不考慮袋裝貨物的裝載情形。

(2)對(duì)于貨物重心穩(wěn)定與包裝支撐方面暫不考慮，本文僅計(jì)算裝載率部分。

(3)車(chē)廂內(nèi)貨物的質(zhì)量和路線(xiàn)中的坡度等不影響單位距離配送成本。

(4)傳統(tǒng)三維裝載方案因在每個(gè)客戶(hù)點(diǎn)需要區(qū)分貨物歸屬，默認(rèn)每個(gè)客戶(hù)點(diǎn)卸載過(guò)程需要至少0.5 h的時(shí)間。

(5)每輛配送車(chē)輛負(fù)責(zé)一條配送線(xiàn)路，任意兩輛配送車(chē)輛不進(jìn)行相同的路線(xiàn)配送。

2.2 裝載設(shè)計(jì)

在托盤(pán)與車(chē)廂的裝載設(shè)計(jì)上，本文采用“砌墻法”進(jìn)行三維裝載設(shè)計(jì)，如圖4所示，具體步驟如下。

圖4 “砌墻”裝載方式Fig.4 Wall loading method

Step 1 將被裝載貨物的三維按照l(shuí) ＞w ＞h的順序進(jìn)行重新排序。

Step 2 對(duì)貨物體積按照由大到小的順序進(jìn)行排序生成初始遍歷序列。

Step 3 車(chē)廂高度為托盤(pán)的最大高度，以托盤(pán)最左方、下方及后方的點(diǎn)作為坐標(biāo)原點(diǎn)，檢測(cè)貨物的三維是否滿(mǎn)足lkmn≤Lkm,wkmn≤Wkm,hkmn≤Hkm。

Step 4 對(duì)于沒(méi)有超出托盤(pán)約束的貨物首先檢測(cè)ykmn+wkmn≤Wkm。若超出，則檢測(cè)下一個(gè)貨物；沒(méi)有超出托盤(pán)約束，則檢測(cè)xkmn+lkmn≤Lkm。若超出，則更新y坐標(biāo)，即向前一層進(jìn)行裝載；沒(méi)有超出，便繼續(xù)檢測(cè)貨物的高是否能放入當(dāng)前z軸，即zkmn+hkmn≤Hkm。若超出，更新x坐標(biāo)，向右進(jìn)行裝載；若不超出，便在當(dāng)前位置放入貨物并重新更新x軸、y軸及z軸的坐標(biāo)。例如，在空托盤(pán)內(nèi)放入第一個(gè)貨物，檢測(cè)均未超出托盤(pán)三維后，其新的檢測(cè)點(diǎn)更新為z1=z0+h1，x1=x0，y1=y0。

2.3 符號(hào)定義

本文涉及的相關(guān)變量和含義如表1 所示。

表1 符號(hào)定義Table 1 Symbol definitions

2.4 模型構(gòu)建

本文以配送中心的物流運(yùn)營(yíng)總成本和車(chē)輛平均裝載率作為目標(biāo)，為求得總成本最低和車(chē)輛裝載率最高，建立基于托盤(pán)三維裝載下車(chē)輛路徑優(yōu)化模型。

雙目標(biāo)為

對(duì)于帶有百分比的最大值和常數(shù)的最小值的多目標(biāo)最優(yōu)值問(wèn)題，本文采用多目標(biāo)線(xiàn)性加權(quán)法將多目標(biāo)優(yōu)化模型式(1)和式(2)轉(zhuǎn)換成單目標(biāo)優(yōu)化模型，其數(shù)值越大，表示方案越優(yōu)，將雙目標(biāo)轉(zhuǎn)化后形成的目標(biāo)函數(shù)為

式中：S為車(chē)輛總數(shù)；β為成本轉(zhuǎn)化權(quán)重系數(shù)，0 ≤β≤1，其比重通過(guò)熵值法確定，本文取0.5，即裝載率和總成本同等重要。

約束條件為

式(5)～式(10)表示擺放第n個(gè)貨物時(shí)，不能超出托盤(pán)的三維限制；式(11)～式(13)表示任意兩個(gè)貨物之間不發(fā)生空間上的重疊；式(14)～式(16)表示任意兩個(gè)托盤(pán)之間不發(fā)生空間上的重疊；式(17)表示每條運(yùn)輸線(xiàn)路只派一輛車(chē)進(jìn)行配送；式(18)是消除路線(xiàn)規(guī)劃中的子回路；式(19)表示車(chē)內(nèi)貨物重量之和不得超過(guò)運(yùn)輸車(chē)輛的最大載重量；式(20)～式(22)是決策變量約束。

計(jì)量模型中每個(gè)主要解釋變量間有可能隱含多重共線(xiàn)性問(wèn)題，本文采用Pearson方法逐次計(jì)算了每個(gè)主要解釋變量的相關(guān)系數(shù)，所有主要解釋變量的相關(guān)系數(shù)均小于0.4，可知每個(gè)主要解釋變量間不具有嚴(yán)重的多重共線(xiàn)性問(wèn)題。

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

3.1 算法總體設(shè)計(jì)

本文在混合模擬退火-遺傳算法的基礎(chǔ)上設(shè)計(jì)3DRP算法進(jìn)行求解，首先，對(duì)空間內(nèi)各個(gè)物流節(jié)點(diǎn)的位置進(jìn)行時(shí)空聚類(lèi)并更新聚類(lèi)中心，得到較好的聚類(lèi)結(jié)果；隨后，將該聚類(lèi)中心中各個(gè)結(jié)點(diǎn)的貨物進(jìn)行三維裝載，其中，包括生成初始序列，對(duì)初始序列的貨箱進(jìn)行檢驗(yàn)，得到初始解，計(jì)算適應(yīng)度；隨后，隨機(jī)生成旋轉(zhuǎn)后的貨物信息，通過(guò)模擬退火-遺傳算法的交叉、變異及選擇等操作生成新的序列，并進(jìn)行檢驗(yàn)得到新的解，在不斷的退火迭代過(guò)程中選擇最高的適應(yīng)度對(duì)應(yīng)的解，對(duì)于沒(méi)有裝載的貨物打包成新的待裝載貨物裝入下一個(gè)托盤(pán)，終止條件中ΔC表示迭代前后適應(yīng)度函數(shù)的增量，Te表示當(dāng)前退火溫度；然后，根據(jù)聚類(lèi)結(jié)果進(jìn)行車(chē)廂裝載，針對(duì)車(chē)廂內(nèi)的客戶(hù)進(jìn)行路徑優(yōu)化，產(chǎn)生最優(yōu)方案；最后，得出總路程、裝載率、總成本以及裝卸時(shí)間等結(jié)果，算法流程如圖5所示。

圖5 算法流程Fig.5 Algorithm flow chart

3.2 時(shí)空聚類(lèi)

為便于進(jìn)行路徑優(yōu)化，減少算法的運(yùn)行時(shí)間，本文結(jié)合各物流配送點(diǎn)的空間位置對(duì)物流點(diǎn)進(jìn)行時(shí)空聚類(lèi)[12]，首先確定聚類(lèi)中心，在聚類(lèi)中心周?chē)鷥?nèi)分類(lèi)不同的時(shí)間范圍和空間范圍，理論上是基于余弦距離以及歐幾里得距離進(jìn)行客戶(hù)點(diǎn)規(guī)劃，本文所用k-means時(shí)空聚類(lèi)公式為

式中：Dob為時(shí)空距離；t1和t2為時(shí)間窗前后時(shí)間；δ為距離與時(shí)間的轉(zhuǎn)換系數(shù)?？蛻?hù)聚類(lèi)是獲得更好的物流網(wǎng)絡(luò)配置和確保高效配送的方法。

3.3 編碼設(shè)計(jì)

編碼過(guò)程主要包括三維裝載的編碼和配送車(chē)輛路徑優(yōu)化的編碼，其編碼結(jié)構(gòu)采用元胞數(shù)組的形式。三維裝載的編碼表示為cargo[o,k,m]，即在第o個(gè)客戶(hù)聚類(lèi)中，第k輛車(chē)的第m個(gè)托盤(pán)內(nèi)貨物的三維裝載狀態(tài)。其中，該客戶(hù)點(diǎn)的貨物若在該托盤(pán)內(nèi)，則貨物狀態(tài)為1；否則，為0。三維裝載結(jié)果依據(jù)貨物長(zhǎng)、寬及高等大小判斷，采用“砌墻”法進(jìn)行三維碼放判斷，得到貨物在托盤(pán)中碼放的三維空間布局狀態(tài)。三維裝載編碼的結(jié)構(gòu)如圖6 所示。對(duì)于路徑優(yōu)化的編碼部分，客戶(hù)點(diǎn)編碼采用自然數(shù)編碼，每輛車(chē)的行駛路線(xiàn)被存在元胞數(shù)組route[o,k]，即第o個(gè)客戶(hù)聚類(lèi)中，第k輛車(chē)的行駛路徑被存在route 中的第o行，第k列中。路徑解在元胞數(shù)組route中的結(jié)構(gòu)如圖7所示。route[o,2]表示在聚類(lèi)o中，配送車(chē)輛2從配送中心0出發(fā)，首先到達(dá)客戶(hù)點(diǎn)4，隨后，依序到達(dá)客戶(hù)點(diǎn)2，5，1，最后，返回配送中心0，該解在算法中呈現(xiàn)在元胞數(shù)組內(nèi)的第o行，第2列中，其內(nèi)容是[0,4,2,5,1,0]。

圖6 三維裝載解貨物編碼的結(jié)構(gòu)Fig.6 Structure diagram of cargo

圖7 路徑解編碼的結(jié)構(gòu)Fig.7 Structure diagram of path solution

3.4 貨物旋轉(zhuǎn)

為充分利用車(chē)內(nèi)空間，本文算法在迭代之前對(duì)貨物的擺放形態(tài)進(jìn)行預(yù)處理，即貨物的旋轉(zhuǎn)。算法中將貨物的6 種旋轉(zhuǎn)給予相同的比重，利用函數(shù)int[r and(·)×6]+1 得以實(shí)現(xiàn)，分別實(shí)現(xiàn)1～6的6種選擇，對(duì)應(yīng)旋轉(zhuǎn)方式分別為貨物未旋轉(zhuǎn)、繞x軸旋轉(zhuǎn)、繞y軸旋轉(zhuǎn)、繞z軸旋轉(zhuǎn)、繞z軸旋轉(zhuǎn)后繞y軸旋轉(zhuǎn)及繞x軸旋轉(zhuǎn)后繞y軸旋轉(zhuǎn)。具體展示如圖8所示。

3.5 遺傳操作

(1)選擇操作

通常而言，父代染色體適應(yīng)度高低會(huì)影響算法結(jié)果的好壞，選擇質(zhì)量較優(yōu)的染色體適應(yīng)度函數(shù)就會(huì)越高，被保存下來(lái)的概率也就越大。本文父代以貨箱體積由大到小排列，可以提高算法效果。

(2)交叉操作

在交叉操作過(guò)程中，由于配送中心是配送路徑的出發(fā)點(diǎn)和結(jié)束點(diǎn)，所以，為避免交叉操作過(guò)程中丟失配送中心，本文在進(jìn)行交叉操作之前先將染色體前后剔除配送中心基因0，然后，再進(jìn)行交叉操作。交叉采用局部映射的方法，首先，對(duì)隨機(jī)產(chǎn)生的片段進(jìn)行兩兩互換；然后，進(jìn)行重復(fù)基因的替換，兩部分的交叉操作是相互獨(dú)立的。交叉操作如圖9所示，具體步驟如下。

圖9 交叉操作Fig.9 Cross operation

Step 1 隨機(jī)選擇兩個(gè)父代染色體命名為Z1和Z2，從范圍[1,n]選取兩個(gè)隨機(jī)數(shù)，選擇隨機(jī)數(shù)區(qū)間[Fbegin,Fend] 對(duì)應(yīng)染色體中的第Fbegin到第Fend個(gè)基因的片段進(jìn)行兩兩交叉互換。

Step 2 刪除新染色體片段中與原片段重復(fù)的基因，保留沒(méi)有重復(fù)的基因片段。

Step 3 對(duì)被刪除的基因片段補(bǔ)充未重復(fù)的基因，新補(bǔ)充的基因前后順序隨機(jī)排列。

Step 4 返回新的子代。

(3)變異操作

變異操作是在選擇和交叉操作產(chǎn)生的染色體后，隨機(jī)選擇某個(gè)或者是多個(gè)基因產(chǎn)生突變，如圖10所示。首先，給予一定的概率Pm作為突變概率選擇一條染色體產(chǎn)生突變；其次，隨機(jī)選擇染色體中的兩個(gè)基因進(jìn)行互換，產(chǎn)生新的子代，變異互換基因的過(guò)程中不考慮產(chǎn)生重復(fù)基因，因此，不需要進(jìn)行重復(fù)基因的刪除和補(bǔ)充的操作。

圖10 變異操作Fig.10 Mutation operation

3.6 終止條件

設(shè)退火算法的初始溫度為T(mén)0，算法的終止溫度為T(mén)end。退火時(shí)降溫的速度滿(mǎn)足Te+1=ωTe，ω為[0.8,1.0]內(nèi)的溫度系數(shù)，該系數(shù)隨機(jī)產(chǎn)生。當(dāng)溫度小于等于終止溫度或迭代次數(shù)達(dá)到100次，便終止循環(huán)。貨物量存在較多的情況時(shí)，需要第2個(gè)甚至第3個(gè)托盤(pán)進(jìn)行裝載，根據(jù)以上貨物裝載的編碼方式會(huì)得到裝載好的貨物編碼為1，因此，要將未裝載的貨物(編碼為0 的貨物)進(jìn)行打包，生成初始解進(jìn)行下一托盤(pán)的裝載。

3.7 算法檢驗(yàn)

由于缺少3LCVRP相關(guān)問(wèn)題的標(biāo)準(zhǔn)數(shù)據(jù)集，為驗(yàn)證算法的有效性，本文將LOH 和NEE 的三維裝載經(jīng)典算例LN 算例[13]作為測(cè)試對(duì)象，并與NGOI等[14]與BISCHOFF 等[15]實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，具體如表2所示。

表2 算法結(jié)果對(duì)比Table 2 Comparison of algorithm results

通過(guò)對(duì)比可以看出，在平均容積裝載率為68.2%情況下，本算法與其他算法求解差異不大，3 種算法求解裝載率結(jié)果均在68%～69%，但本文算法擁有更少的平均未裝載貨物量，在快遞行業(yè)是尤為重要的，因?yàn)檫@意味著更少的延誤訂單產(chǎn)生以及更少的申訴量，因此，可以認(rèn)為本算法在裝載方面是有效性的。

4 實(shí)例分析

4.1 實(shí)例概況

本文以重慶市某快遞公司配送中心向周?chē)?03個(gè)客戶(hù)點(diǎn)配送為例進(jìn)行實(shí)例分析。對(duì)傳統(tǒng)的三維裝載方案和托盤(pán)三維裝載方案的求解結(jié)果進(jìn)行比較。車(chē)廂規(guī)格為6 m×2 m×2 m，車(chē)輛行駛速度為15 km·h-1，其中，貨車(chē)載重量15 t，租賃費(fèi)和維修費(fèi)用每次100元，運(yùn)輸過(guò)程中違反客戶(hù)服務(wù)時(shí)間窗的懲罰成本為100 元·h-1，運(yùn)輸成本為5 元·km-1，每次卸載托盤(pán)耗用5 min。

其物流配送節(jié)點(diǎn)分布在配送中心0的周?chē)?，由于每個(gè)配送中心向同一站點(diǎn)配送的頻率通常是每天兩次，因此，物流結(jié)點(diǎn)的需求都是以0.5 d作為一次統(tǒng)計(jì)，本文以每個(gè)結(jié)點(diǎn)的最早時(shí)間窗為8:00，最晚時(shí)間窗互有不同。快遞行業(yè)包裝沒(méi)有具體規(guī)格標(biāo)準(zhǔn)，因此，本文采用大小不一的6 種常用規(guī)格的貨物作為研究，具體如表3 所示，各個(gè)配送點(diǎn)對(duì)貨物的需求量也有所不同。

表3 貨物規(guī)格Table 3 Cargo specifications

由表3中可以看出，貨物序號(hào)是按照貨長(zhǎng)大小要求從大到小排列，這有利于“砌墻”理論產(chǎn)生更高的裝載率。貨物1～貨物3屬于中型貨物，貨物4屬于中小型貨物，貨物5和貨物6屬于小型貨物。

4.2 結(jié)果與分析

4.2.1 托盤(pán)結(jié)果分析

該算例所設(shè)計(jì)的3DRP 算法基于改進(jìn)的混合模擬退火-遺傳算法進(jìn)行改進(jìn)，其中，初始溫度T0=100，終止溫度Tend=1，種群規(guī)模為150。本文將貨物裝入長(zhǎng)1 m，寬1.2 m的托盤(pán)，限制托盤(pán)裝載最高的高度為2.0 m，算法運(yùn)行環(huán)境為Matlab R2018a,Windows10 Intel(R) Core(TM) i7-7660U CPU@2.50 GHz。

部分客戶(hù)點(diǎn)因需求量不同而產(chǎn)生的不同高度的托盤(pán)展示如圖11 所示。由于貨物需求量的不同，客戶(hù)點(diǎn)的托盤(pán)高度也不相同，托盤(pán)最低高度為0.4 m，最高高度為2.0 m，當(dāng)需求量超過(guò)這個(gè)限制時(shí)，會(huì)增加裝載托盤(pán)的使用。因此，部分需求量較大的客戶(hù)點(diǎn)托盤(pán)數(shù)會(huì)超過(guò)1個(gè)，經(jīng)過(guò)算法裝載得到所有客戶(hù)點(diǎn)托盤(pán)平均裝載率為86.44%，能夠充分利用裝載容器的空間。

圖11 不同高度部分托盤(pán)裝載展示Fig.11 Display of partial pallet loading at different heights

4.2.2 車(chē)廂結(jié)果分析

完成托盤(pán)裝載后需要進(jìn)行托盤(pán)入車(chē)的規(guī)劃，本例中將客戶(hù)點(diǎn)分為三個(gè)聚類(lèi)，分別為R1、R2、R3。圖12 表示R3 聚類(lèi)中，通過(guò)3DRP 算法求解后得到的車(chē)廂內(nèi)托盤(pán)擺放示意圖。其中，每個(gè)長(zhǎng)方體被視作一個(gè)待裝載的托盤(pán)，圖示編號(hào)為托盤(pán)卸貨結(jié)點(diǎn)的編號(hào)與托盤(pán)高度，同一指引線(xiàn)的上下托盤(pán)表示碼放關(guān)系。例如，在圖12中，R3聚類(lèi)的車(chē)輛1服務(wù)編號(hào)108 客戶(hù)點(diǎn)的托盤(pán)高為0.4 m，107 客戶(hù)點(diǎn)的托盤(pán)為1.5 m，并且該托盤(pán)被壓在客戶(hù)點(diǎn)108托盤(pán)之下。

圖12 R3聚類(lèi)中部分車(chē)廂內(nèi)托盤(pán)三維裝載Fig.12 Three-dimensional loading diagram of pallets in some R3 cars

經(jīng)過(guò)算法得出方案最終解如表4所示。其中，R1、R2 及R3 聚類(lèi)分別得到7 條、7 條及5 條配送線(xiàn)路，平均裝載率分別為81.23%，84.04%，83.6%。所有線(xiàn)路平均每輛車(chē)配送成本為606.84元，平均裝載率為83.02%，且車(chē)輛的平均里程均未超過(guò)100 km。

本文所使用的托盤(pán)裝載配送方案與傳統(tǒng)未使用托盤(pán)的三維裝載配送方案在本例R3中的優(yōu)化結(jié)果對(duì)比如表5所示?？芍訰3聚類(lèi)區(qū)域的配送方案結(jié)果為例，本文提出的托盤(pán)三維裝載方案在總配送成本、時(shí)間成本及配送車(chē)輛運(yùn)輸距離等指標(biāo)方面要遠(yuǎn)優(yōu)于傳統(tǒng)三維裝載方案，僅車(chē)輛裝載率指標(biāo)要略低于傳統(tǒng)三維裝載方案。傳統(tǒng)三維裝載方案是以最大車(chē)輛裝載率為優(yōu)化目標(biāo)，較少考慮貨物區(qū)分與裝卸便利性，其車(chē)內(nèi)貨物區(qū)分與裝卸效率較低，由此導(dǎo)致的平均配送時(shí)間成本劇增，達(dá)到了7738.37 元。然而，本文提出的托盤(pán)三維裝載方案的平均時(shí)間成本為193.68元，僅為傳統(tǒng)三維轉(zhuǎn)載方案的2.5%，相當(dāng)于節(jié)約了97.5%的時(shí)間懲罰成本。此外，傳統(tǒng)三維裝載方案因僅考慮車(chē)輛的最大裝載率目標(biāo)，其配送車(chē)輛多頻次重復(fù)訪(fǎng)問(wèn)客戶(hù)點(diǎn)，造成運(yùn)輸距離劇增，也是該方案成本較高的主要原因之一。綜上所述，采用托盤(pán)三維轉(zhuǎn)載方案可以兼顧車(chē)輛高裝載率，并有效節(jié)約物流運(yùn)營(yíng)成本，提高車(chē)輛利用率。

表5 R3聚類(lèi)中優(yōu)化前后方案對(duì)比Table 5 Comparison of schemes before and after optimization

5 結(jié)論

本文針對(duì)快遞行業(yè)中存在的配送效率低和易發(fā)生爆倉(cāng)等問(wèn)題，在三維裝載方案的基礎(chǔ)上提出以可調(diào)節(jié)支撐結(jié)構(gòu)高度的托盤(pán)為中間載體的托盤(pán)三維裝載方案，建立托盤(pán)三維裝載下車(chē)輛裝載率最高和配送總成本最低的雙目標(biāo)模型，設(shè)計(jì)3DRP 算法進(jìn)行求解，得到結(jié)論如下。

(1)使用托盤(pán)作為中間載體的兩階段裝載模型可以兼顧高裝載率與高的配送效率。當(dāng)卸貨時(shí)間被作為時(shí)間成本考慮在多目標(biāo)優(yōu)化模型中時(shí)，托盤(pán)三維裝載方案相比單純只考慮裝載率方案，可以兼顧車(chē)輛高裝載率，并節(jié)約97.5%的時(shí)間懲罰成本。相比傳統(tǒng)方案來(lái)說(shuō)，托盤(pán)三維裝載方案下的車(chē)輛配送路徑優(yōu)化更加高效，車(chē)輛利用率更高。

(2)配送效益與各成本構(gòu)成因素成反比，但與車(chē)輛裝載率成正比。在車(chē)輛配送過(guò)程中，車(chē)廂容積裝載率不作為配送成本的一部分，卻影響著配送成本，在3 個(gè)聚類(lèi)范圍內(nèi)的裝載率分別為81.23%，84.04%，83.60%，對(duì)應(yīng)的成本分別為5381.02，3086.20，3062.97元。為提高3LCVRP模型的性能，一方面可以降低各類(lèi)成本因素，同時(shí)，也需要提高配送車(chē)輛的裝載率。