三維裝載約束下基于運(yùn)輸資源共享的車輛路徑問題

王 勇,魏遠(yuǎn)晗,蔣 瓊,許茂增

(重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院,重慶 400074)

0 引言

隨著城市物流市場需求規(guī)模的不斷增長和有限的物流配送設(shè)施間矛盾的日益凸顯,城市物流配送在資源協(xié)同性和時(shí)間緊迫性上提出了更高的要求,而隨著共享運(yùn)輸經(jīng)濟(jì)、互用配送模式和共享配送聯(lián)盟等新興物流運(yùn)營模式的興起,城市物流運(yùn)輸行業(yè)在整合物流基礎(chǔ)設(shè)施資源和提高配送車輛使用率方面進(jìn)行了有益的探索和應(yīng)用[1-2]。研究三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題,有助于完善三維裝箱調(diào)度理論體系構(gòu)建以及提高物流資源的集約化利用和促進(jìn)城市物流系統(tǒng)的綠色可持續(xù)發(fā)展。國內(nèi)外學(xué)者在三維裝載約束下的車輛路徑問題相關(guān)研究主要集中在三維裝箱問題和基于運(yùn)輸資源共享的車輛調(diào)度問題兩個(gè)方面。

在三維裝箱問題研究方面,鄭煒等[3]研究了考慮貨物在車廂中不同擺放狀態(tài)的三維裝箱問題,并設(shè)計(jì)了一種基于車廂空間分割的啟發(fā)式算法用于求解問題。吳蓓等[4]為了滿足客戶不同規(guī)格的貨物需求,建立了多箱型的三維配載模型并設(shè)計(jì)了混合啟發(fā)式算法用于模型求解,有效提高了貨箱的空間利用率和配送效率。BORTFELDT等[5]在考慮了三維裝箱中的貨物重量限制、支撐約束以及卸載順序等約束,建立了三維裝載約束下的車輛路徑優(yōu)化模型,并設(shè)計(jì)了混合啟發(fā)式算法求解模型。靳志宏等[6]從三維裝載約束的實(shí)際出發(fā),考慮了配送車輛的載重約束以及車廂的三維尺寸大小等約束,建立了貨物裝載與車輛配送路徑組合優(yōu)化的數(shù)學(xué)模型,并設(shè)計(jì)了基于CW(Clarke-Wright)節(jié)約算法和蟻群算法的交互式混合算法求解模型。FENG等[7]在三維裝箱問題中考慮了貨箱空間劃分策略,建立了以貨箱數(shù)最少為目標(biāo)的三維裝箱模型,并設(shè)計(jì)了一種新的混合遺傳算法用于模型求解。LI等[8]為了最大化利用車廂空間,研究了貨物不同擺放方位的三維裝箱問題,構(gòu)建了以車廂空載體積最小化為目標(biāo)的三維裝載模型,并設(shè)計(jì)了一種差分進(jìn)化算法進(jìn)行模型求解。由上述文獻(xiàn)可知,當(dāng)前關(guān)于三維裝箱問題的研究主要集中在考慮相關(guān)裝載約束的模型構(gòu)建和算法設(shè)計(jì)方面,且混合啟發(fā)式算法常被用于研究三維裝箱問題,而三維裝箱問題為三維裝載約束下基于運(yùn)輸資源共享的車輛路徑問題研究提供了研究方法切入。

