伊俊敏 蘇志雄

(廈門理工學院經(jīng)濟與管理學院 廈門 361024)

0 引 言

入廠物流是將不同供應(yīng)商的貨物通過集約運輸送到工廠指定地點存儲等使用的過程，其中車輛裝載和路線設(shè)計是二個關(guān)鍵點，這首先是帶容量限制的車輛路徑問題(CVRP)，其次是裝車裝箱問題[1].CVRP幾十年來一直是運籌學的熱點研究問題之一，但傳統(tǒng)的CVRP模型并未考慮裝車，入廠物流需要綜合考慮路徑和裝箱這兩個相互制約、不可分割的過程，不考慮裝箱，車輛優(yōu)化路線上的貨物無法全部裝車；忽視路徑優(yōu)化，車廂裝得再滿成本也降不下來[2].

Gendreau等[3]從家具配送實踐中提出了帶三維裝箱約束的車輛路徑問題(3L-CVRP)的研究，引起國內(nèi)外[4-6]學者的不斷關(guān)注.帶裝箱約束的車輛路徑問題將裝箱作為CVRP新的約束條件，來保證路線上各節(jié)點的貨物能夠裝入車廂空間，并滿足不同客戶貨物的裝卸貨要求.這類問題將原本兩個NP-難的運籌學問題集成考慮，模型與算法更加復(fù)雜.帶裝箱約束的路徑復(fù)合問題主要包括二維、三維裝載約束的(2L-CVRP, 3L-CVRP)、多疊車輛路徑問題(MP-VRP[7])、托盤裝箱車輛路徑問題(PPVRP[8])等.

由于帶裝箱約束路徑類問題的多重復(fù)雜性，它們的求解方法集中在啟發(fā)式算法和混合算法.而裝箱約束方面，借助已有裝箱問題的研究成果和容器、單品、裝載和貨物相關(guān)的四類裝載約束劃分，具體問題結(jié)合裝載實踐要求相應(yīng)考慮其中的幾個方面.對于中小尺寸的弱異性貨物(即每品種均有一定數(shù)量)，裝載之前還存在是否先托盤裝箱的問題.托盤裝箱問題(MPLP)考慮一批等同貨物如何裝入盡量少的托盤中，現(xiàn)在已經(jīng)得到較好解決.這樣，等同貨物托盤單元化之后，就是PPVRP的簡單情況，用常規(guī)CVRP就可以求解.

另一方面，裝載相關(guān)的約束還涉及到同一客戶的貨物是否分批裝車，打破CVRP“客戶唯一拜訪”的假設(shè)就是需求可拆分的車輛路徑問題(SDVRP)[9].SDVRP對一些線路總成本有顯著降低，但拆分會額外增加物流作業(yè)交易和管理成本.物流實踐中部分客戶節(jié)點的需求量大于車輛容量(稱為大節(jié)點)的現(xiàn)象也比較常見，對我們涉及大量裝載裝箱作業(yè)的問題，要考慮SDVRP以前很少考慮的三維裝載約束.

本文針對某公司大量弱異性貨物入廠物流問題，考慮需求拆分、托盤裝箱、分類堆碼等多方面實際裝載可能性，建立不同的裝載約束CVRP復(fù)合問題模型，并進行實例數(shù)據(jù)算法求解和物流綜合成本比較分析，不僅必要而且有現(xiàn)實意義.

1 入廠物流貨物裝車決策

裝配型工廠生產(chǎn)經(jīng)常需要批量采購多種不同的貨物，對于中小尺寸貨物每品種都有不菲的數(shù)量，即弱異性貨物.它們的裝載及運輸集約決策問題，首先是貨物要否托盤化以及托盤類型選擇決策；非托盤化時則有裝車方式的選擇：是分類堆碼裝車還是三維優(yōu)化裝車.決策方案包括：①貨物先托盤化，再裝車；②包裝貨物在車廂內(nèi)分類堆碼裝車1L；③采用3L-CVRP的三維優(yōu)化裝車，總的決策樹見圖1.對應(yīng)托盤類型、裝車方式和a,b兩種車型最終形成8個決策分枝.然后就是不同方案的建模、求解和結(jié)果比較分析.

圖1 入廠物流優(yōu)化決策樹

