智能配送車拼箱裝車和路徑優(yōu)化問題研究

高夢偉，盧 瑋 （上海交通大學 中美物流研究院 上海 200030）

0 引言

隨著人工智能技術的興起以及人力成本的逐年增長，“智慧物流”越來越受到人們的關注，其中使用智能配送車配送是“智慧物流”的重要組成部分，菜鳥、阿里、京東、順豐等企業(yè)紛紛推出智能配送車項目來提升最后一公里的配送效率。在實際應用中，京東、唯品會推出智能配送車在大學校園內配送快遞，車廂貨柜大小不一，采用模塊化設計，通過拆卸貨柜之間的隔板，可組合成多種型號的貨柜。貨柜模塊化設計可以使智能配送車容納更多的包裹尺寸，為包裹裝車提供更多的可能方案，可以通過優(yōu)化貨柜組合，選擇最優(yōu)的裝車方案，以提高智能無人車空間利用率。

智能配送車包裹配送涉及到裝載和路徑規(guī)劃兩個重要的組成部分，其中裝載要求通過合理的箱體設計來提升空間利用率，路徑規(guī)劃通過行駛線路優(yōu)化減少行駛距離。本文研究帶有拼箱設計的智能配送車路徑規(guī)劃問題，同時考慮時間窗約束，以總行駛距離最小為目標，規(guī)劃裝車和路徑行駛方案。

裝箱問題（bin packing problem）是復雜的離散組合優(yōu)化問題，根據考慮貨物尺寸的維度多少可劃分為一維、二維、三維裝箱，本文貨柜組合裝車屬于二維裝箱問題，即只考慮物品的長和寬。二維裝箱比較著名的算法包括BL[1]、BLF[2]、砌墻式啟發(fā)算法[3]、遞歸分支定界法[4]等啟發(fā)式算法。關于車輛路徑問題（vehicle routing problem），國內外的研究體系已經非常成熟，主要集中在模型應用創(chuàng)新和算法創(chuàng)新。在車輛路徑基本模型上衍生了帶時間窗的車輛路徑問題[5]、取送貨車輛路徑問題[6]、多車場車輛路徑問題[7]等，本文路徑規(guī)劃屬于帶時間窗的VRP問題；求解算法主要包括精確算法如分支定界法[8]、切平面法[9]、動態(tài)規(guī)劃法[10]等，以及啟發(fā)式算法如遺傳算法[11]、緊急搜索、蟻群算法[12]等。貨物配載和路徑優(yōu)化問題最早由Gebdreua[13]等人提出，用來解決家具配送的問題，目前把兩者結合起來的相關研究比較少。在同時考慮貨物配載和路徑優(yōu)化時，目前的解決方案主要分兩類：一類是先進行路徑規(guī)劃，然后再調用裝箱算法，檢驗每一條路徑是否滿足裝載約束，如滿足則為最優(yōu)解，如不滿足則需要重新尋找最優(yōu)解；另一類是以裝箱優(yōu)化為主，以最優(yōu)化裝載率為目標形成裝車方案，然后在此基礎上進行路徑優(yōu)化[14]。

現有的關于貨物配載和路徑規(guī)劃問題中的裝車部分，主要是考慮在整個車廂空間中如何進行物品擺放，很少考慮拼箱設計情況下的裝車問題。有學者研究汽車出廠物流的組合裝箱問題，考慮商品車和運輸工具之間特有的組合方式，不同車位可容納不同型號的商品車，形成裝載組合，是對傳統裝箱問題的新突破。本文研究的帶有拼箱設計的智能配送車裝載和路徑規(guī)劃問題，在現有理論基礎上加入了智能配送車廂體模塊設計，貨柜可進行根據貨物尺寸進行自由組合，這也是本文的創(chuàng)新之處。

1 問題建模

1.1 問題描述

智能配送車裝載和路徑規(guī)劃優(yōu)化問題可描述為：某封閉園區(qū)內使用多輛智能配送車進行包裹的末端配送，包裹按照大小和形狀的不同可分為多種尺寸，為容納各種尺寸不同的包裹，提高智能配送車空間利用率，智能配送車廂體采用模塊化設計。