在基于資源共享的車輛調(diào)度問題研究方面,王萬良等[9]為了解決配送中心車輛不能即時(shí)滿足客戶配送需求的問題,引入車輛共享機(jī)制,使得配送中心通過車輛租賃的方式實(shí)現(xiàn)了車輛資源的共享,進(jìn)而實(shí)現(xiàn)了物流資源的合理化配置。劉家利等[10]針對企業(yè)自身運(yùn)力有限的情況,提出一種基于車輛租賃的運(yùn)輸資源共享策略,構(gòu)建了以配送成本最小化為目標(biāo)的混合整數(shù)規(guī)劃模型,設(shè)計(jì)了基于CW節(jié)約算法的混合遺傳算法用于模型求解。ZHANG等[11]針對物流配送網(wǎng)絡(luò)中的協(xié)同運(yùn)輸問題,提出一種基于共享運(yùn)輸資源和客戶信息的物流網(wǎng)絡(luò)協(xié)同優(yōu)化機(jī)制,進(jìn)而降低了運(yùn)輸成本和提高了物流資源利用率。LI等[12]為節(jié)約運(yùn)輸資源和提高配送效率,提出通過共享倉庫資源實(shí)現(xiàn)物流網(wǎng)絡(luò)的合理化資源配置,進(jìn)而降低了運(yùn)輸距離和減少了車輛使用數(shù)。DENG等[13]提出一種基于物流設(shè)施服務(wù)能力、運(yùn)輸車輛和客戶信息共享的集成優(yōu)化策略,并證明該策略可以有效降低物流網(wǎng)絡(luò)運(yùn)營的總成本和車輛使用數(shù),從而實(shí)現(xiàn)物流資源的合理化配置。由上述研究可知,物流企業(yè)可以通過車輛租賃、增加車輛使用頻次、共享客戶信息以及共享倉庫資源等方式實(shí)現(xiàn)物流資源的共享,進(jìn)而降低物流運(yùn)營總成本和節(jié)約運(yùn)輸資源,這為車輛調(diào)度問題研究中資源共享模式的選擇和優(yōu)化方法的提出提供了理論參考和決策支持。

在三維裝箱與運(yùn)輸資源調(diào)度組合優(yōu)化的問題研究方面,GUENTHER等[14]研究了三維裝箱和車輛調(diào)度的組合優(yōu)化問題,建立了以最小運(yùn)輸成本為優(yōu)化目標(biāo)的數(shù)學(xué)模型,并設(shè)計(jì)了基于CW節(jié)約算法的蟻群優(yōu)化算法用于模型求解。章勛宏等[15]為有效降低運(yùn)輸車輛的使用數(shù)和提高運(yùn)輸資源利用率,將三維裝箱問題與車輛循環(huán)取貨調(diào)度優(yōu)化問題相結(jié)合,建立了多目標(biāo)優(yōu)化模型和設(shè)計(jì)了用于模型求解的啟發(fā)式算法。王超等[16]研究了三維裝箱問題與車輛調(diào)度問題的多目標(biāo)組合優(yōu)化問題,建立了運(yùn)輸車輛最小化和配送距離最小化的雙目標(biāo)優(yōu)化模型,并設(shè)計(jì)了兩階段混合算法進(jìn)行模型求解。BORTFELDT等[17]構(gòu)建了混合整數(shù)規(guī)劃模型用于研究運(yùn)輸車輛調(diào)度和三維裝箱約束的組合優(yōu)化問題,并提出一種基于遺傳算法的混合啟發(fā)式算法求解模型。吳倩云等[18]研究了裝配車間物料配送的集成調(diào)度問題,構(gòu)建了三維裝載與車輛運(yùn)輸調(diào)度相結(jié)合的組合優(yōu)化模型,并設(shè)計(jì)了遺傳算法進(jìn)行模型求解,進(jìn)而提高了車輛的裝載能力并節(jié)約了運(yùn)輸資源。由上述文獻(xiàn)可知,關(guān)于三維裝箱與運(yùn)輸資源調(diào)度問題的組合優(yōu)化方面取得了一定的研究進(jìn)展,但將三維裝載約束的車廂空間區(qū)域劃分模式與運(yùn)輸資源共享調(diào)度相結(jié)合問題的研究方面還有待進(jìn)一步拓展。

本文考慮了三維裝載約束的車輛空間區(qū)域劃分模式,研究了三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題。首先,結(jié)合客戶的多個(gè)服務(wù)時(shí)間窗需求特征,確定客戶的多個(gè)服務(wù)時(shí)間周期,并根據(jù)客戶不同規(guī)格的貨物需求,選擇合理的配送車輛車廂空間區(qū)域劃分模式;然后,構(gòu)建了包含配送中心固定成本、配送車輛運(yùn)輸成本、維修成本、租賃成本和違反時(shí)間窗懲罰成本的物流運(yùn)營總成本最小化和車輛使用數(shù)最小化的雙目標(biāo)優(yōu)化模型;其次,設(shè)計(jì)了一種基于k-means時(shí)空聚類算法的Clarke-Wright—非支配排序遺傳算法(Clarke-Wright—fast elitist Non-dominated Sorting Genetic Algorithm,CW-NSGA-II)求解模型,該算法引入CW節(jié)約算法以提高初始解的質(zhì)量,并結(jié)合NSGA-II算法提高了混合算法尋找優(yōu)化解的全局和局部空間搜索能力;最后,通過實(shí)例分析探討了三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化前后,以及不同車廂空間區(qū)域劃分模式下的物流運(yùn)營總成本、車輛使用數(shù)、平均裝載率和車輛平均使用頻次的變化情況,進(jìn)而為城市三維裝載約束下的物流配送問題提供新的研究思路。

