考慮車輛限行和裝箱約束的車輛路徑優(yōu)化方法*

徐翔斌 任晨昊

（華東交通大學(xué)交通運輸與物流學(xué)院 南昌330013）

0 引 言

傳統(tǒng)的車輛路徑問題（vehicle routing problem，VRP）中，每個客戶由其對應(yīng)的1輛車來配送，而實際配送中經(jīng)常將客戶需求拆分為多輛車配送，這類問題稱為需求可拆分車輛路徑問題（split delivery VRP，SDVRP）。Dror等[1]首次提出并構(gòu)建了SDVRP數(shù)學(xué)模型，并證明SDVRP最優(yōu)解中任意2條路徑最多有1個相同客戶，該特性是判斷SDVRP解可行的1個基本依據(jù)。Archetti等[2]證明需求拆分能節(jié)省50%以上的成本，并且在客戶需求大于車輛限載量的SDVRP中，對車輛訪問客戶的最小次數(shù)進行約束也能實現(xiàn)配送總成本的降低。Nowak等[3]在取送貨車輛問題中引入了需求拆分概念，得出當裝載量大于車輛限載量一半以上時，獲得的效益最大。Archetti等[4]研究了SDVRP和VRP在不同場景下的計算復(fù)雜度，在大多數(shù)場景下，SDVRP均能求得解，而VRP是NP-hard問題。Sliva等[5]建立了配送中心車輛有數(shù)量限制和無數(shù)量限制下的SDVRP模型。Luo等[6]提出了考慮時間窗以及車輛實時重量相關(guān)成本下的帶時間窗的SDVRP，將單位距離的出行成本確定為車輛重量的線性函數(shù)，并提出了1個分支-定價-切割算法進行求解，結(jié)果表明：該算法求解性能良好。彭勇等[7]研究了帶二維裝箱約束的SDVRP，將遺傳算法和最底最左位置填充算法（bottom-left-fill，BLF）結(jié)合求解。張得志等[8]研究了基于隨機需求訂單可拆分的多目標VRP，添加司機工作線路均衡度為目標之一，并通過數(shù)值算例驗證所建模型和算法的有效性。Bianchessi等[9]研究了2種客戶不便配送情況下的帶時間窗的SDVRP，通過不同的目標函數(shù)來評估客戶不便配送情況下配送效率的影響。Zhang等[10]針對在線零售企業(yè)的終端配送問題，提出了1種新的訂單整合方法，首先將客戶的需求在配送站進行拆分，再以成本最小化為目標安排車輛進行配送。通過數(shù)值仿真證明該方法優(yōu)于先到先服務(wù)的配送策略。Li等[11]對帶時間窗的SDVRP問題展開研究，在允許客戶的需求能夠拆分的前提下，為每個客戶設(shè)定了1個服務(wù)時間窗，并設(shè)計了1個分支-定價-切割算法來求解該問題。徐菱等[12]建立了時間窗約束下需求可拆分的揀選與配送聯(lián)合優(yōu)化模型，并分別與需求不拆分、S-Shape策略和順序決策算法進行比較，需求拆分策略能降低33.43%，12.3%和28.17%的總成本。

針對城市交通擁擠的情況，不少大中城市出臺了交通管制措施，其中車輛限行是當前常見的交通管制手段之一，不少學(xué)者對考慮車輛限行的相關(guān)問題進行研究，Yannis等[13]考慮配送交付時間、交通流量以及通行能力等因素，研究在高峰時間內(nèi)限制部分車輛配送對雅典城市交通產(chǎn)生的影響，胡云超等[14]構(gòu)建了以限行時間窗和限行區(qū)域為約束的城市配送多目標優(yōu)化模型，趙璐[15]以城市蔬菜配送為切入點，提出了考慮客戶滿意度和蔬菜新鮮度的有道路限行的多車型帶時間窗的VRP模型，Shi等[16]提出了考慮限行區(qū)域和限行車輛數(shù)量的交通限行方案優(yōu)化方法來緩解城市交通擁堵，賴平仲等[17]建立了城市交通管制下帶軟時間窗的配送優(yōu)化模型，楊雨等[18]對比分析了實施車輛限行前后對天津市不同路段的交通流量變化的影響。葛顯龍等[19]提出面向交通限行的車輛協(xié)作與序貫式換乘聯(lián)運策略，并構(gòu)建基于車輛協(xié)作的換乘聯(lián)運模型。