2 三種方案的模型與求解

2.1 基本假設(shè)

1) 各取貨節(jié)點i(i=0, 1, 2, …,n，其中i=0表示工廠)間的距離cij均已知且對稱.

2) 貨物包裝的長、寬、高分別是li,wi,hi，所需數(shù)量為qi，裝箱裝車時hi不能倒置.

3) 對同一個實例，容器、車輛都是同質(zhì)的，即對任一車k(k=1, 2, …,m)，容量為Q，車廂內(nèi)尺寸長、寬、高分別是L,W,H；對任一托盤p(p=1,2,…,r)，托盤尺寸長、寬分別是B,D.

4) 每一車輛從工廠出發(fā)并回到工廠，中間經(jīng)若干個節(jié)點裝取貨物，并且盡可能一次取完，需求拆分除外.

5) 一條路線一輛車，每條路線所取貨物不超過車輛容量限制.

2.2 托盤化裝車路徑方案

這一方案實際上就是MPLP和CVRP的先后實施.首先要考慮托盤化MPLP問題，即尋求托盤單元內(nèi)正交擺放同尺寸箱子(B,D,l,w)實例下最大數(shù)量的問題.按照文獻[11]的算法，針對中小尺寸數(shù)據(jù)不超過托盤底面尺寸，分別得到每種貨物在兩種國標托盤(國際I、日式T)上的單層裝碼樣式和各自需要的托盤單元數(shù)量，見圖2.

圖2 MPLP結(jié)果示例：290 mm×210 mm尺寸貨物依次在國際和日式托盤上，單層18和20個

這些限定尺寸的托盤單元在車輛上的裝載數(shù)量確定，又是一個MPLP的(L,W,B,D)實例，最終有了各節(jié)點的托盤單元數(shù)量qi和車輛的托盤單元容量Q，形成常規(guī)的CVRP問題如下所示的三指數(shù)流動模型.

(1)

(2)

(p=1,2,…,n,?k)

(3)

(4)

(5)

(?k,S?V{0},|V|>2)

(6)

(7)

式(2)保證每一節(jié)點僅由一輛車拜訪一次；式(3)為節(jié)點流量守恒約束，每節(jié)點流入與流出的交通量相等；式(4)～(5)保證每臺車在各節(jié)點只被使用一次，m臺車輛均從工廠出發(fā)并回到工廠；式(6)為子回路消除約束，采用集合的形式表示；式(7)保證所取貨物不超過車輛的容積.

2.3 1L-CVRP方案

包裝貨物在貨車車廂內(nèi)分類堆碼的傳統(tǒng)裝車方式實際上就是一維堆碼裝車(1L-CVRP)[10].通常貨物裝箱優(yōu)化涉及到三維容器裝箱問題，但對于本問題弱異性小尺寸貨物，采用三維容器裝箱問題的砌墻法，可以近似算出每種貨物在車廂內(nèi)同方向堆碼的墻厚ti(包裝箱長或?qū)挼恼麛?shù)倍)[11].這種近似算法設(shè)定每堵墻在車廂內(nèi)垂直于車輛L方向，且橫貫整個車廂寬度，不考慮不同墻在車廂寬度方向的拼接，在CVRP的基礎(chǔ)之上增加了裝車長度一維裝載約束，即在2.2節(jié)CVRP模型的基礎(chǔ)之上，增加下式可以建立1L-CVRP模型.

(8)

式(8)保證裝入車輛中的每種貨物的分類堆碼的墻厚ti合計不超過車廂總長，這也是該方案的特殊之處，裝箱約束條件簡化為一維線性約束.

求解時將不同貨物作為單獨的節(jié)點來處理，解決了通常需要需求可拆分路徑問題才能解決的、節(jié)點需求量大于車輛容量的難題.這一模型求解采用遺傳算法實現(xiàn).

2.4 3L-CVRP方案

3L-CVRP主要是在式(7)的基礎(chǔ)之上增加三維裝箱諸約束.問題的不同之處在于存在超過車輛容量的大節(jié)點，基于文獻[12]所提出的帶需求拆分的3L-CVRP，在模型的基礎(chǔ)之上放松對車輛唯一訪問的限制(式(2)的=1改為≥1)，來解決大節(jié)點問題.該方案的基本思路是重點考慮那些接近或超過車輛容量的節(jié)點，先構(gòu)造這類節(jié)點的裝車方式；于是剩余節(jié)點的問題則是3L-CVRP所能解決的.該方案求解的具體步驟如下.

