伊俊敏 蘇志雄

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

考慮循環(huán)取貨裝車堆碼的一種車輛路徑問題研究*

伊俊敏 蘇志雄

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

研究了某制造企業(yè)循環(huán)取貨物流路徑優(yōu)化問題，根據(jù)弱異性小尺寸貨物裝車堆碼特點(diǎn)，在裝箱約束處理中通過“砌墻法”的有效簡化處理，得到車輛容積和裝車長度雙容量約束的新型車輛路徑問題模型，區(qū)別于已有帶裝箱約束的車輛路徑問題.將不同貨物作為單獨(dú)的節(jié)點(diǎn)來處理，解決了通常需要需求可拆分路徑問題才能解決的、節(jié)點(diǎn)需求量大于車輛容量的難題.運(yùn)用遺傳算法求解，松弛雙容量的難約束，對(duì)該問題實(shí)際數(shù)據(jù)算例求得最終路徑-裝車結(jié)果.從結(jié)果解析、“砌墻”誤差分析、相關(guān)問題比較和應(yīng)用條件等方面驗(yàn)證了問題模型物流應(yīng)用的可靠性和可行性.

車輛路徑問題；裝車堆碼；需求可拆分；遺傳算法；弱異性

0 引 言

循環(huán)取貨(milk-run)是汽車等制造企業(yè)應(yīng)用的一種先進(jìn)入廠物流模式，它是對(duì)不足整車運(yùn)輸?shù)亩嗉夜?yīng)商物料，按設(shè)計(jì)好的路線，采取多頻次、小批量的方式取貨，統(tǒng)一送到工廠生產(chǎn)現(xiàn)場的方式.通過對(duì)取貨順序、路線和頻次的總體安排來更好地控制入廠物流.循環(huán)取貨方式不僅降低了庫存，還加速了物流效率和線路合理性[1].

循環(huán)取貨優(yōu)化的關(guān)鍵是路線設(shè)計(jì)和車輛裝車，這離不開帶容量限制的車輛路徑問題(CVRP)[2].但常規(guī)的CVRP模型并未考慮裝車，優(yōu)化結(jié)果在實(shí)踐中卻裝不下[3].實(shí)際上，對(duì)這類需要拼裝貨物的配送問題，運(yùn)輸和裝箱是2個(gè)相互制約、不可分割的過程，不考慮裝箱，車輛優(yōu)化路線上的貨物卻無法全部裝上該車；忽視路徑問題，車廂裝得再滿成本也降不下來[4].因此，循環(huán)取貨物流的研究要綜合考慮路徑與車輛裝箱問題.

綜合考慮裝箱和路徑問題的最常見做法是將裝箱作為CVRP新的約束條件，來保證一條路線各節(jié)點(diǎn)的貨物能夠裝入車廂空間，并滿足不同客戶貨物的卸貨要求.當(dāng)然具有裝箱約束的車輛路徑復(fù)合問題總的還是路徑成本最小的NP-難問題，但裝箱約束本身也是NP-難問題，兩者的復(fù)合更加難以求解.根據(jù)裝箱約束的維數(shù)，目前的研究分為二維問題(2L-CVRP)和三維問題(3L-CVRP)[5-9]，提升了車輛路徑問題和裝箱問題在物流運(yùn)輸領(lǐng)域的實(shí)際應(yīng)用并指明了方向.

另一方面，循環(huán)取貨作業(yè)常有將外地供應(yīng)商的貨物先行集中到工廠附近取貨節(jié)點(diǎn)的操作，這些節(jié)點(diǎn)所需取貨量可能會(huì)超過車輛容量(稱為“大節(jié)點(diǎn)”)，已不滿足CVRP問題“節(jié)點(diǎn)惟一拜訪”的基本假設(shè)，需要考慮需求可拆分的車輛路徑問題(SDVRP)，允許該節(jié)點(diǎn)需求量被不同車輛分裝送貨.對(duì)于SDVRP問題，通過需求拆分可以形成更合理的路線來降低路徑問題的目標(biāo)總里程[10].SDVRP雖然降低了總里程成本，但是對(duì)同一客戶的多次訪問卻提高了交易及管理成本，總的物流成本可能難以降低.從管理角度看，如果不是特別需要，并不值得推薦.

