基于三維裝載場景的車輛路徑優(yōu)化算法研究與實(shí)踐①

陳永強(qiáng), 周躍進(jìn), 黃莎杉

(1.蕪湖職業(yè)技術(shù)學(xué)院智能制造學(xué)院,安徽 蕪湖 241006;2.南京大學(xué)工程管理學(xué)院,江蘇 南京 210093)

0 引 言

典型的車輛路徑問題(Vehicle Routing Problem, VRP)包含因素有:車場點(diǎn)、顧客點(diǎn)、車輛、約束條件、道路網(wǎng)絡(luò)以及運(yùn)作目標(biāo)。三維裝載問題(Three-dimensional Bin Packing Problem,3D-BPP)是車輛裝載問題(Vehicle Filled Problem, VFP)的一個(gè)重要分支。車輛裝載問題主要包含因素有:裝載容器、裝載貨物、約束條件、裝載策略以及運(yùn)作目標(biāo)[1]。學(xué)者在面臨路徑與裝載聯(lián)合優(yōu)化時(shí),多采用降維的方式,車輛裝載以空間利用率的形式加入目標(biāo)函數(shù),降低算法難度,且模型的構(gòu)建只針對單一的案例進(jìn)行,與實(shí)際存在一定的差距,因而3D-BPP仍具有很大的改善空間和研究價(jià)值[2]。

1 車輛路徑問題(VRP)數(shù)學(xué)模型

VRP數(shù)學(xué)模型可描述為:存在N個(gè)客戶點(diǎn),第i個(gè)客戶點(diǎn)的貨物需求總質(zhì)量是qi(i=1,2,…,N),需求總體積是si,各個(gè)客戶點(diǎn)需回收貨物總質(zhì)量是pi(i=1,2,…,N),回收貨物總體積是ssi,求在滿足以上提到的約束條件下的總運(yùn)輸成本最小。總運(yùn)輸成本包括與使用配送車輛數(shù)量成正比的固定成本和車輛行駛距離帶來的變動成本。該文基于物流配送優(yōu)化問題,在配送過程中考慮車輛最遠(yuǎn)距離、車輛裝載問題、客戶服務(wù)水平提升、損缺貨退回等實(shí)際問題,構(gòu)建較前人更為豐富、更為綜合、解釋性更強(qiáng)的數(shù)學(xué)模型。其數(shù)學(xué)模型表達(dá)如下:

1)固定成本。該成本包括:司機(jī)雇傭成本、搬運(yùn)工雇傭成本、車輛折舊費(fèi)用、車輛輪胎損耗、車輛日均維護(hù)費(fèi)用等。為了使模型解釋性更強(qiáng),加入成本系數(shù),見公式(1)。

α1·fk·M

(1)

2)總變動成本。車輛總變動成本主要與車輛行駛距離呈正相關(guān)關(guān)系。研究發(fā)現(xiàn)路況不同對配送車輛的速度、損耗、運(yùn)行時(shí)間等會有一定影響,需要在配送基礎(chǔ)模型上考慮不同行駛路徑產(chǎn)生的不同變動成本,用系數(shù)βij表示路況對車輛的影響。配送點(diǎn)之間一般的路況系數(shù)定為1,其他路徑如果路況較之更好,則βij小于1,反之βij大于1,見式(2)。

(2)

3)時(shí)間窗約束。完成i客戶的配送任務(wù)(裝貨或者取貨)的時(shí)間為hi,任務(wù)開始的時(shí)間在客戶時(shí)間窗[ei,li]內(nèi),其中ei是允許任務(wù)服務(wù)最早的開始時(shí)間,li是允許任務(wù)服務(wù)最遲的開始時(shí)間。構(gòu)建軟時(shí)間窗懲罰成本進(jìn)行時(shí)間窗約束,見式(3),其中α3,α4作為懲罰函數(shù)系數(shù),需要根據(jù)公司對配送服務(wù)水平的重視程度進(jìn)行設(shè)定,當(dāng)設(shè)定成無窮大或者較大的整數(shù)的時(shí),則函數(shù)表示硬時(shí)間窗約束。

α3·max{0,ei-ATki}+α4·max{0,ATki-li}

(3)

4)優(yōu)化目標(biāo)。以車輛配送過程中固定成本、變動成本、違反時(shí)間窗懲罰成本的和作為目標(biāo)函數(shù),并且用4個(gè)調(diào)節(jié)系數(shù)進(jìn)行函數(shù)適應(yīng)性調(diào)節(jié)。取α1,α2為整數(shù),并且α1?α2,其優(yōu)化第一目標(biāo)為最小化車輛使用數(shù)量,第二目標(biāo)為最小化總行駛距離。α3α3,α4則作為時(shí)間窗重要程度的調(diào)節(jié)參數(shù)。

綜上,車輛路徑問題的數(shù)學(xué)模型如下:

dij·Xijk+α3·max{0,ei-ATki}+

α4·max{0,ATki-li}

(4)