步驟1由容器裝箱問題的遺傳算法來產(chǎn)生每個節(jié)點的裝車計劃.先對一個客戶的箱子采用建墻法生成若干“墻”.這里墻與一維優(yōu)化的主要區(qū)別是可以由不同箱子組成，以充分利用空間，各“墻”依次沿車輛長度方向豎立排列，互不交疊.接下來用遺傳算法來確定一個客戶所形成的全部墻在車廂內(nèi)的排列組合以使總深度最小，不同節(jié)點的裝車計劃可以在后面的路徑計劃中進一步合并.對大節(jié)點可能形成多個裝車計劃，每裝車計劃對應(yīng)一輛車；但對填充率超過一定比例(按三維裝箱結(jié)果，如60%)的近大節(jié)點，優(yōu)先考慮與小節(jié)點組合形成不能再裝的完整裝車計劃.這些裝好的節(jié)點就從待求解節(jié)點集中刪除.

步驟2用混合算法來解決剩下的3L-CVRP問題.路徑部分采用禁忌搜索算法將多啟動隨機節(jié)約法產(chǎn)生的初始解逐步迭代到路線最少，同時樹搜索算法進行路徑的裝車結(jié)果檢查，以尋求可行路徑中裝車的箱子最大化.兩算法還通過緩存已測過路線來提高耦合性減少計算工作量.因為要裝車的箱子數(shù)量多，就以上一步GA產(chǎn)生的墻或塊組合方案代替單個箱子來加速樹搜索算法.

步驟3合并步驟1～2的解就得到最終解.

3 案例數(shù)據(jù)及結(jié)果分析

3.1 案例數(shù)據(jù)

入廠物流案例數(shù)據(jù)為某工廠市內(nèi)13個待取貨節(jié)點的82種不同的中小尺寸貨物(平均體積0.03 m3)，篇幅原因，表略.該批中小尺寸貨物具有典型的弱異性特征，總件數(shù)達23 220箱，每種貨物數(shù)量平均達284件.每節(jié)點待取貨物種類從1～15不等，平均為6.3種貨物.

案例車型為大型車a，貨廂內(nèi)部裝貨尺寸為，L=12 024 mm，W=2 350 mm，H=2 697 mm，容積76.3 m3；中型車b，L=8 600 mm，W=2 400 mm，H=2 400 mm，容積49.536 m3.

3.2 案例及計算結(jié)果

3.2.1托盤裝車方案結(jié)果

按托盤單元貨物堆碼凈高≤1 000 mm，每種貨物單獨托盤化.82種貨物按底面尺寸應(yīng)用MPLP求解單層裝碼數(shù)量，再確定堆碼層數(shù)，即得每種貨物在托盤上可裝碼數(shù)量.將節(jié)點內(nèi)各貨物所需托盤數(shù)匯總即得各節(jié)點所需的托盤數(shù)量，見表1.表1粗體字為“大節(jié)點”，如A2，A3，A6，A9.但82種貨物單獨每種的總體積均沒有超過任一車型的車輛容積，且總重小于車型載重量.

表1 I、T兩種不同托盤化后的各節(jié)點裝箱結(jié)果 托盤數(shù)

上述兩種托盤化結(jié)果，按a, b兩種車型的容量，對大節(jié)點直接減去滿載的直取車數(shù)，便得到四個常規(guī)CVRP方案算例.因為節(jié)點距離矩陣已知，這一問題可以用Lingo求得最優(yōu)解，結(jié)果見表2.

表2 4個CVRP算例的計算結(jié)果

*總托盤數(shù)與表1合計數(shù)據(jù)不同在于大節(jié)點的直取路線的托盤數(shù)量已減去.

上述總里程還要加上各條滿載直取路線的雙倍距離，便得各實例的總里程.

3.2.2一維堆碼裝車方案結(jié)果

這種方式采用的遺傳算法在Matlab環(huán)境下實現(xiàn)，運行于i3-4130/4G配置的64位計算機上.兩方案計算各運行了15次，得到了最好的計算結(jié)果見表3.