文中針對(duì)某物流循環(huán)取貨問題展開研究，通過簡化的裝車堆碼近似算法，得到專門的路徑-裝箱復(fù)合問題及模型.對(duì)實(shí)例數(shù)據(jù)，通過擴(kuò)展節(jié)點(diǎn)的方法解決了“大節(jié)點(diǎn)”需求拆分的問題，運(yùn)用遺傳算法求解，并給出結(jié)果及應(yīng)用分析.

1 循環(huán)取貨裝車堆碼決策

針對(duì)汽車制造等行業(yè)生產(chǎn)需求的變化、眾多供應(yīng)商和各零部件重量與尺寸的差異，Milk-run決策先要根據(jù)既定取貨周期下各零部件需要的數(shù)量，來綜合解決合理數(shù)量下取貨車輛的路線和裝箱的復(fù)合要求.

由于汽車零部件貨物體積尺寸差別大，無法全部托盤單元化，尤其是小尺寸零部件裝車常是包裝貨物在貨車車廂內(nèi)堆碼的傳統(tǒng)方式.對(duì)于裝車堆碼，假設(shè)車型相同，即對(duì)任一車k(k=1,2,…,m)，載重量為Q，車廂內(nèi)尺寸長、寬、高分別為L,W,H.每種貨物包裝的長寬高分別為li,wi,hi，其中裝車時(shí)hi不能倒置.

就裝箱優(yōu)化來說，涉及到貨物裝車的三維容器裝箱問題，這類問題2種最基本的解法是砌墻法和分層法[11].對(duì)于本問題，弱異性小尺寸貨物，砌墻法更合適.

采用砌墻法可以近似算出每種貨物在車廂內(nèi)同方向堆碼的墻厚ti(包裝箱長或?qū)挼恼麛?shù)倍).這種近似算法設(shè)定每堵墻在車廂內(nèi)垂直于車輛L方向，且橫貫整個(gè)車廂寬度(見圖1)，不考慮不同墻在車廂寬度方向的拼接.這時(shí)墻厚的計(jì)算公式如下.

(1)

2 路徑與裝箱復(fù)合問題的建模

解決了裝車堆碼之后，系統(tǒng)優(yōu)化的關(guān)鍵問題是確定循環(huán)取貨路線安排和所需路線數(shù)量，以使總成本最小.這是CVRP類的路徑問題，首先是基本的模型假設(shè)[12]：

1) 每一車輛從倉庫出發(fā)并回到倉庫(回路問題)，中間每節(jié)點(diǎn)只拜訪一次.

2) 車輛到達(dá)一個(gè)節(jié)點(diǎn)后只取貨物，并且一次取完.

3) 所用車輛均相同，一條路線一輛車，每條路線所取貨物不超過車輛容量限制.

并采用以下記號(hào)：i為取貨節(jié)點(diǎn)，i=0,1,2,…,n，其中i=0表示倉庫;qi為每一取貨節(jié)點(diǎn)的取貨數(shù)量(以重量計(jì))，i=1,2,…,n;cij為節(jié)點(diǎn)i和j之間的距離，i,j=0,1,2,…,n.

圖1 不同貨物的砌墻法裝車示意圖(注：t為墻厚，A為節(jié)點(diǎn))

本問題的目標(biāo)是所有車輛總的行程距離最小，沿用三指數(shù)車輛流動(dòng)模型，設(shè)置0-1變量xijk，僅當(dāng)車輛k直接從節(jié)點(diǎn)i到節(jié)點(diǎn)j，值為1，否則為0.所有的節(jié)點(diǎn)構(gòu)成集合V，S為進(jìn)入某一路線的節(jié)點(diǎn)的集合，顯然S為V的子集，S不能為空且至少包含兩點(diǎn).