不少學(xué)者對SDVRP問題及其相關(guān)變體問題進行了研究，需求拆分策略能降低企業(yè)的運輸距離和配送成本?；诖耍P者將部分客戶所在區(qū)域作為車輛限行區(qū)域，該區(qū)域內(nèi)的客戶需求只能由該區(qū)域允許通行的車輛進行配送，同時考慮車輛運輸中物品后進先出（last-in-first-out，LIFO）等裝載約束，對考慮車輛限行和二維裝箱約束的需求可拆分車輛路徑問題（SDVRP with vehicle restrictions and two-dimensional loading constraints，2LVR-SDVRP）進行研究，構(gòu)建了2LVR-SDVRP數(shù)學(xué)模型，設(shè)計了1種啟發(fā)式算法進行求解，通過數(shù)值案例對該問題進行仿真分析。

1 問題描述及模型建立

2LVR-SDVRP描述如下：存在1個配送中心有不同型號的配送車輛，客戶的位置和需求量均已知，車輛的限載量和車廂尺寸也已知。其中部分客戶位置在限行區(qū)域內(nèi)，只允許滿足該區(qū)域限行條件的車輛來配送，見圖1。

圖1 車輛限行下的配送路徑圖Fig.1 Distribution routes under vehicle restrictions

在考慮車輛限行、限重限容和物品LIFO等約束的基礎(chǔ)上，尋求1個車輛配送方案使總成本最小。假設(shè)如下。

1）每條配送路徑上所有客戶的需求量之和不超過車輛的限載量，且配送路徑的長度不超過該車輛1次允許行駛的最遠距離。

2）所有客戶的需求必須滿足，且可以由多輛車進行配送（需求可拆分），即客戶允許被服務(wù)多次。

3）物品為矩形且正交放置在車廂中，即物品的邊必須與車廂的邊平行（或重合），不能傾斜放置。

4）車廂內(nèi)的任意2個物品之間不能重疊而且不能超過車廂的邊界。

5）所有車輛從配送中心出發(fā)，完成配送任務(wù)后均須回到配送中心。

1.1 符號定義

V=V c∪{0}={0，1，…，i}：其中0為配送中心，V c={1 ，2，…，i}為客戶集合，限行區(qū)域內(nèi)客戶集合為A，A?V c。

K={1，2，…，k}：配送中心的車輛集合。

Q k：車輛k的限載量。

D k：車輛k的最遠行駛距離。

L k：車輛k的車廂長度。

W k：車輛k的車廂寬度。

fc k：車輛k1次配送的使用成本，包括駕駛員工資和保養(yǎng)費等。

vc k：車輛k的單位公里行駛成本。

E={(i，j)|i，j∈V}：節(jié)點i和j（包括配送中心和客戶）之間邊的集合。

d ij：節(jié)點i到j(luò)的行駛距離。

M i={1，2，…，mi}：客戶i的物品集合。

I imi：客戶i的第mi個物品。

l imi：物品Iimi的長度。

wimi：物品I imi的寬度。

gimi：物品I imi的重量。

qi：客戶i的物品總需求量。

G：限行區(qū)域內(nèi)允許通行車輛的限載量。

eimi k：車輛k中物品I imi左下角的橫坐標。

oimi k：車輛k中物品I imi左下角的縱坐標。

令車廂俯視圖以車頭向下時的左下角為坐標原點，水平向右，垂直向上建立坐標軸，物品Iimi在車輛k中的左下角坐標(eimi k，oimi k)，見圖2。

圖2 車廂內(nèi)物品位置示意圖Fig.2 Positions of items in the carriage

定義決策變量如下。

yik：車輛k中客戶i的配送量。

uik：客戶i在車輛k中配送順序，其中uik=0表示車輛k不配送客戶i。

1.2 數(shù)學(xué)模型