1 問題描述

三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題需要考慮車輛的三維裝載約束、客戶需求貨物類型和客戶服務(wù)需求時(shí)間窗等條件進(jìn)行運(yùn)輸資源共享調(diào)度和車輛路徑優(yōu)化的一類問題。在三維裝載物流配送過程中,由于客戶的需求貨物類型存在差異,且存在多個(gè)服務(wù)需求時(shí)間窗長短不一的現(xiàn)象,導(dǎo)致當(dāng)前的配送模式存在車輛裝載率低、車輛使用數(shù)過多和物流運(yùn)營總成本較高等問題。為了提高車輛裝載率,增加車輛使用頻次和降低物流運(yùn)營總成本,需要有效整合物流資源進(jìn)行合理的貨物裝載和配送調(diào)度,進(jìn)而結(jié)合三維裝載約束、車輛載重和客戶訪問時(shí)間窗等約束條件構(gòu)建物流運(yùn)營成本最小和車輛使用數(shù)最小的雙目標(biāo)優(yōu)化模型,研究三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題。為了更清楚地說明三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題,本研究結(jié)合調(diào)研數(shù)據(jù)繪制了一類基于運(yùn)輸資源共享的三維裝載物流配送優(yōu)化方案前后對比圖,如圖1所示。

圖1 基于運(yùn)輸資源共享的三維裝載物流配送優(yōu)化前后對比

圖1a表示基于運(yùn)輸資源共享的三維裝載車輛路徑優(yōu)化前,配送中心服務(wù)客戶配送線路的各服務(wù)時(shí)間窗存在時(shí)間交錯(cuò)和重疊等現(xiàn)象,且存在交錯(cuò)運(yùn)輸和較多違反服務(wù)時(shí)間窗的客戶點(diǎn),進(jìn)而導(dǎo)致配送車輛使用數(shù)較多和物流運(yùn)營成本較高等現(xiàn)象。圖1b表示基于運(yùn)輸資源共享的三維裝載車輛路徑優(yōu)化后,具有相近服務(wù)時(shí)間窗的客戶在一個(gè)聚類單元內(nèi)接受配送服務(wù),結(jié)合客戶不同規(guī)格的貨物需求進(jìn)行車廂分區(qū)和貨物裝載方式優(yōu)化,進(jìn)而提高了車輛使用頻次,且消除了違反時(shí)間窗的懲罰成本。假設(shè)單位時(shí)間的配送成本為40元,違反時(shí)間窗的單位時(shí)間懲罰成本是15元,車輛的租賃費(fèi)用為100元/輛?；诩僭O(shè)數(shù)值并結(jié)合考慮運(yùn)輸資源共享的三維裝載車輛路徑優(yōu)化前后路段通行時(shí)間、違反時(shí)間窗時(shí)間和車輛使用數(shù),計(jì)算得到基于運(yùn)輸資源共享的三維裝載車輛路徑優(yōu)化前后配送時(shí)間、車輛數(shù)量和運(yùn)營成本等指標(biāo)的比較結(jié)果,如表1所示。結(jié)果表明基于運(yùn)輸資源共享的三維裝載車輛路徑優(yōu)化后有效降低了物流運(yùn)營總成本,減少了共享車輛使用數(shù)和配送線路數(shù),消除了違反時(shí)間窗的客戶點(diǎn),降低了車輛配送時(shí)間和配送成本,增加了車輛平均使用頻次。

表1 基于運(yùn)輸資源共享的三維裝載車輛路徑優(yōu)化前后對比

2 模型建立

2.1 符號定義

本文研究涉及到的一些變量和符號定義如表2所示。

表2 變量定義

2.2 模型構(gòu)建

本文以配送中心的物流運(yùn)營成本Z1最小化和配送車輛使用數(shù)Z2最小化為優(yōu)化目標(biāo),建立了具有普適性的三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化模型。

