托盤裝載約束下帶時間窗的配送車輛路徑優化研究

劉永，岳志城，王勇

(重慶交通大學，a.經濟與管理學院；b.智能物流網絡重慶市重點實驗室，重慶 400074)

0 引言

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

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

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

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

1 問題描述

本文引入可伸縮支撐結構托盤作為快遞貨物裝卸載體，并設計三維裝載規則集中碼放各個配送站點的貨物，這種統一有序的操作既有利于提高站點的裝卸速度，節約貨物配送時間，又能保證貨物在配送過程中規整有序，提高物流服務質量。

托盤可調節高度的支撐結構有利于根據貨物量靈活調整高度并進行堆疊規則碼放，利用三維裝載約束算法也可進一步優化托盤與車輛的空間利用率，如圖1 所示。具體做法是，根據不同客戶點用托盤進行區分，當貨物過多導致碼放高度超過最大高度限制(即車廂高度)時，采用下一個托盤進行貨物裝載，直至該客戶點的貨物碼放完成。

圖1 可伸縮立體式托盤Fig.1 Diagram of retractable three-dimensional pallet

為充分發揮物流資源的利用效率，提高車輛裝載率，對配送車輛裝載的三維空間進行優化設計調整，本文引入托盤三維裝載和客戶服務時間窗等約束，構建配送車輛裝載率最大和物流運營總成本最小的雙目標車輛路徑優化模型。傳統三維裝載方案與本文方案對比如圖2所示。

圖2 傳統方案與托盤方案對比Fig.2 Comparison between traditional scheme and pallet scheme

圖2 中，優化前為傳統三維裝載方案，該方案以容積裝載率最大為優化目標，在實際配送過程中存在區分貨物困難的情況，以及卸載貨物效率低下的問題。通過使用托盤三維裝載方案優化后，貨物通過三維裝載算法裝載入托盤，根據實際貨物量確定托盤高度，再將不同高度托盤視作長寬相同，高度不同的長方體裝載入車廂。

托盤三維裝載約束下配送車輛路徑優化方案如圖3所示。首先，將不同高度的托盤通過三維裝載優化裝入車廂，得到該車廂內所有托盤的客戶點編號、位置信息及服務時間窗等；其次，依據該車輛服務的客戶點，進行配送路徑優化；最終，得到托盤三維裝載下的配送方案最優解。在整個配送過程中，由于托盤的使用，可以以托盤為單位進行裝卸工作，提高裝卸效率，降低因裝卸過程導致的時間成本。

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

2 模型建立

2.1 研究假設

為便于研究，本文基于如下假設：

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

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

(3)車廂內貨物的質量和路線中的坡度等不影響單位距離配送成本。

(4)傳統三維裝載方案因在每個客戶點需要區分貨物歸屬，默認每個客戶點卸載過程需要至少0.5 h的時間。

(5)每輛配送車輛負責一條配送線路，任意兩輛配送車輛不進行相同的路線配送。

2.2 裝載設計

在托盤與車廂的裝載設計上，本文采用“砌墻法”進行三維裝載設計，如圖4所示，具體步驟如下。

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

Step 1 將被裝載貨物的三維按照l ＞w ＞h的順序進行重新排序。

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

Step 3 車廂高度為托盤的最大高度，以托盤最左方、下方及后方的點作為坐標原點，檢測貨物的三維是否滿足lkmn≤Lkm,wkmn≤Wkm,hkmn≤Hkm。

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

2.3 符號定義

本文涉及的相關變量和含義如表1 所示。

表1 符號定義Table 1 Symbol definitions

2.4 模型構建

本文以配送中心的物流運營總成本和車輛平均裝載率作為目標，為求得總成本最低和車輛裝載率最高，建立基于托盤三維裝載下車輛路徑優化模型。

雙目標為

對于帶有百分比的最大值和常數的最小值的多目標最優值問題，本文采用多目標線性加權法將多目標優化模型式(1)和式(2)轉換成單目標優化模型，其數值越大，表示方案越優，將雙目標轉化后形成的目標函數為

式中：S為車輛總數；β為成本轉化權重系數，0 ≤β≤1，其比重通過熵值法確定，本文取0.5，即裝載率和總成本同等重要。

約束條件為

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

計量模型中每個主要解釋變量間有可能隱含多重共線性問題，本文采用Pearson方法逐次計算了每個主要解釋變量的相關系數，所有主要解釋變量的相關系數均小于0.4，可知每個主要解釋變量間不具有嚴重的多重共線性問題。

3 算法設計

3.1 算法總體設計

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

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

3.2 時空聚類

為便于進行路徑優化，減少算法的運行時間，本文結合各物流配送點的空間位置對物流點進行時空聚類[12]，首先確定聚類中心，在聚類中心周圍內分類不同的時間范圍和空間范圍，理論上是基于余弦距離以及歐幾里得距離進行客戶點規劃，本文所用k-means時空聚類公式為

式中：Dob為時空距離；t1和t2為時間窗前后時間；δ為距離與時間的轉換系數?？蛻艟垲愂谦@得更好的物流網絡配置和確保高效配送的方法。

3.3 編碼設計

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

圖6 三維裝載解貨物編碼的結構Fig.6 Structure diagram of cargo

圖7 路徑解編碼的結構Fig.7 Structure diagram of path solution

3.4 貨物旋轉

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

3.5 遺傳操作

(1)選擇操作

通常而言，父代染色體適應度高低會影響算法結果的好壞，選擇質量較優的染色體適應度函數就會越高，被保存下來的概率也就越大。本文父代以貨箱體積由大到小排列，可以提高算法效果。

