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

0 引言

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

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

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

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

1 問題建模

1.1 問題描述

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

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

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

圖1 貨柜組合示意圖

1.2 模型建立

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

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

（1） 集 合

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

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

AR：貨柜組合屬于SR的對應(yīng)包裹編號集合，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） 參 數(shù)

cij：服務(wù)點i到服務(wù)點j的運輸成本；

Si：車輛在i點的服務(wù)時長；

tij：車輛從i點到j(luò)點的行駛時間；

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

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

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

L：配送中心的結(jié)束時間；

M：無窮大的正數(shù)。

（3） 變 量

模型構(gòu)建如下：

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

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

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

2 模型求解

2.1 算法設(shè)計

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

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

2.2 算法具體步驟

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

3 算例分析

圖2 算法流程圖

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

圖3 貨柜組合

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

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

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

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

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

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

4 結(jié)束語

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

表1 車輛配送路徑

圖6 班次一車輛行駛路徑

圖7 班次二車輛行駛路徑