(1)

(2)

約束條件：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

其中：式(3)表示服務(wù)周期t內(nèi)每個(gè)客戶點(diǎn)僅接受一輛配送車輛服務(wù);式(4)表示每個(gè)客戶在服務(wù)周期t內(nèi)僅接受一條配送線路服務(wù);式(5)表示配送車輛將貨物送達(dá)客戶后必須離開;式(6)表示消除子回路約束;式(7)表示服務(wù)周期t內(nèi)配送車輛v的使用次數(shù)等于其配送線路數(shù)之和;式(8)表示在服務(wù)周期t內(nèi)配送車輛v上各區(qū)域內(nèi)貨物數(shù)量的約束;式(9)表示在服務(wù)周期t內(nèi)配送車輛v上裝載貨物的總重量不超過配送車輛的最大裝載量;式(10)和式(11)表示配送車輛到達(dá)客戶點(diǎn)的時(shí)間,式(12)和式(13)表示配送車輛離開和到達(dá)配送中心的時(shí)間必須在其服務(wù)時(shí)間窗內(nèi);式(14)～式(16)表示貨物必須擺放在車廂內(nèi);式(17)～式(19)表示配送車輛任何區(qū)域內(nèi)裝載貨物長寬高的加和不能超出區(qū)域長寬高的限制;式(20)表示后服務(wù)客戶的貨物不能壓在先服務(wù)客戶貨物的上面;式(21)表示后服務(wù)客戶的貨物不能擋在先服務(wù)客戶貨物的前方;式(22)～式(25)表示變量約束。

3 CW-NSGA-II混合算法

3.1 算法過程描述

本文設(shè)計(jì)了基于k-means時(shí)空聚類的CW-NSGA-II混合算法求解三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化模型。首先,結(jié)合客戶的服務(wù)時(shí)間窗,利用k-means時(shí)空聚類算法[19]確定客戶的多個(gè)服務(wù)周期,在相應(yīng)服務(wù)周期內(nèi),選取k個(gè)聚類中心,計(jì)算每個(gè)客戶點(diǎn)到聚類中心的時(shí)空距離,并將客戶點(diǎn)指派到最臨近的聚類中心;然后,結(jié)合帕累托優(yōu)化原理設(shè)計(jì)適應(yīng)度函數(shù)并計(jì)算適應(yīng)度函數(shù)值[20-21],并應(yīng)用CW節(jié)約算法[22]生成初始的配送方案;最后,應(yīng)用NSGA-II算法[23]進(jìn)行配送方案優(yōu)化和非支配排序優(yōu)化,進(jìn)而生成配送路徑和三維裝載方案。CW節(jié)約算法和NSGA-II算法的集成旨在利用CW節(jié)約算法獲得質(zhì)量較好的次優(yōu)解,進(jìn)而提高混合算法尋找優(yōu)化解的全局和局部空間搜索能力,從而更有效地收斂到最優(yōu)解。在混合算法設(shè)計(jì)過程中集成了聚類算法和智能算法間的選擇性賦予機(jī)制,進(jìn)一步提高了算法的尋優(yōu)能力?；趉-means時(shí)空聚類的CW-NSGA-II混合算法的流程圖如圖2所示,具體算法步驟如表3所示。

表3 基于k-means時(shí)空聚類的CW-NSGA-II混合算法步驟

圖2 混合算法流程圖

3.2 基于k-means的時(shí)空聚類

客戶聚類是獲得更好的物流網(wǎng)絡(luò)配置和確保貨物高效配送的方法[19]。k-means算法傳統(tǒng)上是基于歐幾里得距離、余弦距離等對客戶進(jìn)行聚類,本文在傳統(tǒng)k-means算法的基礎(chǔ)上結(jié)合客戶服務(wù)時(shí)間窗設(shè)計(jì)了距離函數(shù),首先在時(shí)間范圍[t1,t2]內(nèi)對客戶進(jìn)行聚類,然后再考慮空間范圍,將客戶點(diǎn)指派到最臨近的聚類中心,如圖3所示。

圖3 k-means時(shí)空聚類示意圖

客戶點(diǎn)間時(shí)空距離的計(jì)算如下：