則問題模型如下.

(2)

(3)

(5)

(6)

(7)

(8)

(9)

其中：式(3)保證每1節(jié)點(diǎn)僅由1輛車拜訪1次；式(4)為節(jié)點(diǎn)流量守恒約束，每節(jié)點(diǎn)流入與流出的交通量相等；式(5)和(6)保證每臺(tái)車在各節(jié)點(diǎn)只被使用一次，m臺(tái)車輛均從倉庫出發(fā)并回到倉庫；式(7)為子回路消除約束，采用集合的形式表示；式(8)保證所取貨物不超過車輛的載重量；式(9)保證裝入車輛中的每種貨物的墻厚合計(jì)不超過車廂總長，這也是本問題的特殊之處，裝箱約束條件簡化為一維線性約束，它仍然屬于帶裝箱約束的CVRP問題.

需要注意的是，原始節(jié)點(diǎn)下的需求量數(shù)據(jù)有“大節(jié)點(diǎn)”，不滿足本問題模型的式(3)及基本假設(shè).但將每種貨物單獨(dú)當(dāng)成一個(gè)節(jié)點(diǎn)后，上述模型及假設(shè)仍然成立，詳細(xì)處理見下節(jié).

3 模型求解

本問題是NP-難問題，對(duì)于大規(guī)模問題主要采用亞啟發(fā)式算法，如禁忌搜索、模擬退火和遺傳算法等亞啟發(fā)式算法來求解.

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

考慮遺傳算法(GA)求解車輛路徑問題的優(yōu)勢在于它可以隨機(jī)地從1個(gè)可行解跳到另1個(gè)可行解，從而解除其他方法容易陷入局部最優(yōu)解的困擾[13].此外，GA計(jì)算速度快且易與其他算法相結(jié)合，適合較大規(guī)模的車輛路徑問題.

3.1.1 編碼和解碼

編碼問題是GA算法設(shè)計(jì)關(guān)系到算法效率和質(zhì)量的首要和關(guān)鍵問題，這里設(shè)計(jì)了一種整數(shù)編碼來表示可行的節(jié)點(diǎn)排序與車輛指派方案，同時(shí)避免了子回路現(xiàn)象.染色體由兩部分組成：第一部分為基于節(jié)點(diǎn)的編碼，用來確定節(jié)點(diǎn)的訪問先后順序(從左到右)；第二部分為基于車輛的編碼，用來選擇每個(gè)節(jié)點(diǎn)的訪問車輛.解碼是將染色體轉(zhuǎn)化為CVRP解的過程.

3.1.2 適應(yīng)度值計(jì)算

對(duì)原問題的式(8)～(9)進(jìn)行松弛，懲罰系數(shù)分別為較大的正整數(shù)M1,M2，進(jìn)而得到新的目標(biāo)函數(shù)(見式(10))，并確定該染色體的適應(yīng)度值(值越小越好).

(10)

3.1.3 初始種群生成

采用完全隨機(jī)的方法來構(gòu)造初始化種群：第一部分編碼為1,2,…,n的隨機(jī)排列，第二部分編碼中的每一基因取值為介于1～m之間的隨機(jī)整數(shù).

3.1.4 遺傳操作

1) 選擇操作 選擇的實(shí)質(zhì)是對(duì)種群中的染色體優(yōu)勝劣汰.文中采用隨機(jī)遍歷抽樣法(SUS)，根據(jù)染色體的期望值來實(shí)際分配染色體被復(fù)制的數(shù)目.