3.2.3三維優(yōu)化裝車方案結(jié)果

三維優(yōu)化裝車采用前述混合算法用C++在Intel 3.30GHz處理器的計算機上實現(xiàn)，不同車輛容量的二個方案結(jié)果見表3.

表3 1L-CVRP及3L-CVRP算例的計算結(jié)果

4 分析與決策

4.1 三種模型結(jié)果比較

三種模型的8個方案結(jié)果比較如表4所示，其中車輛數(shù)包括了整車直達的情況.

總體來說，托盤裝車方案的結(jié)果較后兩種方案差很多，主要是因為它二個層次的裝箱都沒有高的填充率.一維優(yōu)化與三維優(yōu)化的差別較小在于二者都是建墻，不過前者的等同箱子墻，后者是不同箱子的墻，因為算例數(shù)據(jù)為大量弱異性，且相對于車廂尺寸較小，故兩者墻相似度較高，最終結(jié)果接近.

表4 三種模型共8種情況的結(jié)果比較

可以看到，采用大型車a的三維優(yōu)化裝車方案的總里程最短，車輛數(shù)最少，平均車輛滿載率為77.8%.但是不管是哪種模型若采用小車型b，車輛數(shù)雖然多了，但裝車尺寸契合度更好，滿載率均有所提高.特別的是采用托盤化后，所需車輛數(shù)和總里程顯著增加，總體滿載率大幅降低.

4.2 入廠物流作業(yè)成本分析

雖然從上面結(jié)果來看，托盤裝車方案最差，但是入廠物流決策不只是車輛路徑和滿載率，各方案的物流裝卸作業(yè)的情況也需考慮，比較它們的優(yōu)劣最終要從整個物流系統(tǒng)來衡量，物流作業(yè)成本是最終的衡量因素(各物流系統(tǒng)配置已定，不計系統(tǒng)的配置成本).

首先各節(jié)點距離決定我們是城市配送，假設(shè)按配送每車公里成本λ與總里程Z的乘積得到成本C1；每多訪問一次節(jié)點(因為有需求拆分，訪問次數(shù)多于節(jié)點個數(shù))，增加固定成本C2，它只是減速停車的成本，不包括后面要考慮的可變裝貨成本，按各算例數(shù)的總里程和節(jié)點總訪問次數(shù)g可得到車輛路線距離和訪問方面的總成本.

其次就是裝卸車、碼箱的物流作業(yè)成本.因為裝車、碼箱是繁重的物流作業(yè)，這里測算出物流搬運時間，再折算成物流成本.取貨時每條線路訪問一個節(jié)點(停車成本已在前面C2中考慮)需要考慮裝貨時間T1，它包括按件(一箱或一托盤均算一件)的裝車作業(yè)時間T11，和箱型不同時的挑選和排隊的裝車準備時間T12；其中T11為取貨件數(shù)e與單件裝車時間t11的累計乘積，T12為單位準備時間t12與轉(zhuǎn)換次數(shù)f的乘積.最后還有到達工廠的卸車時間T2，不管是叉車作業(yè)還是人工作業(yè)都是按件來卸，單件卸車時間t2較單件裝車時間t11更低，因此考慮上述因素的物流搬運總時間T為

T=T1+T2=e·t11+f·t12+e·t2

(9)

T12是指在共同的揀貨作業(yè)完成之外，多箱型裝車時先要準備好不同箱型分區(qū)排隊順序后才能按件依次裝車.對于托盤裝車，每按一種貨物托盤時需要考慮一個t12，同貨物托盤因為按件裝箱時間已經(jīng)考慮了，就不再需要；一維優(yōu)化裝箱時，只在每墻(同一箱型組成)不同時考慮t12.但三維優(yōu)化裝箱最復(fù)雜，因為要考慮每個箱子的裝箱順序和位置，每兩個箱子之間都要考慮一次，但連續(xù)的同一種箱子只考慮一次t12.

設(shè)每小時平均物流搬運成本為μ，則最終有

C=C1+C2+C3=λZ+gc2+μT

(10)

根據(jù)物流實踐，取t11=0.2 min，t12=1 min，t2=0.133 min，c2=50元，λ=5元(a型)，4元(b型)，μ=20 元/h，則得到的成本比較結(jié)果見表5.