Dob=|xo-xb|+|yo-yb|+δ|t1o-t1b|+
δ|t2o-t2b|,o,b∈O。

(26)

式中：x,y表示地理坐標(biāo);t1,t2表示時(shí)間窗;δ表示距離與時(shí)間的轉(zhuǎn)換系數(shù)。

3.3 CW-NSGA-II混合算法設(shè)計(jì)

本研究設(shè)計(jì)了CW-NSGA-II混合算法用于求解三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化模型。NSGA-II是一種基于群體的啟發(fā)式算法[24-25],通常用于解決多目標(biāo)問題,CW算法用于生成初始種群,整個(gè)優(yōu)化過程在NSGA-II算法的基本框架上進(jìn)行設(shè)計(jì),并通過帕累托前沿進(jìn)行雙目標(biāo)解的帕累托優(yōu)化解排序,進(jìn)而通過排序選取帕累托優(yōu)化解并輸出雙目標(biāo)最優(yōu)解,這樣既能保證初始解的質(zhì)量,又可以很好地解決本文提出的雙目標(biāo)模型。

3.3.1 編碼方式

針對三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題,本研究采用整數(shù)編碼的方式構(gòu)造共享車輛的配送路徑染色體。假設(shè)配送中心為6個(gè)客戶提供配送服務(wù),其初始配送安排如圖4所示。其中0表示配送中心,其余整數(shù)表示各客戶。根據(jù)配送車輛空間各區(qū)域裝載貨物的最大數(shù)量、車輛最大載重能力以及客戶的時(shí)間窗等約束,用自然數(shù)0對染色體進(jìn)行解碼,形成相應(yīng)的子路徑。由圖3可知,該染色體可解碼為[0,2,4,3,0]與[0,6,5,1,0]兩條子路徑,即配送車輛V1的配送路徑為：配送中心0→客戶2→客戶4→客戶3→配送中心0;配送車輛V2的配送路徑為：配送中心0→客戶6→客戶5→客戶1→配送中心0。

圖4 染色體編碼和路徑解碼說明

3.3.2 交叉操作

圖5 2-opt*交叉操作過程

3.3.3 變異操作

變異操作是在選擇、交叉生成的種群中隨機(jī)選擇一條染色體,并使染色體上隨機(jī)選擇的兩個(gè)基因發(fā)生突變,產(chǎn)生新的染色體的過程。其步驟如下：首先,根據(jù)突變概率值Pm隨機(jī)選擇父代中的一個(gè)染色體;然后,在父代染色體中隨機(jī)選擇兩個(gè)基因進(jìn)行交換,交換后產(chǎn)生一個(gè)新的子代染色體。變異操作后,判斷配送車輛路徑所對應(yīng)的車輛裝載方案是否符合相關(guān)約束條件,若不符合,則應(yīng)重新進(jìn)行變異操作。變異過程如圖6所示。

圖6 變異過程

3.4 算法檢驗(yàn)

將CW-NSGA-II混合算法、多目標(biāo)和聲搜索算法(Multi-Objective Harmony Search Algorithm,MO-HSA)[27]和多目標(biāo)蟻群算法(Multi-Objective Ant Colony Optimization,MO-ACO)[28]進(jìn)行比較,實(shí)驗(yàn)數(shù)據(jù)是在所羅門數(shù)據(jù)集基礎(chǔ)上增加客戶貨物需求個(gè)數(shù)而來,具體實(shí)驗(yàn)數(shù)據(jù)參數(shù)如表4所示。算法參數(shù)設(shè)置如下：CW-NSGA-II、MO-HSA和MO-ACO算法中的種群規(guī)模popsize=100,最大迭代次數(shù)maxgen=200,精英迭代次數(shù)maxrun=20,精英染色體個(gè)數(shù)NN=30,選擇概率Ps=0.9,交叉概率Pc=0.9,變異概率Pm=0.1;MO-HSA算法中和聲庫大小HMS=100,和聲記憶庫保留概率HMCR=0.9,擾動(dòng)概率PAR=0.1,音調(diào)微調(diào)幅度BW=0.000 5;MO-ACO算法中信息素重要程度α=1,啟發(fā)式因子重要程度β=10,信息素蒸發(fā)系數(shù)ρ=0.5。將每種算法分別運(yùn)行30次,選取最優(yōu)的物流運(yùn)營總成本和車輛使用數(shù)以及對應(yīng)的求解時(shí)間,如表5所示。