2) 交叉操作 這里交叉操作采用單親操作，對(duì)于基于節(jié)點(diǎn)編碼的基因串采用翻轉(zhuǎn)(Flip)算子，即將隨機(jī)選擇的兩點(diǎn)之間的序列進(jìn)行翻轉(zhuǎn)；對(duì)于基于車輛編碼的基因串也采用翻轉(zhuǎn)算子.

3) 變異操作 變異操作也采用單親操作，對(duì)于基于節(jié)點(diǎn)編碼的基因串采用兩點(diǎn)交換(Swap)算子；對(duì)于基于車輛編碼的基因串采用整數(shù)變異，即對(duì)每一基因以一定的概率用介于1～m之間的其余整數(shù)進(jìn)行替換.

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

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

循環(huán)取貨案例數(shù)據(jù)來源于某公司市內(nèi)13個(gè)待取貨節(jié)點(diǎn)的82種不同尺寸的小體積貨物(平均體積0.03 m3).每節(jié)點(diǎn)待取貨物種類從1～15不等(見表1)，平均為6.3種貨物.

案例分別采用2種車型得到2個(gè)不同的算例，對(duì)于算例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.

表1 各節(jié)點(diǎn)貨物類型分布

3.2.2 大節(jié)點(diǎn)及擴(kuò)展節(jié)點(diǎn)分拆

由表1最后一列可知，存在“大節(jié)點(diǎn)”，如A6，A2，A3.但這82種小體積貨物每種均沒有超過2種車型的車輛容積，且小于其載重量(滿足式(8))，因此采用砌墻法裝車，每種貨物均可單獨(dú)堆碼在一段車廂內(nèi).這樣，待裝車的82種貨物擴(kuò)展為82個(gè)不同的地址節(jié)點(diǎn).因?yàn)?3個(gè)原始節(jié)點(diǎn)間距離已知，且處于同1個(gè)原始節(jié)點(diǎn)內(nèi)的擴(kuò)展節(jié)點(diǎn)之間的兩兩距離為0，則82個(gè)擴(kuò)展節(jié)點(diǎn)間的兩兩距離也可得，即cij數(shù)據(jù).

3.2.3 最少路線數(shù)m的下界

按照式(8)和(9)可分別算得m的下界值，見表2最后4列，所求最優(yōu)車輛數(shù)不會(huì)低于這些值.2個(gè)算例的主要數(shù)據(jù)特征見表2.

表2 1L-CVRP問題算例主要數(shù)據(jù)特征

3.2.4 計(jì)算環(huán)境及結(jié)果

文中采用的遺傳算法在Matlab環(huán)境下實(shí)現(xiàn)，運(yùn)行于i3-4130/4G配置的64位計(jì)算機(jī)上.對(duì)于式(10)，設(shè)置M1=M2=1 000，交叉概率取0.85，變異概率0.05，種群規(guī)模設(shè)為120，進(jìn)化代數(shù)設(shè)為6 000代，最長運(yùn)行時(shí)間控制在600 s內(nèi).兩算例計(jì)算各運(yùn)行了15次，最好的計(jì)算結(jié)果分別見表3～表4.

表3 1L-CVRP問題遺傳算法求解最優(yōu)結(jié)果(算例a：V=76.3 m3,L=12 024 mm)

注：*原始節(jié)點(diǎn)代號(hào)后標(biāo)有星號(hào)的為采用分拆取貨的節(jié)點(diǎn)，加下劃線的為大節(jié)點(diǎn)，即需求量超過車輛容量，如A6.下表同.

4 分析與討論

4.1 計(jì)算結(jié)果分析

1) 結(jié)果解析 前面是將82種貨物當(dāng)成節(jié)點(diǎn)來計(jì)算的，各條路線最終還原成原取貨節(jié)點(diǎn)的情況見表3～4第三列所示.其中該列僅1個(gè)原始節(jié)點(diǎn)的實(shí)際上是直達(dá)路線，算例a有5條，均是發(fā)生在大節(jié)點(diǎn)(A2,A3,A6)上；算例b有12條，大節(jié)點(diǎn)A2,A3,A6均有直達(dá)路線，但A9無直達(dá)只是分拆取貨，還有A5,A12 2個(gè)未超過車輛容量限制的節(jié)點(diǎn)也采用直達(dá)送貨且無分拆取貨，因?yàn)椴煌渥映叽缃档土塑囕v利用率.

