徐翔斌 任晨昊

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

0 引 言

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

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

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

1 問(wèn)題描述及模型建立

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

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

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

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

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

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

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

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

1.1 符號(hào)定義

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的最遠(yuǎn)行駛距離。

L k：車輛k的車廂長(zhǎng)度。

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

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

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

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

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

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

I imi：客戶i的第mi個(gè)物品。

l imi：物品Iimi的長(zhǎng)度。

wimi：物品I imi的寬度。

gimi：物品I imi的重量。

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

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

eimi k：車輛k中物品I imi左下角的橫坐標(biāo)。

oimi k：車輛k中物品I imi左下角的縱坐標(biāo)。

令車廂俯視圖以車頭向下時(shí)的左下角為坐標(biāo)原點(diǎn)，水平向右，垂直向上建立坐標(biāo)軸，物品Iimi在車輛k中的左下角坐標(biāo)(eimi k，oimi k)，見(jiàn)圖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）為模型的目標(biāo)函數(shù)，表示所有車輛的總配送成本最小，前1項(xiàng)為車輛行駛成本，后1項(xiàng)為車輛使用成本；式（2）～（4）為需求拆分下的客戶服務(wù)約束；式（5）～（8）為車輛行駛路徑約束；式（9）為車輛限行約束，該區(qū)域內(nèi)的客戶只允許車輛限載量不超過(guò)G的車輛進(jìn)行配送；式（10）表示車輛的裝載量不能超過(guò)其限載量；式（11）和式（12）表示車廂內(nèi)物品不超過(guò)車廂邊界；式（13）表示同一車廂內(nèi)，物品的物理空間不會(huì)重疊；式（14）為車廂內(nèi)物品的LIFO約束；式（15）～（16）表示車輛k不配送物品Iimi時(shí)，物品I imi在車輛k中無(wú)位置信息；式（17）～（20）為變量取值范圍。

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

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

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

2.1 初始解生成

SA算法的全局搜索能力較強(qiáng)，對(duì)初始解的依賴程度不高，可采用1種隨機(jī)方法生成初始可行解?？蛻舻男枨罂煽醋魇窍嗷オ?dú)立的節(jié)點(diǎn)，故解的編碼采用車輛和需求節(jié)點(diǎn)排列組合的形式，如有5個(gè)客戶，客戶2的需求量為2，其他客戶的需求為1，則解可表示為0—1—3—2—0—2—4—5—0。采用該編碼方式能直觀體現(xiàn)車輛裝載的客戶需求。

初始解的生成步驟如下。

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

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

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

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

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

2.2 鄰域構(gòu)造

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

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

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

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

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

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

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

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

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

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

2.3 BLF算法

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

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

3 算例分析

3.1 算例描述

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

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

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

圖8 客戶坐標(biāo)位置Fig.8 Coordinate position of customers

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

3.2 運(yùn)行結(jié)果

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

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

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

3.3 算法有效性分析

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

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

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

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

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

圖11 求解波動(dòng)情況Fig.11 Fluctuations of optimal solutions

3.4 對(duì)比分析

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

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

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

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

4 結(jié)束語(yǔ)

本文以車輛的使用成本和行駛成本之和最小為目標(biāo)，對(duì)2LVR-SDVRP問(wèn)題進(jìn)行研究。

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

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

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

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