表4 實(shí)驗(yàn)數(shù)據(jù)參數(shù)表

表5 不同算法優(yōu)化結(jié)果的比較

由表5可知,CW-NSGA-II算法、MO-HSA算法與MO-ACO算法的最小物流運(yùn)營成本的t檢驗(yàn)和p值的比較結(jié)果表明,CW-NSGA-II算法的最小物流運(yùn)營成本與其他兩種算法相比具有顯著差異性。此外,在物流運(yùn)營成本和車輛使用數(shù)方面,CW-NSGA-II算法均優(yōu)于MO-HSA算法和GA-ACO算法,CW-NSGA-II混合算法計(jì)算的物流運(yùn)營成本平均值比MO-HSA降低了8.86%,比MO-ACO降低了13.18%。在20組實(shí)例的求解平均時(shí)間方面,CW-NSGA-II混合算法比MO-HSA多耗時(shí)3 s,但是物流運(yùn)營成本和車輛使用數(shù)均優(yōu)于后者。

4 算例分析

4.1 算例相關(guān)數(shù)據(jù)

以重慶市某配送中心(DC)及其服務(wù)的120個(gè)客戶點(diǎn)(C1～C120)為例進(jìn)行研究,相應(yīng)的地理位置分布如圖7所示。配送中心所服務(wù)客戶的商品需求類型存在差異,且其中一部分客戶有多個(gè)服務(wù)時(shí)間窗,具體如表6所示。配送中心負(fù)責(zé)配送的貨物類型有4種,相應(yīng)的車廂空間根據(jù)貨物規(guī)格大小劃分為4個(gè)區(qū)域,各個(gè)區(qū)域大小、每種類型貨物的規(guī)格、重量和每個(gè)車廂區(qū)域可裝載的貨物數(shù)量如表7所示。

表7 各個(gè)區(qū)域大小及其裝載貨物的規(guī)格、重量和可裝載的貨物數(shù)量

圖7 配送中心與客戶點(diǎn)地理位置分布圖

4.2 結(jié)果與分析

在現(xiàn)有文獻(xiàn)[29-30]和多次實(shí)驗(yàn)計(jì)算的基礎(chǔ)上,相應(yīng)參數(shù)設(shè)置如下：車廂長L=4 m,車廂寬W=2 m,車廂高H=2 m,車輛最大載重量Q=700 kg,車輛最大裝載體積V=16 m2,車輛租賃成本rv=100 元/輛,車輛維修成本mv=30 元/輛,單位體積固定成本f=0.2 元,配送車輛單位距離行駛成本cv=0.8,車輛數(shù)V=12,車輛早到單位時(shí)間懲罰系數(shù)λ1=15,車輛晚到單位時(shí)間懲罰系數(shù)λ2=20。如表8所示為三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化前后運(yùn)營成本、車輛使用數(shù)以及車輛平均裝載率等的變化情況。

表8 三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化前后結(jié)果對比

由表8可知,車輛路徑優(yōu)化前后,車輛使用數(shù)減少了68.42%,車輛租賃成本降低68.42%,配送線路數(shù)減少5.3%,車輛平均使用頻次提高200%,時(shí)間窗違反時(shí)間減少84.62%,違反時(shí)間窗懲罰成本降低84.29%,配送時(shí)間減少了9.8%,配送成本降低了27.97%,物流運(yùn)營成本節(jié)約了48%,平均裝載率提高8.69%。此外,本文選取了車輛使用數(shù)、平均裝載率、違反時(shí)間窗的懲罰成本,物流運(yùn)營成本和車輛平均使用頻次等指標(biāo),繪制了各個(gè)指標(biāo)優(yōu)化前后的對比圖,如圖8所示。由圖8可知,優(yōu)化后車輛使用數(shù)、違反時(shí)間窗的懲罰成本和物流運(yùn)營成本均大幅減少,而平均裝載率和車輛平均使用頻次有所增加。

本文將客戶時(shí)間窗劃分為3個(gè)服務(wù)周期進(jìn)行研究,在每個(gè)服務(wù)周期內(nèi),應(yīng)用CW-NSGA-II混合算法求解了三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題,求得各服務(wù)周期的優(yōu)化配送方案,各共享車輛的平均裝載率以及不同共享頻次的車輛平均裝載率,具體結(jié)果如表9所示。