需要特別指出的是,公式(4)在具體數(shù)學(xué)模型求解過程中,需要考慮決策的變量、額定載重、限定距離、時(shí)間參數(shù)等約束條件。

2 車輛三維裝載(VFP)數(shù)學(xué)模型

VFP數(shù)學(xué)模型可描述為:有m種編號為i(i∈M={1,2,3,…,m})的貨物需要裝入一個(gè)長寬高分別為L,W,H的容器中,已知每種貨物的數(shù)量為bi,每種貨物的長寬高分別為li,wi,hi,從容器的左前下角開始放置,要求在裝載過程中需要滿足貨物不重疊、貨物后進(jìn)先出、保護(hù)好易碎貨物以及貨物需要擺放穩(wěn)定等約束條件,最終求得容器中最多能夠放置多少種和多少個(gè)貨物。

裝載模型構(gòu)建主要考慮了裝載過程中三維空間不可重疊、垂直方向穩(wěn)定性和易碎性堆放的數(shù)學(xué)表達(dá)式[3],并且根據(jù)實(shí)際裝載過程進(jìn)行約束設(shè)置。其數(shù)學(xué)模型表達(dá)如下:

圖2 不可重疊約束不等式關(guān)系

1)使用笛卡爾坐標(biāo)系(x,y,z)來定位貨物在運(yùn)輸車輛容器內(nèi)的位置。坐標(biāo)原點(diǎn)取車箱左邊底部前邊的頂點(diǎn),如圖1所示,在建立模型約束范圍時(shí)盡可能準(zhǔn)確以減少算法的搜索范圍。

則得出(x,y,z)與(x′,y′,z′)取值范圍:

2)三維空間不可重疊約束。設(shè)置坐標(biāo)(x′,y′,z′)作為選定裝載位置(x,y,z)的貨品所占據(jù)的空間點(diǎn),如圖1所示。進(jìn)一步分析,如圖2以x坐標(biāo)軸為例,得出x′與x的不等式關(guān)系式,并且給出了空間不重疊的約束關(guān)系式。

如圖可得關(guān)系式:

空間不重疊約束為:

x′∈X,y′∈Y,z′∈Z

(5)

3)垂直方向穩(wěn)定性約束。引入一個(gè)穩(wěn)定系數(shù)αj的概念,即垂直放置在上層的貨物與放置在其下層的貨物之間接觸面積比必須大于該穩(wěn)定系數(shù),否則判定不符合條件。因?yàn)樨浳锬J(rèn)是垂直放置,所以z軸的坐標(biāo)存在關(guān)系z=z″-hi,二維俯視圖如圖3、圖4。在實(shí)際裝載過程中,基本上不會出現(xiàn)上大下小或者貨物偏放的問題,所以會設(shè)置穩(wěn)定系數(shù)αj=1,但此處為了使模型的解釋性更強(qiáng),考慮多種情況出現(xiàn)的可能。

上層貨物的穩(wěn)定性最低限制的表達(dá)式為:

αj·lj·wj·ajx″y″z″

(6)

兩個(gè)貨物接觸面積存在兩種情況(以橫坐標(biāo)為例),如圖所示:

圖3 x″≥x 圖4 x″

同理可得:

y-wj

整理可得:

Lij=min(li,lj)-|x″-x|

(7)

Wij=min(wi,wj)-|x″-x|

(8)

(9)

穩(wěn)定性約束為:

αj·lj·wj·ajx″y″z″

i,j∈M,x″∈Xj,y″∈Yj,z″∈Zj

(10)

4)易碎性堆放約束。引入一個(gè)易碎性系數(shù)βi的概念,即表示每個(gè)貨物所能夠承受的最大的壓強(qiáng),并且通過公式“壓強(qiáng) = 重力(qi)/ 接觸面積”表示。在討論該約束時(shí),需要多加入一個(gè)前提條件:穩(wěn)定系數(shù)αj=1,因此才能直接使用貨物的底面積作為兩個(gè)貨物的“接觸面積”。

上層貨物施加總壓強(qiáng)表達(dá)式:

(11)

貨物承受壓強(qiáng)最大限制的表達(dá)式為:

βi·aixyz

(12)

易碎性約束為:

x″∈Xj,y″∈Yj,z″∈Zj

(13)

綜上,問題的數(shù)學(xué)模型如下:

(14)

公式(14)在具體數(shù)學(xué)模型求解過程中還需考慮貨物j最多裝載數(shù)量約束;貨物空間不可重疊約束、穩(wěn)定性約束和易碎性約束。

3 綜合算法設(shè)計(jì)及優(yōu)化

VRP與VFP進(jìn)行聯(lián)合優(yōu)化時(shí)所涉及的兩個(gè)子問題的對象、類型及方向的不一樣,不能簡單進(jìn)行整合優(yōu)化,主要存在三種優(yōu)化方案:以VFP為主,VRP為輔、以VRP為主,VFP為輔、VFP與VRP同時(shí)進(jìn)行優(yōu)化?？紤]到VFP只是作為裝載的可行性判定,將VFP模型作為VRP的一個(gè)約束條件,采用先進(jìn)行VRP優(yōu)化再進(jìn)行VFP優(yōu)化的策略,具體優(yōu)化思路如圖5。