智能配送車廂體模塊化設計是指智能配送車貨柜之間的可以進行任意的拼裝組合形成大小不同的貨柜，從而可以裝載不同尺寸的貨物。整個車廂被擋板劃分為多個單元貨柜，每個單元貨柜可容納最小尺寸的包裹，貨柜之間的擋板可拆卸，拆出擋板可將多個單元貨柜組合成大貨柜，拆出不同的擋板可形成不同的貨柜組合方式，從而滿足各類大小貨物的裝載。如圖1，是智能配送車貨柜設計簡圖，貨柜之間的擋板可拆卸，使多個小貨柜組合成大貨柜。圖1中A類包裹占用1個貨柜，B類包裹占據2個貨柜，C類包裹占據4個貨柜，D類包裹占據3個貨柜，以此類推。

在進行配送時，將每天的配送時間劃分為多個時間段，每個時間段智能配送車運行一個班次；對于配送時間有要求的客戶可以提前選擇配送時間。出發(fā)配送前，后臺系統需根據智能配送車不同的貨柜組合形成裝車方案并進行路徑規(guī)劃，在客戶預約的時間內將貨物送達，最終使得所有車輛總的行駛路徑最短。

圖1 貨柜組合示意圖

1.2 模型建立

根據上述問題建立智能配送車裝載和配送的數學模型，模型中包含了以下基本假設：（1）物品單向流動，即只送貨不取貨；（2）智能配送車出發(fā)位置和返回位置都在配送中心，且配送中心只有一個；（3）配送中心位置已知，各停靠點之間以及停靠點與配送中心之間的距離已知；（4）每個停靠點的配送任務量已知；（5）智能配送車不得超載；（6）智能配送車貨柜組合情況已知，且每種包裹對應的拼箱組合已知；（7）每個車輛只服務一條線路；（8）每個停靠點的客戶預約取貨時間已知；（9）在客戶規(guī)定的時間內到達停靠點；（10）適合智能配送車通行的道路已知。

車體模塊化設計使得智能配送車裝載配送問題不同于經典的車輛裝載和路徑規(guī)劃問題，關于車體組合優(yōu)化問題的研究和相關解決方法較少。針對貨柜組合這類特殊問題，本文創(chuàng)新性地引入SR集合，用以表示所有可能組合的情況。每種組合可容納的貨物編號集合為AR。模型中涉及到以下集合、參數和變量：

（1） 集 合

SR= ｛ ｛P1,P2,…,PR｝, ｛PR+1,PR+2,…｝,… ｝：貨柜組合集合。集合內每一元素表示一種組合情況，一共有R種組合，R=1,2,3,…。

sr：SR中的任意一個元素，sr∈SR，r=1,2,3,…。表示SR中每種組合的貨柜編號。

AR：貨柜組合屬于SR的對應包裹編號集合，R=1,2,3,…。

O=｛p|p=1,2,3,…,P｝，單個小貨柜的編號集合，共P個貨柜。

V=｛i|i=1,2,3,…,N ｝，包裹編號集合，共有N個包裹。

D=｛k|k=1,2,3,…,K ｝，車輛編號集合，共有K輛車。

（2） 參 數

cij：服務點i到服務點j的運輸成本；

Si：車輛在i點的服務時長；

tij：車輛從i點到j點的行駛時間；

［ai, bi］：客戶i的服務時間窗，ai指最早開始服務時間，bi指最晚開始服務時間；

Wik：k車到達i點的時間；

E：配送中心的開始時間；

L：配送中心的結束時間；

M：無窮大的正數。

（3） 變 量

模型構建如下：

上述模型說明如下：式（1）表示模型的目標函數，即總的配送成本最低；式（12）、式（13） 為模型的變量；約束條件可分為兩部分：

貨柜組合裝載約束：約束條件式（2）表示每個包裹只能被安排一次，對于任意包裹，其占用所有單元貨柜之和等于相應的體積，防止包裹被多次排班裝車；式（3）表示每個單位小貨柜最多被占用一次，對于任意單元貨柜，不允許被多次組合、多次占用；約束條件式（4）、式（5）是貨柜組合約束，式（4）表示每種組合可裝載的包裹尺寸，對于任一特定的貨柜組合，其對應的單元貨柜作為一個整體，即要么同時被占用，要么同時被空置，式（5）表示包裹不可放入其對應組合之外的貨柜集合，每個包裹只能被放入其對應特定的貨柜集合。

車輛路徑約束：約束條件式（6）、式（7）表示到達客戶點的車輛的唯一性，即到達和離開某一客戶點的為同一輛車；約束條件式（8）為車輛行駛路線約束，即要求每個車輛從配送中心出發(fā)，配送完裝載的所有貨物后再返回配送中心；約束條件式（9）、式（10）、式（11）為配送時間窗的約束，式（9）表示車輛到達下一客戶的時間晚于到達上一客戶的時間加上服務時間和路徑行駛時間，式（10）表示每個客戶點的車輛到達時間不得超出該客戶點的服務時間窗，式（11）表示每個客戶點的服務時間不得超出配送中心的時間窗。