表9 三維裝載優(yōu)化后共享車輛配送方案

續(xù)表9

由表9可知,以物流成本最小化和車輛使用數(shù)最小化為目標(biāo)進(jìn)行優(yōu)化研究,優(yōu)化后的配送方案中,配送中心需要派遣12輛車對120個(gè)客戶進(jìn)行配送服務(wù)。在三維裝載優(yōu)化過程中,配送車輛SV1～SV10均在3個(gè)服務(wù)周期進(jìn)行了車輛共享,而配送車輛SV11和SV12均在2個(gè)服務(wù)周期進(jìn)行了車輛共享。此外,3個(gè)服務(wù)周期內(nèi)共享車輛(SV1～SV10)的平均裝載率為84.88%,2個(gè)服務(wù)周期內(nèi)共享車輛(SV11和SV12)的平均裝載率為80.92%。

此外,本研究選取了車輛在共享次數(shù)為3情況下平均裝載率最高的共享車輛9和車輛在共享次數(shù)為2情況下平均裝載率最高的共享車輛11,分別繪制了它們在各個(gè)服務(wù)周期的三維裝載圖,如圖9和圖10所示。共享車輛9和11在各服務(wù)周期的各區(qū)域裝載率和整車廂裝載率如表10和表11所示,并繪制了共享車輛9和11在各服務(wù)周期的各區(qū)域裝載率和整車廂裝載率的對比圖,如圖11和圖12所示。

表10 第一服務(wù)周期[8,12]內(nèi)SV9和SV11的裝載率對比 %

表11 第二服務(wù)周期[12,16]內(nèi)SV9和SV11的裝載率對比 %

圖9 SV9在各服務(wù)周期配送方案的三維裝載圖

圖10 SV11在各服務(wù)周期配送方案的三維裝載圖

圖11 第一服務(wù)周期[8,12]內(nèi)SV9和SV11的裝載率對比

由圖11可知,共享車輛9和共享車輛11在第一服務(wù)周期內(nèi),區(qū)域1的裝載率均為95.06%,區(qū)域2的裝載率均為72.05%,區(qū)域4的裝載率均為99%,共享車輛9區(qū)域3和整車廂的裝載率比共享車輛11分別高49%和14.7%。由圖12可知,共享車輛9和共享車輛11在第二服務(wù)周期內(nèi),區(qū)域1的裝載率均為95.06%,區(qū)域3的裝載率均為98%,共享車輛9區(qū)域2的裝載率比共享車輛11低48.37%,而區(qū)域4和整車裝載率比共享車輛11分別高出33%和7.6%。綜上所述,共享車輛的區(qū)域裝載率和整車廂裝載率會(huì)隨著服務(wù)周期和車輛使用頻次的改變而發(fā)生變化,且提高共享車輛的使用頻次可以有效提高共享車輛的平均裝載率。

4.3 分析與討論

三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題是以物流運(yùn)營成本和車輛使用數(shù)為優(yōu)化目標(biāo),不同車廂空間的分區(qū)模式通過影響貨物在車廂中的裝載方式,進(jìn)而影響車輛使用數(shù)和物流運(yùn)營成本。為了進(jìn)一步研究不同車廂空間分區(qū)模式對優(yōu)化目標(biāo)的影響,本文假定車廂空間平均分成2個(gè)區(qū)域、3個(gè)區(qū)域、4個(gè)區(qū)域和按貨物規(guī)格大小分成4個(gè)區(qū)域4種模式,考慮到車廂分區(qū)會(huì)增加配送車輛上的操作時(shí)間和成本,本研究假定車廂最大的空間區(qū)域劃分?jǐn)?shù)為4,不同車輛空間分區(qū)模式如圖13所示。4種模式下平均裝載率,物流運(yùn)營成本,車輛使用數(shù)和車輛平均使用頻次的變化情況,如表12所示。不同車廂空間分區(qū)模式下平均裝載率、物流運(yùn)營成本、車輛使用數(shù)以及車輛平均使用頻次的對比如圖14所示。

表12 不同車廂空間分區(qū)模式下優(yōu)化結(jié)果對比

圖13 不同車廂空間分區(qū)模式