式（1）為模型的目標函數(shù)，表示所有車輛的總配送成本最小，前1項為車輛行駛成本，后1項為車輛使用成本；式（2）～（4）為需求拆分下的客戶服務(wù)約束；式（5）～（8）為車輛行駛路徑約束；式（9）為車輛限行約束，該區(qū)域內(nèi)的客戶只允許車輛限載量不超過G的車輛進行配送；式（10）表示車輛的裝載量不能超過其限載量；式（11）和式（12）表示車廂內(nèi)物品不超過車廂邊界；式（13）表示同一車廂內(nèi)，物品的物理空間不會重疊；式（14）為車廂內(nèi)物品的LIFO約束；式（15）～（16）表示車輛k不配送物品Iimi時，物品I imi在車輛k中無位置信息；式（17）～（20）為變量取值范圍。

2 算法設(shè)計

考慮到2LVR-SDVRP是1個NP問題，設(shè)計了1種啟發(fā)式算法對該問題進行求解。整個算法以SA算法為主體框架確定車輛配送路徑，然后利用BLF算法檢驗物品是否滿足二維裝箱約束，并將結(jié)果返回主框架，主框架再對路徑進行調(diào)整，直至得到最終配送方案，算法流程見圖3。考慮到頻繁調(diào)用BLF算法檢驗裝箱的可行性會花費大量的時間，這里不是在鄰域構(gòu)造時進行裝箱檢驗，而是在接收新解為當前最優(yōu)解時調(diào)用BLF算法，來加速算法求解。

圖3 算法流程圖Fig.3 Flow of the algorithm

2.1 初始解生成

SA算法的全局搜索能力較強，對初始解的依賴程度不高，可采用1種隨機方法生成初始可行解。客戶的需求可看作是相互獨立的節(jié)點，故解的編碼采用車輛和需求節(jié)點排列組合的形式，如有5個客戶，客戶2的需求量為2，其他客戶的需求為1，則解可表示為0—1—3—2—0—2—4—5—0。采用該編碼方式能直觀體現(xiàn)車輛裝載的客戶需求。

初始解的生成步驟如下。

步驟1。選擇限載量最小的車輛作為初始裝載車輛，確定當前客戶為客戶1。

步驟2。計算車輛配送完當前客戶后的總路線距離，若總路線距離超過車輛的最遠行駛距離，轉(zhuǎn)步驟5。

步驟3。判斷客戶所需物品的總重量和車輛的剩余可裝載量的比值β，若β≤1，則客戶需求被滿足；若β＞1，則對客戶需求進行拆分，拆分量為客戶所需物品的總重量與車輛的剩余可裝載量的差值。

步驟4。選擇下1個客戶，轉(zhuǎn)步驟2。

步驟5。選擇下1輛車，重復(fù)步驟2～4，直至所有客戶的需求都被滿足。

2.2 鄰域構(gòu)造

鄰域解的構(gòu)造采取文獻[20]的鄰域構(gòu)造方法，包括頂點重新指派(NS1，NS4)、頂點交換(NS2，NS5)和2-opt(NS3，NS6)，其中，NS1，NS2和NS3為路徑內(nèi)鄰域構(gòu)造，NS4，NS5和NS6為路徑間鄰域構(gòu)造。隨機選擇這6種鄰域構(gòu)造方法進行鄰域變換，能增加鄰域搜索空間從而提高解的質(zhì)量，也能擴大鄰域范圍避免算法陷入局部最優(yōu)的可能[11]。

2.2.1 路徑內(nèi)鄰域構(gòu)造

路徑內(nèi)的鄰域構(gòu)造僅對單條路徑上的客戶需求節(jié)點變換。NS1是指隨機選定1個客戶從當前位置刪除，再將其插入到路徑中的另1個位置，見圖4（a）；NS2是指隨機選擇2個客戶，互換位置，見圖4（b）；NS3是指選定2個不相鄰的客戶，并將這2個客戶之間所有客戶的位置進行逆序，見圖4（c）。

圖4 路徑內(nèi)鄰域構(gòu)造Fig.4 Neighborhood structures within a path

2.2.2 路徑間鄰域構(gòu)造

路徑間的鄰域構(gòu)造涉及2條路徑的客戶位置變換。NS4是指從某條路徑選定1個客戶從當前位置刪除，再將其插入到另1條路徑所選定的位置，見圖5（a）；NS5是指分別在2條路徑中隨機選擇1個客戶，并互換位置，見圖5（b）；NS6是在2條路徑中各自隨機選擇1個客戶，并將這2個客戶之間所有客戶以及配送中心位置進行逆序，見圖5（c）。