2個(gè)算例的主要不同在于車輛尺寸和容量，算例b的車輛更小，在要裝車貨物總量不變的情況下，所用車輛當(dāng)然更多，路線所訪問的節(jié)點(diǎn)數(shù)也趨小，采用直達(dá)路線的可能性也更高.

表4 1L-CVRP問題遺傳算法求解最優(yōu)結(jié)果(算例b：V=49.536 m3,L=8 600 mm)

2) 裝箱近似算法的誤差分析 在式(1)的計(jì)算中，向上取整時(shí)墻厚中的排數(shù)為整數(shù)，會(huì)有些墻的箱子沒裝滿一排而空著(參見圖1裝車側(cè)視圖上部的缺口).以算例a為例，研究找到這種最大的空排部分前5個(gè)分別是貨物7，33，13，60，1，它們墻厚空檔部分分別占各自ti的21.1%，21.1%，4.8%，22.1%，12.7%，相應(yīng)占L的2.17%，2.17%，1.88%，1.49%，1.69%，均不超過3%，而且在各自線路中這些誤差均沒有超過最小的ti/L百分比.再比較本文線路容積利用率77.55%的均值，可以確定裝箱近似算法的誤差都不足以影響裝箱和線路的最終結(jié)果.

4.2 與相關(guān)CVRP問題的不同

注意到表1中有大節(jié)點(diǎn)，必須分拆送貨.從表3～4中的分拆節(jié)點(diǎn)來看，算例a除3個(gè)大節(jié)點(diǎn)外，還有非大節(jié)點(diǎn)A9,A12被分拆；算例b除4個(gè)大節(jié)點(diǎn)外還有A11,A12被分拆.文中的大節(jié)點(diǎn)涉及到貨物尺寸及裝箱組合，并不能像對(duì)待單一體積數(shù)據(jù)那樣直接減去整車的量，如何拆分這些需求量實(shí)際上是1個(gè)新的組合問題.SDVRP有專門的算法，但是還沒有涉及到貨物尺寸及裝箱.在這里，同1節(jié)點(diǎn)內(nèi)的不同貨物被當(dāng)作虛擬節(jié)點(diǎn)處理，擴(kuò)展了節(jié)點(diǎn)規(guī)模n及相應(yīng)距離矩陣cij，從另一個(gè)角度解決了分拆送貨問題.當(dāng)然節(jié)點(diǎn)規(guī)模的增加使得這種處理會(huì)犧牲一定的計(jì)算時(shí)間，總的還是值得的.

與現(xiàn)行的3L-CVRP測試算例相比，本案例為小體積弱異類貨物，數(shù)量更多也更符合實(shí)際情況；當(dāng)然3L-CVRP測試算例中貨物常為強(qiáng)異類，數(shù)量常為一件，更要考慮精確裝箱，不能用這里的裝箱近似算法.

4.3 應(yīng)用可行性分析

作為從循環(huán)取貨案例中提出的特殊CVRP問題，除了砌墻法裝箱的誤差分析，其可行適用條件也需探討.本例將三維裝箱通過砌墻法簡化為不同于3L-CVRP的單維堆碼長度問題，更便于應(yīng)用.這里裝車堆碼處理的適用條件是小型弱異類貨物，即單個(gè)貨物箱子尺寸相對(duì)于車廂尺寸都比較小，且同種貨物數(shù)量較多，這樣才能“有磚砌墻”.如果是家電配送大體積且數(shù)量少的強(qiáng)異性貨物就難以采取這種方法，但本問題源于實(shí)際，有較好的應(yīng)用意義.