圖14 不同車廂空間分區(qū)模式下優(yōu)化結(jié)果對比

由表12和圖14可知,當(dāng)共享配送車輛的車廂空間按照貨物規(guī)格大小分為4個(gè)區(qū)域時(shí),可得到最少的車輛使用數(shù)、最低的物流運(yùn)營成本、最高的車輛平均裝載率和最多的共享車輛使用頻次。而將車廂空間平均分成2個(gè)區(qū)域,3個(gè)區(qū)域和4個(gè)區(qū)域3種情況相比于車廂空間按貨物規(guī)格大小分成4個(gè)區(qū)域,物流運(yùn)營成本分別增加了3 301元、3 686元和3 138元,車輛使用數(shù)分別增加了9輛、10輛和9輛,平均裝載率分別減少了34.26%、35.09%和34.26%,車輛平均使用頻次均減少了1次。綜上所述,按貨物規(guī)格大小進(jìn)行合理的空間區(qū)域劃分可以有效地降低物流運(yùn)營成本,減少車輛使用數(shù),增加車輛平均裝載率和提高車輛使用頻次。

5 結(jié)束語

本文研究了三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化問題,首先,結(jié)合客戶多個(gè)服務(wù)時(shí)間窗的需求和空間地理位置進(jìn)行合理的服務(wù)周期劃分和k-means時(shí)空聚類,并在每個(gè)聚類單元內(nèi)根據(jù)客戶不同規(guī)格貨物需求和服務(wù)時(shí)間窗進(jìn)行合理的配送車輛調(diào)度和貨物裝載方式優(yōu)化。其次,建立了包含配送中心固定成本、配送車輛運(yùn)輸成本、維修成本、租賃成本和違反時(shí)間窗懲罰成本的物流運(yùn)營總成本最小化和配送車輛使用數(shù)最小化的雙目標(biāo)優(yōu)化模型。然后,設(shè)計(jì)了一種基于k-means時(shí)空聚類的CW-NSGA-II混合算法求解模型,該算法引入CW節(jié)約算法以提高初始解的質(zhì)量,并結(jié)合NSGA-II算法提高了混合算法獲取優(yōu)化解的全局和局部空間搜索能力,并在混合算法過程中設(shè)計(jì)了聚類算法和智能算法間的選擇性賦予機(jī)制,進(jìn)一步提高了混合算法的尋優(yōu)能力。最后,將CW-NSGA-II混合算法與MO-HSA混合算法、MO-ACO混合算法進(jìn)行了對比分析研究,驗(yàn)證了本研究提出的混合算法的有效性和合理性。

本文結(jié)合重慶市某配送中心的三維裝載物流配送實(shí)際數(shù)據(jù),通過模型求解對各類不同需求客戶的貨物運(yùn)輸配送路線和裝載方式進(jìn)行了聯(lián)合優(yōu)化,進(jìn)一步驗(yàn)證了模型與算法的可行性。計(jì)算結(jié)果表明,相對于優(yōu)化前的車輛路徑方案,三維裝載約束下基于運(yùn)輸資源共享的車輛路徑優(yōu)化方案的物流運(yùn)營成本和車輛使用數(shù)分別減少了48%和68.42%,違反時(shí)間窗的懲罰成本降低了84.29%,平均裝載率提高了8.69%。本文在實(shí)際算例的基礎(chǔ)上探討了不同空間分區(qū)模式下物流成本、車輛使用數(shù)、平均裝載率以及共享車輛使用頻次的變化情況。研究表明,根據(jù)客戶需求貨物種類數(shù)和不同種類貨物的規(guī)格大小劃分配送車輛車廂空間區(qū)域,能有效降低物流運(yùn)營總成本,減少配送車輛使用數(shù),且提高共享車輛使用頻次可以有效提高車輛平均裝載率。本研究為基于運(yùn)輸資源共享的三維裝載物流網(wǎng)絡(luò)優(yōu)化問題研究提供了相應(yīng)方法借鑒,未來研究將結(jié)合收集裝載問題、客戶動(dòng)態(tài)需求裝載問題以及多車型協(xié)同調(diào)度裝載問題研究三維裝載約束下基于運(yùn)輸資源共享的車輛路徑問題,進(jìn)而豐富三維裝箱調(diào)度理論并拓展其應(yīng)用領(lǐng)域。