2 模型求解

2.1 算法設計

在進行模型求解時，涉及到裝車和路徑規(guī)劃兩個部分。在VRP問題中，蟻群算法被普遍應用并且具有良好的求解結果，但考慮到貨柜組合拼接對貨物裝載的特殊約束，其難以同時完成組合裝車和路徑規(guī)劃，因此本文采用精確算法和蟻群算法相結合，優(yōu)先進行裝車方案求解，然后再進行路徑規(guī)劃。包裹裝車采用精確算法，確定每個包裹對應的裝車車輛和貨柜位置和組合，對于形成的裝車方案作為路徑規(guī)劃的輸入，每輛車的途徑點已知，運用蟻群算法求解出每輛車的規(guī)劃路徑。

本文的模型求解思路是：模型中貨物裝載部分是典型的0-1整數線性規(guī)劃問題，可以利用matlab自帶的intlinprog函數求解，以模型中式（2）～式（5）為約束條件，形成貨物的裝車方案，建立貨物和車輛貨柜的一一對應關系；然后采用蟻群算法對智能配送車進行車輛路徑規(guī)劃。將每只螞蟻的行駛路徑的長短轉化為螞蟻的信息素濃度。針對部分貨物有時間窗的約束，記錄每只螞蟻的到達時間，在計算路徑時引入懲罰函數，每次違反時間窗都會增加懲罰成本，并且增加的懲罰成本加到螞蟻的行駛距離上，從而導致信息素濃度降低，最終促使螞蟻選擇路徑較短且不違反時間窗的路徑。具體算法流程如圖2。

2.2 算法具體步驟

步驟一：輸入初始信息；步驟二：求解貨物裝車方案；步驟三：計算車輛各個收貨點的距離矩陣；步驟四：蟻群算法初始化；步驟五：螞蟻進行路徑選擇，記錄行駛路徑、到達時間；步驟六：計算并記錄最短行駛路徑和行駛距離，更新信息素濃度；步驟七：判斷是否滿足終止條件，如果滿足，進入下一步；如果不滿足，回到步驟五；步驟八：判斷是否所有車輛完成路徑規(guī)劃，如果滿足，進入下一步，否則回到步驟四；步驟九：計算終止，輸出貨物裝車方案、車輛行駛路徑、行駛距離及每個節(jié)點的到達時間。

3 算例分析

圖2 算法流程圖

以唯品會無人車為例，在某校園內有3輛智能配送車用于每天的快遞包裹配送，車行駛速為1m/s，每輛車共有28個小貨柜，貨柜組合如圖3所示。組合集合為6種組合占用的小貨柜個數分別是1,2,2,4,4,3。每種組合對應的訂單編號分別為：共有84個訂單，每天配送時段為10:00～17:00。部分客戶選擇預約配送。

圖3 貨柜組合

蟻群算法參數如下：螞蟻數量為100，信息素重要程度因子為1，啟發(fā)函數重要程度因子設置為5，信息素揮發(fā)因子為0.4，最大迭代次數1 000，懲罰值1 000。

輸入貨柜組合對應訂單編號、訂單位置、客戶預約時間窗信息，初始化參數，通過matlab算法求解，可以同時得出裝箱和路徑規(guī)劃的方案。

最終求解結果為：當天車輛運行兩個班次，圖4為第一班次車輛裝載方案；圖5為第二班次車輛裝載方案；表1為車輛配送路徑；圖6為第一班次車輛行駛路徑；圖7為第二班次車輛行駛路徑。結果如下所示：

圖4 第一班次包裹裝車組合方案

圖5 第二班次包裹裝車組合方案

行駛總距離=3.877+3.4757+5.099+3.604+4.5044+4.2956=24.8557（km）。

4 結束語

本文針對智能配送車的貨柜組合和包裹配送這一問題建立了數學模型，并針對模型設計了相應的算法，解決了智能配送車在封閉園區(qū)內配送的貨物裝車和路徑規(guī)劃問題，通過算例驗證了模型和算法的有效性。但是仍有很多不足，比如沒有考慮同一收貨人有多個貨物的情況；設計算法時沒有考慮裝載和路徑規(guī)劃之間的相互影響。后面將針對上述問題進行更深入的研究。

表1 車輛配送路徑

圖6 班次一車輛行駛路徑

圖7 班次二車輛行駛路徑