5 結(jié) 束 語

針對(duì)循環(huán)取貨優(yōu)化決策，結(jié)合具體案例的裝車堆碼要求，將車輛路徑問題與裝箱問題綜合考慮，符合當(dāng)前剛興起的3L-CVRP研究方向，克服了傳統(tǒng)兩類問題孤立研究難以實(shí)用化的不足.研究建立了包含容積和堆碼長度的雙約束的CVRP問題模型，并通過擴(kuò)展節(jié)點(diǎn)解決了“大節(jié)點(diǎn)”處理的難題.這一問題模型及求解方案符合特定實(shí)際情況，比3L-CVRP更簡潔實(shí)用.并進(jìn)行了結(jié)果分析與討論，驗(yàn)證了方案應(yīng)用的可靠性.

[1]汪金蓮,蔣祖華.汽車制造廠零部件入廠物流的循環(huán)取貨路徑規(guī)劃[J].上海交通大學(xué)學(xué)報(bào),2009,43(11):1703-1709.

[2]YI J M, ZHOU J, GAO X L, et al. Tactical planning and optimization of a milk run system of parts pickup for an engine manufacturer[J]. Journal of Southeast University: English Edition,2007,23(增刊1):99-104.

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

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

[5]GENDREAU M, IORI M, LAPORTE G, et al. A tabu search heuristic for the vehicle routing problem with two dimensional loading constraints[J]. Networks,2007,51(1):4-18.

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

[7]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.

[8]BORTFELDT A, HOMBERGER J. Packing first, routing second—a heuristic for the vehicle routing and loading problem[J]. Computers & Operations Research,2013,40(3):873-885.

[9]顏瑞,張群,胡睿.考慮三維裝箱約束的多車場車輛路徑問題[J].管理工程學(xué)報(bào),2016,30(1):108-116.

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

[11]黃文奇,何琨.求解長方體Packing問題的純粹擬人算法[J].中國科學(xué) F輯:信息科學(xué),2009,39(6):617-622.

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

[13]BAKER B M, AYECHEW M A. A genetic algorithm for the vehicle routing problem[J]. Computers & Operations Research,2003,30(5):787-800.

A Study on a Specific Vehicle Routing Problem Under the Cargo Loading and Stacking by Milk-run Operations

YI Junmin SU Zhixiong

(SchoolofEconomicsandManagement,XiamenUniversityofTechnology,Xiamen361024,China)

A special vehicle routing problem with easy-to-implement loading scheme for route optimizing of a manufacturer’s milk-run operations is proposed with focus on the loading and stacking of weak-heterogeneous small-sized cargos. A new model is formulated with dual capacity constraints on both volume and loading length by applying a wall-building method for cargo stacking inside the vehicle. It is a new variant of the Capacitated Vehicle Routing Problem with Loading Constraints. Besides, the node set is extended temporarily by treating each cargo as a different node, thus an affordable increase in solving time by the node extension is traded with way out the difficulty of node demand surplus vehicle capacity, rather by the method of Split Delivery Vehicle Routing Problem. With slack of the dual-capacity constraints, the fitness value is evaluated using the genetic algorithm, and comprehensive routing and loading results for two instances from real data are achieved. The results are examined with discussions on result analysis, error study of wall-building approximation, model comparison, application conditions, which suggest a sound reliability and feasibility of the model’s application in logistics practice.

vehicle routing problem; loading and stacking; split delivery; genetic algorithm; weak heterogeneity

2016-02-20

*國家自然科學(xué)基金項(xiàng)目(71371162)、福建省自然科學(xué)基金項(xiàng)目 (2014J01271)資助

U492.3

10.3963/j.issn.2095-3844.2017.02.001

伊俊敏(1969—)：男，博士，教授，主要研究領(lǐng)域?yàn)槲锪飨到y(tǒng)工程、物流運(yùn)籌與管理