(2)交叉操作

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

圖9 交叉操作Fig.9 Cross operation

Step 1 隨機選擇兩個父代染色體命名為Z1和Z2，從范圍[1,n]選取兩個隨機數，選擇隨機數區間[Fbegin,Fend] 對應染色體中的第Fbegin到第Fend個基因的片段進行兩兩交叉互換。

Step 2 刪除新染色體片段中與原片段重復的基因，保留沒有重復的基因片段。

Step 3 對被刪除的基因片段補充未重復的基因，新補充的基因前后順序隨機排列。

Step 4 返回新的子代。

(3)變異操作

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

圖10 變異操作Fig.10 Mutation operation

3.6 終止條件

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

3.7 算法檢驗

由于缺少3LCVRP相關問題的標準數據集，為驗證算法的有效性，本文將LOH 和NEE 的三維裝載經典算例LN 算例[13]作為測試對象，并與NGOI等[14]與BISCHOFF 等[15]實驗結果進行對比，具體如表2所示。

表2 算法結果對比Table 2 Comparison of algorithm results

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

4 實例分析

4.1 實例概況

本文以重慶市某快遞公司配送中心向周圍203個客戶點配送為例進行實例分析。對傳統的三維裝載方案和托盤三維裝載方案的求解結果進行比較。車廂規格為6 m×2 m×2 m，車輛行駛速度為15 km·h-1，其中，貨車載重量15 t，租賃費和維修費用每次100元，運輸過程中違反客戶服務時間窗的懲罰成本為100 元·h-1，運輸成本為5 元·km-1，每次卸載托盤耗用5 min。

其物流配送節點分布在配送中心0的周圍，由于每個配送中心向同一站點配送的頻率通常是每天兩次，因此，物流結點的需求都是以0.5 d作為一次統計，本文以每個結點的最早時間窗為8:00，最晚時間窗互有不同?？爝f行業包裝沒有具體規格標準，因此，本文采用大小不一的6 種常用規格的貨物作為研究，具體如表3 所示，各個配送點對貨物的需求量也有所不同。

表3 貨物規格Table 3 Cargo specifications

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

4.2 結果與分析

4.2.1 托盤結果分析

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

部分客戶點因需求量不同而產生的不同高度的托盤展示如圖11 所示。由于貨物需求量的不同，客戶點的托盤高度也不相同，托盤最低高度為0.4 m，最高高度為2.0 m，當需求量超過這個限制時，會增加裝載托盤的使用。因此，部分需求量較大的客戶點托盤數會超過1個，經過算法裝載得到所有客戶點托盤平均裝載率為86.44%，能夠充分利用裝載容器的空間。

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

4.2.2 車廂結果分析

完成托盤裝載后需要進行托盤入車的規劃，本例中將客戶點分為三個聚類，分別為R1、R2、R3。圖12 表示R3 聚類中，通過3DRP 算法求解后得到的車廂內托盤擺放示意圖。其中，每個長方體被視作一個待裝載的托盤，圖示編號為托盤卸貨結點的編號與托盤高度，同一指引線的上下托盤表示碼放關系。例如，在圖12中，R3聚類的車輛1服務編號108 客戶點的托盤高為0.4 m，107 客戶點的托盤為1.5 m，并且該托盤被壓在客戶點108托盤之下。

圖12 R3聚類中部分車廂內托盤三維裝載Fig.12 Three-dimensional loading diagram of pallets in some R3 cars

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

本文所使用的托盤裝載配送方案與傳統未使用托盤的三維裝載配送方案在本例R3中的優化結果對比如表5所示?？芍?，以R3聚類區域的配送方案結果為例，本文提出的托盤三維裝載方案在總配送成本、時間成本及配送車輛運輸距離等指標方面要遠優于傳統三維裝載方案，僅車輛裝載率指標要略低于傳統三維裝載方案。傳統三維裝載方案是以最大車輛裝載率為優化目標，較少考慮貨物區分與裝卸便利性，其車內貨物區分與裝卸效率較低，由此導致的平均配送時間成本劇增，達到了7738.37 元。然而，本文提出的托盤三維裝載方案的平均時間成本為193.68元，僅為傳統三維轉載方案的2.5%，相當于節約了97.5%的時間懲罰成本。此外，傳統三維裝載方案因僅考慮車輛的最大裝載率目標，其配送車輛多頻次重復訪問客戶點，造成運輸距離劇增，也是該方案成本較高的主要原因之一。綜上所述，采用托盤三維轉載方案可以兼顧車輛高裝載率，并有效節約物流運營成本，提高車輛利用率。

表5 R3聚類中優化前后方案對比Table 5 Comparison of schemes before and after optimization

5 結論

本文針對快遞行業中存在的配送效率低和易發生爆倉等問題，在三維裝載方案的基礎上提出以可調節支撐結構高度的托盤為中間載體的托盤三維裝載方案，建立托盤三維裝載下車輛裝載率最高和配送總成本最低的雙目標模型，設計3DRP 算法進行求解，得到結論如下。

(1)使用托盤作為中間載體的兩階段裝載模型可以兼顧高裝載率與高的配送效率。當卸貨時間被作為時間成本考慮在多目標優化模型中時，托盤三維裝載方案相比單純只考慮裝載率方案，可以兼顧車輛高裝載率，并節約97.5%的時間懲罰成本。相比傳統方案來說，托盤三維裝載方案下的車輛配送路徑優化更加高效，車輛利用率更高。

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