圖5 路徑間鄰域構(gòu)造Fig.5 Neighborhood structures between paths

2.2.3 客戶重復(fù)配送調(diào)整

考慮到需求拆分下的路徑構(gòu)造中，存在同1個客戶在1條路徑中不連續(xù)的情況，見圖6（a）。該路徑分別配送客戶1、客戶2、客戶3和客戶4，其中客戶1被先后服務(wù)了2次，產(chǎn)生了1—2—3—1—4這1條重復(fù)配送路徑。為此對該路徑進行調(diào)整，在第1次服務(wù)客戶1時滿足其在該路徑的所有需求，即調(diào)整路徑為1—1—2—3—4，見圖6（b）。

圖6 重復(fù)配送調(diào)整Fig.6 Adjusting repeated distribution

2.3 BLF算法

在得到所有車輛的配送路徑后，為了使車廂中的物品均能找到合適的位置，選用BLF算法來求解二維裝箱問題。BLF算法通過確定物品的左下標點及其寬度區(qū)間來實現(xiàn)裝箱，但可能會產(chǎn)生后進物品被阻擋的情況，見圖7（a），當前車廂中已放入物品I11，I21，I22，I31和I41，物品I51為待放入物品，按照BLF算法放置物品I51時，物品I51會被物品I41阻擋。故對已放入的物品進行覆蓋操作以避免該情況的發(fā)生，分別做最上方物品的側(cè)邊至車廂底邊的延長線，被其覆蓋的所有區(qū)域都作為該物品處理，覆蓋操作后車廂內(nèi)的物品位置見圖7（b），物品I21被合并到I31和I41中，物品I22也被合并到I41中。

圖7 物品覆蓋處理Fig.7 Deal with covering items

3 算例分析

3.1 算例描述

基于文獻[7]的客戶數(shù)據(jù)和文獻[15]的車輛信息，設(shè)計了1組具有20個客戶的算例。算例描述如下：某物流企業(yè)有2種車型的貨車提供配送服務(wù)，配送中心和客戶的位置分布在邊長為20 km的矩形區(qū)域內(nèi)，大型貨車限行區(qū)域的橫坐標范圍為[0，10]，縱坐標范圍為[5，10]，見圖8。配送中心坐標為（14.5，13），客戶位置及需求信息見表1，車輛參數(shù)見表2。

表1 客戶需求信息Tab.1 Customers'demand information

表2 車輛參數(shù)Tab.2 Vehicle parameters

圖8 客戶坐標位置Fig.8 Coordinate position of customers

相關(guān)參數(shù)設(shè)置如下：T0=500，T s=1，I=2100，U=300，α=0.997。算法采用Matlab R2017a軟件編程實現(xiàn)，計算機運行環(huán)境為Inte（lR）Core（TM）i7-4710HQ CPU@2.50G HZ處理器，16GB內(nèi)存。

3.2 運行結(jié)果

本文算法求解該算例的最優(yōu)配送方案總成本為1 751.69元，共6條配送路徑，其中客戶18的需求被拆分到2條路徑中，具體配送方案和路線見圖9和表3，表3路徑中用括號列出的為需求拆分的客戶在該路徑中的配送量。

圖9 最優(yōu)路線圖Fig.9 Optimal route

表3 最優(yōu)配送方案Tab.3 Optimal distribution plan

3.3 算法有效性分析

為檢驗算法有效性，分別選取表1中前5、前8、前11和前14個客戶作為測試算例，分別用CPLEX 12.6和所提出的算法求解這4個算例，其中CPLEX運行時間設(shè)置為3 600 s，算法取運行10次得到的求解結(jié)果和求解時間的平均值，結(jié)果見表4。可以看出，客戶規(guī)模較小的2個算例，算法求解的結(jié)果與CPLEX完全一致，但在時間上CPLEX變化較大，且隨著客戶規(guī)模的增加，算法的求解時間明顯優(yōu)于CPLEX。對于客戶規(guī)模較大的2個算例，CPLEX無法在設(shè)定的時間內(nèi)求得結(jié)果，而本文算法分別在152.53 s和177.28 s內(nèi)求得結(jié)果。

