王 勇,魏遠晗,蔣 瓊,許茂增

(重慶交通大學 經濟與管理學院,重慶 400074)

0 引言

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

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

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

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

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

1 問題描述

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

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

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

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

2 模型建立

2.1 符號定義

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

表2 變量定義

2.2 模型構建

本文以配送中心的物流運營成本Z1最小化和配送車輛使用數Z2最小化為優(yōu)化目標,建立了具有普適性的三維裝載約束下基于運輸資源共享的車輛路徑優(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)表示服務周期t內每個客戶點僅接受一輛配送車輛服務;式(4)表示每個客戶在服務周期t內僅接受一條配送線路服務;式(5)表示配送車輛將貨物送達客戶后必須離開;式(6)表示消除子回路約束;式(7)表示服務周期t內配送車輛v的使用次數等于其配送線路數之和;式(8)表示在服務周期t內配送車輛v上各區(qū)域內貨物數量的約束;式(9)表示在服務周期t內配送車輛v上裝載貨物的總重量不超過配送車輛的最大裝載量;式(10)和式(11)表示配送車輛到達客戶點的時間,式(12)和式(13)表示配送車輛離開和到達配送中心的時間必須在其服務時間窗內;式(14)～式(16)表示貨物必須擺放在車廂內;式(17)～式(19)表示配送車輛任何區(qū)域內裝載貨物長寬高的加和不能超出區(qū)域長寬高的限制;式(20)表示后服務客戶的貨物不能壓在先服務客戶貨物的上面;式(21)表示后服務客戶的貨物不能擋在先服務客戶貨物的前方;式(22)～式(25)表示變量約束。

3 CW-NSGA-II混合算法

3.1 算法過程描述

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

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

圖2 混合算法流程圖

3.2 基于k-means的時空聚類

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

圖3 k-means時空聚類示意圖

客戶點間時空距離的計算如下：

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

(26)

式中：x,y表示地理坐標;t1,t2表示時間窗;δ表示距離與時間的轉換系數。

3.3 CW-NSGA-II混合算法設計

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

3.3.1 編碼方式

針對三維裝載約束下基于運輸資源共享的車輛路徑優(yōu)化問題,本研究采用整數編碼的方式構造共享車輛的配送路徑染色體。假設配送中心為6個客戶提供配送服務,其初始配送安排如圖4所示。其中0表示配送中心,其余整數表示各客戶。根據配送車輛空間各區(qū)域裝載貨物的最大數量、車輛最大載重能力以及客戶的時間窗等約束,用自然數0對染色體進行解碼,形成相應的子路徑。由圖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 變異操作

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

圖6 變異過程

3.4 算法檢驗

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

表4 實驗數據參數表

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

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

4 算例分析

4.1 算例相關數據

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

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

圖7 配送中心與客戶點地理位置分布圖

4.2 結果與分析

在現有文獻[29-30]和多次實驗計算的基礎上,相應參數設置如下：車廂長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,車輛數V=12,車輛早到單位時間懲罰系數λ1=15,車輛晚到單位時間懲罰系數λ2=20。如表8所示為三維裝載約束下基于運輸資源共享的車輛路徑優(yōu)化前后運營成本、車輛使用數以及車輛平均裝載率等的變化情況。

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

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

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

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

續(xù)表9

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

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

表10 第一服務周期[8,12]內SV9和SV11的裝載率對比 %

表11 第二服務周期[12,16]內SV9和SV11的裝載率對比 %

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

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

圖11 第一服務周期[8,12]內SV9和SV11的裝載率對比

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

4.3 分析與討論

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

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

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

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

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

5 結束語

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

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