圖5 聯(lián)合優(yōu)化VRP &VFP流程圖

依據(jù)“以VRP為主,VFP為輔”的解決思路,求解的目標(biāo)是在總成本最低的情況下,保證同一路線上的貨物能被裝載到同一部車輛上并且能夠合理地卸下。因而可以將綜合模型求解拆分為兩個(gè)NP問題的求解:考慮車輛多種約束的車輛路徑優(yōu)化與車輛三維空間裝載優(yōu)化。因?yàn)檫x擇先進(jìn)行VRP優(yōu)化再進(jìn)行VFP優(yōu)化邏輯,所以不需要太復(fù)雜的裝載優(yōu)化算法,只需要找到一個(gè)滿足裝載約束條件下合理的裝載方案即可。因此,三維裝載部分參照六種啟發(fā)式算法,根據(jù)前文構(gòu)建裝載模型的方式調(diào)整這六種啟發(fā)式算法,用Hi(i=1,2,3,4,5,6)分別表示,并按照算法難易程度逐次進(jìn)行使用和判別,直至獲得一個(gè)可行的裝載方案。具體裝卸策略算法流程如圖6。

圖6 啟發(fā)式裝卸策略應(yīng)用流程

4 案例驗(yàn)證

以某公司城南配送中心為例,隨機(jī)選取該配送中心某一天配送計(jì)劃進(jìn)行分析,并利用本文建立的優(yōu)化模型和設(shè)計(jì)的算法進(jìn)行驗(yàn)證,該中心調(diào)度員主要以區(qū)域進(jìn)行訂單劃分,根據(jù)每個(gè)區(qū)域的當(dāng)天客戶需求總量安排車輛配送,該天41個(gè)客戶點(diǎn)可以大致分為五個(gè)區(qū)域。案例計(jì)算分為兩個(gè)組,每組運(yùn)行計(jì)算10次,最終取10次中最優(yōu)解,由于路況系數(shù)數(shù)學(xué)形式僅是體現(xiàn)在距離矩陣的變化上,因此主要分析比較不考慮路況系數(shù)的優(yōu)化結(jié)果,見表1。

表1 不考慮路況系數(shù)最優(yōu)配送路線分析

該配送中心2020年自營車輛配送成本為245.79元/噸,第三方物流配送平均成本為131.00元/噸,總平均成本為137.3元/噸。經(jīng)過優(yōu)化計(jì)算,車數(shù)由7輛減少到6輛,縮短了17.83%的配送距離,平均裝載率由80.97%上升至94.46%,總成本1076元,平均成本119.34元/噸,與近似現(xiàn)行配送方案相比降低了14.5%,與2014年第三方配送成本131.00元/噸相比亦降低了8.9%。以2014年數(shù)據(jù)作為參考,某公司全省配送費(fèi)用6595.21萬元,以降低8%配送成本保守計(jì)算,能為該公司節(jié)約至少527.6萬配送成本,提升了物流公司的綜合競爭力。

5 結(jié) 論

基于對典型車輛路徑優(yōu)化策略和三維裝載策略等問題的總結(jié),建立了車輛路徑問題(VRP)數(shù)學(xué)模型和車輛三維裝載(VFP)數(shù)學(xué)模型,通過聯(lián)合優(yōu)化算法進(jìn)行模型的優(yōu)化求解,以實(shí)際生產(chǎn)案例進(jìn)行可行性驗(yàn)證,得出以下結(jié)論:

(1)車輛路徑問題(VRP)數(shù)學(xué)模型和車輛三維裝載(VFP)數(shù)學(xué)模型的求解需要諸多約束條件。如VFP數(shù)學(xué)模型求解時(shí),添加了貨物承受壓約束、易碎性約束、空間不可重疊約束、穩(wěn)定性約束等,否則方程求解結(jié)果無法有效收斂。

(2)提出了以“以VRP為主,VFP為輔”的及優(yōu)化方案,并進(jìn)行優(yōu)化流程設(shè)計(jì)、裝卸策略算法流程設(shè)計(jì),以偽程序設(shè)計(jì)為基礎(chǔ),驗(yàn)證了“VRP&VFP”聯(lián)合優(yōu)化算法具備有效迭代和結(jié)果收斂的性質(zhì)。

(3)以某實(shí)際配送中心數(shù)據(jù)為例進(jìn)行計(jì)算和對比分析,車數(shù)由7輛減少到6輛,且縮短了17.83%的配送距離,平均裝載率由80.97%上升至94.46%,運(yùn)輸成本與近似現(xiàn)行配送方案相比降低了14.5%,驗(yàn)證了模型和算法的正確性和有效性,具備生產(chǎn)實(shí)踐價(jià)值。