表5 三種模型共8種情況的物流作業(yè)成本結(jié)果比較

由表5可知，總成本最小的是第一個決策枝，即國際托盤I裝a型車；按單位車輛成本最小的是方案4，即日式托盤裝b型車.雖然三維優(yōu)化裝車方案在里程數(shù)和車輛空間利用率方面優(yōu)勢明顯，但平均每車千余件貨物的裝卸和基于三維優(yōu)化裝箱所必需的排序和準備成本高昂，也成為3L-CVRP在人工搬運甚至機器搬運下實現(xiàn)的最大障礙.綜合考慮了物流裝卸及排序準備成本之后，托盤單元化方案的物流作業(yè)總成本還是最低.在復(fù)雜多貨物裝卸搬運成本增加的情況下，托盤單元化的優(yōu)勢更加明顯.

5 結(jié) 束 語

本文針對大量弱異性貨物取貨的實際情況，考慮了三種不同的車輛路徑問題方案，分別進行了建模和求解.系統(tǒng)決策不僅是各運籌學模型總里程、車輛數(shù)和滿載率結(jié)果的比較，還有更切合實際物流作業(yè)的裝卸貨和準備轉(zhuǎn)換下的成本比較.對于總里程數(shù)和車輛空間利用率方面優(yōu)勢明顯的三維優(yōu)化裝車方案，大量貨物按三維優(yōu)化裝箱結(jié)果所必需的排序、準備和裝卸的成本高昂，需要的高效低成本的自動裝車技術(shù)一時還無法實現(xiàn).當然，研究還未涉及循環(huán)取貨式線路問題，且在成本模型中對手工搬運和叉車搬運一次作業(yè)時間等同看待存在一定誤差，方案還需要更多的數(shù)據(jù)來驗證.但這一基于多模型和物流作業(yè)成本的綜合優(yōu)化分析有助于多種不同約束條件下的車輛路徑問題的應(yīng)用決策.

參考文獻

[1] TOTH P, VIGO D. Vehicle routing: problems, methods, and applications [M]. 2nd ed. Philadelphia: Society for Industrial and Applied Mathematics, 2014.

[2] 王征,胡培祥,王旭坪.帶二維裝箱約束的物流配送車輛路徑問題[J].系統(tǒng)工程理論與實踐,2011,31(12):2328-2341

[3] GENDREAU M, IORI M, LAPORTE G. A tabu search algorithm for a routing and container loading problem[J]. Transportation Science, 2006,40(3):342-350.

[4] 王長瓊,戚小振.三維裝載約束下的汽車零部件循環(huán)取貨路徑優(yōu)化研究[J].武漢理工大學學報(交通科學與工程版),2015,39(6):1161-1165.

[5] IORI M, MARTELLO S. Routing problems with loading constraints [J]. Top, 2010,18(1):4-27.

[6] POLLARIS H, BRAEKERS K, CARIS A, et al. Vehicle routing problems with loading constraints: state-of-the-art and future directions [J]. OR Spectrum, 2015,37(2):297-330.

[7] DOERNER K, FUELLERER G, GRONALT M, et al. Metaheuristics for vehicle routing problems with loading constraints [J]. Networks, 2007,49:294-307.

[8] ZACHARIADIS E, TARANTILIS C, KIRANOUDIS C. The pallet-packing vehicle routing problem [J]. Transportation Sciences, 2012,46(3):341-358.

[9] ARCHETTI C, SPERANZA M G. Vehicle routing problems with split deliveries [J]. International Transactions in Operational Research, 2012,39:3-6.

[10] YI J M, SU Z X, QIU Y H. The vehicle routing problem with one-dimensional loading constraints [J]. International Journal of Industrial and Systems Engineering, 2017,27(3):412-426.

[11] 伊俊敏，蘇志雄.考慮循環(huán)取貨裝車堆碼的一種車輛路徑問題研究[J].武漢理工大學學報(交通科學與工程版),2017,41(2):179-184.

[12] YI J M, BORTFELDT A. The capacitated vehicle routing problem with three-dimensional loading constraints and split delivery-a case study [J]. Operations Research Proceedings, 2016(1):47-52.