表4 測試算例求解結(jié)果Tab.4 Results of the test examples

圖10是本文算法在不同客戶規(guī)模下的求解時間，其中橫軸代表客戶規(guī)模，縱軸代表算法的平均求解時間。由圖10可見：本文算法的求解時間隨著客戶規(guī)模的變大而逐漸平緩。客戶規(guī)模從5增加到20，平均求解時間僅從69.08 s增加到192.81 s，沒有呈現(xiàn)指數(shù)級增加，說明算法有較好的求解性能。

圖10 不同客戶規(guī)模下平均求解時間Fig.10 Average solving time under different customer sizes

為了驗證本文算法的穩(wěn)定性，對算例進行15次運算，圖11為求解結(jié)果的波動情況。其中橫坐標為求解次數(shù)，縱坐標為每次（求解結(jié)果與均值的差值/均值）×100%。由圖可知，縱坐標值的波動在0.8%以內(nèi)，說明本文算法具有很好的求解穩(wěn)定性。此外，15次求解結(jié)果的標準差僅為3.2，說明所提出算法的求解質(zhì)量較高。

圖11 求解波動情況Fig.11 Fluctuations of optimal solutions

3.4 對比分析

不同限行區(qū)域客戶數(shù)下的總成本見表5，其中，總配送成本取運行10次得到的平均值，變化率為（當前方案下的總成本與無限行區(qū)域的總成本的差值/無限行區(qū)域的總成本）×100%。由表5可知，當客戶規(guī)模一定時，總配送成本隨著限行區(qū)域內(nèi)的客戶數(shù)增加而增大，并且變化率隨著客戶規(guī)模的增加而逐漸減少，在客戶規(guī)模較?。?）時，總成本變化率均高于20%，而客戶規(guī)模較大（為17）時，總成本變化率不到1%。這主要是因為無限行區(qū)域?qū)囆蜎]有要求，而車輛限行會增加車型2的車輛數(shù)，導(dǎo)致總配送成本的增加。

表5 不同限行區(qū)域客戶數(shù)下的求解結(jié)果Tab.5 Results under different numbers of customers in the vehicle-restricting area

為了進一步分析不同車型方案對總配送成本的影響，對單車型（車型2）和雙車型（車型1和2）下的總成本優(yōu)化率進行比較，優(yōu)化率為（雙車型的總成本與單車型的總成本的差值/單車型的總成本）×100%，見圖12?？梢钥闯觯S著客戶規(guī)模的增加，總成本優(yōu)化率也隨之增加。尤其在客戶規(guī)模較小時，總成本的優(yōu)化率增幅最大；在客戶規(guī)模較大（為17）時，總成本的優(yōu)化率最高，為31.27%。這主要是由于雙車型方案能在滿足車輛限載量以及客戶物品裝箱約束下，提高車輛的裝載率，實現(xiàn)總配送成本的降低。

圖12 不同車型方案結(jié)果對比Fig.12 Comparison of results under different vehicle models

4 結(jié)束語

本文以車輛的使用成本和行駛成本之和最小為目標，對2LVR-SDVRP問題進行研究。

1）提出了2LVR-SDVRP問題的數(shù)學(xué)模型和求解算法，通過數(shù)值案例驗證了模型和算法的實用性，對求解2LVR-SDVRP有較好的效果。

2）無限行區(qū)域?qū)囆筒o要求，但車輛限行措施會限制大型車輛的配送，增加總配送成本，尤其在客戶規(guī)模較小時，這種影響更加明顯。

3）相較于單車型方案，雙車型方案能在滿足客戶需求和物品裝箱的前提下，充分發(fā)揮不同車型的經(jīng)濟性。

研究2LVR-SDVRP可以完善城市車輛限行下配送車輛的調(diào)度，同時也有助于降低物流成本，提升整體的配送效率。本文建立的模型和算法是基于靜態(tài)配送網(wǎng)絡(luò)，缺乏大規(guī)模的實際算例分析。后續(xù)可考慮配送網(wǎng)絡(luò)的時變特性以及不同物品的屬性，對動態(tài)路網(wǎng)下的2LVR-SDVRP進一步研究。