多車型聯運整車物流配送優化模型及算法研究

錢 丹，劉建勝，袁 彬，羅大海

（南昌大學 機電工程學院，南昌 330031）

0 引言

整車物流是指從汽車在制造廠完成組裝下線后開始，直到送達用戶手中為止的一系列倉儲、運輸、維護、檢驗、加工以及其他各種增值服務過程，是實物流、信息流、資金流的統一[1]。整車物流屬于一般商品物流范疇，目前對普通商品物流的研究比較多，如徐天亮等充分考慮車輛的載重能力及其容積.在建立貨物配裝的數學模型[2]；Salani M等研究了基于時間窗約束的物流線路優化問題[3]，李瑩瑩采用粒子群優化方法對物流配送路徑進行了研究[4]，Qingfang Ruan等以成本最低為優化目標，建立了結合配載和線路優化的混合優化方法[5]。

由于汽車商品與普通商品相比有其特殊，因此，汽車整車物流也有其自身的特點。一般商品物流優化調度問題可歸結于裝箱問題和線路優化問題，主要考慮承載空間及貨物尺寸形狀的約束，較少考慮承運車的實際運輸能力約束，如自重、載重、限重以及相關的運輸管理規則等。區別于一般物流，整車物流的運輸能力約束相比其他約束條件凸顯更為重要，已成為制約整車物流績效重要因素，整車物流配送優化一般包括整車配載優化（Finished vehicle loading problem，FVLP）和整車路徑優化（Finished vehicle routing problem，FVRP）。目前對整車物流配送優化研究不多[6]，馬士華等在以整車運輸能力為約束的條件下，研究了同一承運車型的汽車整車物流準時配載計劃[7]；秦緒偉等建立了整車物流網絡規劃集成優化模型[8]；王婷等研究了基于返程帶貨的共同配送的線路優化問題[9]，這類研究大多是對FVLP和FVRP問題獨立進行研究。但是FVLP和FVRP兩者之間是相互影響、相互制約，FVRP優化是以FVLP的結果為輸入，而FVLP裝載順序又必須考慮FVRP規劃的客戶群先后到達順序，否則帶來裝卸的不便。因此，將FVLP和FVRP聯合優化更符合物流管理實際需求，然而較少對FVLP和FVRP統一研究的。在張磊建立的整車配載和運輸路線優化模型中[10]，未對空間尺寸約束加以具體考慮。因此論文以FVLP和FVRP的集成研究為切入點，基于細化的配載空間粒度和實際運輸能力等約束條件，建立貼近實際需求的整車配送優化模型，重點對整車物流配載和線路優化中的算法進行詳細研究，以提高優化算法的運行效率，從而提高訂單處理和執行效率，并進行仿真計算與實驗。

1 配送問題的數學描述

1.1 問題描述

某物流公司裝車庫配有多種型號的轎運車M輛，其車輛自重、體積不完全相同，主機廠下達的客戶訂單N個，并且每個訂單目的地不同，轎運車與訂單基本信息已知，在滿足不同約束條件，通過合理選擇配載和運輸線路，使承運車發揮最大配載價值，運輸支出費用最小，企業利潤最大，提升服務品質和工作效率。

1.2 數學模型

整車配載數學模型如下：

目標函數：

約束條件：

其中：m為轎運車數量，第k()輛轎運車的排數為Tk，自重為wzk，下層折算后高度為Hk1，公路承載能力的限制載重最大標準為Gk，運輸中路橋費為Crk，油費為Cok，罰款費用為Cfk，轎運車的總排數為為訂單數量，第i(j=1,2,…,n)訂單目的地節點為di，第i訂單中商品車高度為hi，總數量為Ni，第j(j=1,2,…,t)排第i種商品車的收入單價為cij，數量為xij，重量為wij，長度為lij；第j排長度為Lj。

式(1)～式(4)為目標函數，其中式(1)表示在滿足配載約束條件下最大收入；式(2)表示在滿足配載約束條件下最少運輸支付費用；式(3)表示每輛轎運車在滿足配載約束條件下最大裝載率；式(4)表示每輛轎運車在滿足配載約束條件下的最低總重量。式(5)～式(9)為約束條件，其中式(5)表示結果為非零正整數約束；式(6)表示轎運車每排長度約束；式(7)表示每種商品車數量約束；式(8)表示每輛轎運車下層高度約束；式(9)表示每輛轎運車最大重量約束。

2 算法設計與分析

問題的輸入是包含商品車各種參數、不同交貨期、不同目的地等信息的客戶訂單，以及裝車庫可用承運車運力信息，輸出的是承轎運車的配載計劃和線路方案。目標是訂單響應時間和配載時間最短，運輸支出成本最小。

針對整車配載、線路問題本身的復雜性，本文采用分層解決策略，具體思路為：基于聚類分析思想，對訂單目的地節點進行分群處理，形成各個方向的客戶節點單元群，再對分類后的節點信息和裝車點進行線路預排序處理，結合訂單中商品車信息、承運車等信息進行預配載優化，得出最后配送計劃。

2.1 客戶目的地聚類

隨著業務不斷擴展，客戶點越來越多，布局越來越散亂，為提高轎運車的運載效率，借鑒數據挖掘中聚類分析思想，需對客戶點進行系統聚類，形成各個方向的客戶節點單元群，整體上按各中心客戶群方向配送，并在MATLAB中實現此算法。

步驟1：客戶節點N個，即有N個類，根據各個點之間的實際距離公里數，假設某兩節點間連通有障礙，設其距離為+∞，得到距離矩陣D0；

步驟2：合并距離最近的兩點歸為一個新類，計算各類之間的客戶節點個數；

步驟3：計算新類與當前各類的距離，若類的個數等于1，轉步驟4，否則，轉步驟2；

步驟4：畫聚類圖；

步驟5：決定類的個數，及各類包含的客戶節點數。

圖1 客戶群聚類算法流程圖

2.2 啟發式配載優化算法

考慮到運輸規則及成本控制，訂單處理應遵守完整性原則，盡量以最少的拆分，以整體進行配送。即能用一輛車完成客戶的配送，不拆分至多輛承運車配送。整車配載屬于復雜整數線性規劃問題（ILP），常規分枝定界算法是求解ILP的有效方法。但處理較大規模問題時，常規分支定界算法分枝過于復雜，線性規劃運算次數增加特別明顯，迭代消耗的時間則相應大幅增加。為滿足整車配載快速高效的要求，改進的分枝定界算法如下：

步驟1：先求解整數規劃對應的線性規劃，判斷是否有解，若全為整數解，則求解結束，否則選出非整數的決策變量xi和初目標值z0；

步驟2：對每個非整數變量xi進行下取整和上取整后的線性規劃，得出相應的線性規劃的目標值根據優中取優準則，取最優決策目標，即取兩者中較小值；

2.3 基于改進Dijkstra的車輛路徑算法

在同一方向的客戶節點單元群內，節點間不同的車輛行駛線路和商品車裝卸，產生的運送費用也大不相同。為降低運送支出成本，基于改進Dijkstra[11]的路徑算法對客戶節點單元群內各節點進行排序處理，并在MATLAB中實現此算法。

步驟1：根據裝車庫d0與各客戶節點di及各客戶節點di之間的實際距離公里數假設某兩節點間連通有障礙，設其距離為+∞，得到距離矩陣D1；

步驟2：取do,t(t=1,2,…,n)中最大值的節點預設為最終節點；

步驟3：調用newdijkstra函數[11]，得出線路集RS和最短總公里數，及未經節點集NS；

步驟4：判斷RS集合數是否為n+1，若是，轉步驟6，否則，轉步驟5；

步驟5：取NS的一個節點，將其插入RS中，重新計算加入新節點的線路集RS和最短總公里數，及剩余的未經節點集NS；轉步驟4；

步驟6：輸出最終線路節點集。

圖2 車輛路徑優化算法流程圖

表1 訂單信息表

表2 客戶節點距離表/km

3 數據仿真與結果分析

假設某批從裝車庫d0至某省13個目的地di的訂單信息如表1所示。

裝車庫與各目的地之間高速公路距離如表2所示。

將下層曲面折算至平面后，承運車參數如表3所示。

表3 承運車參數表

商品車參數如表4所示。

表4 商品車參數表

3.1 客戶節點聚類圖

根據上述訂單及商品車、轎運車信息，調用客戶節點的系統聚類算法對訂單的客戶目的地進行聚類，結果如圖3所示。

3.2 配送計劃表

從客戶目的地聚類圖中，可大致將客戶目的地分為4大群，分別為：G1 = {d3，d10，d2，d4，d7，d1，d12，d6}；G2 = {d5}；G3 = {d8，d13}；G4 = {d9，d11}。將客戶目的地群G1細分，得：G11={ d3，d10，d2，d4，d7} ，G12 ={d1，d12，d6}。調用啟發式配載優化算法及改進Dijkstra的FVRP算法，得出需要7輛承運車進行配載，詳細信息如表5所示。

圖3 客戶節點聚類圖

每輛承運車詳細配送信息如表6所示。

3.3 結果分析

表5中每輛轎運車裝載商品車數量平均，車貨總重控制在高速公路限載標準之內，表6中包含了具體配載明細和配送行駛路線，從配載明細中發現，每輛轎運車盡可能將同一個目的地的客戶訂單及同一客戶群的訂單配載在一起，符合實際整車物流管理需求。

4 結論

現代汽車制造業面向訂單的多品種、少批量的生產模式，直接導致了整車物流配送客戶目的點多，線路分散等問題，論文運用聚類分析方法，將客戶點進行聚類，形成以某客戶點為核心的目的群，有效提高配載和線路規劃的效率和性能?？紤]實際運輸能力約束條件，以最大收入和最小支出為優化目標，建立了配載優化模型，利用波動分析方法改進分支定界算法，實現配載的新啟發式配送優化算法，利用改進Dijkstra算法快速優化各客戶節點群內部線路優化方案，通過一系列實驗分析，結果顯示了模型及算法的有效性和實用性。

表5 承運車配載信息表

表6 配送詳細信息表

[1]吳保峰,劉仲英.我國整車物流發展趨勢及資源整合問題研究[J].汽車工程,2005,27(03):367-371.

[2]徐天亮,劉小群.多品種貨物配裝的優化方法[J].華中科技大學學報:自然科學版,2003,31(9):15-17.

[3]Salani M,Vacca I.Branch and price for the vehicle routing problem with discrete split deliveries and time windows[J].European Journal of Operational Research,Volume 213,Issue 3,16 September 2011:470-477.

[4]李瑩瑩.基于優化粒子群算法的物流配送路徑問題研究[D].北京交通大學,2012.

[5]Qingfang Ruan,Zhengqian Zhang, LixinMiao, etl..A hybrid approach for the vehicle routing problem with three-dimensional loading constraints[J].Computers & Operations Research,Volume 40, Issue 6,June 2013:1579-1589.

[6]馬士華,張曉龍.基于物流能力約束的整車物流計劃[J].工業工程與管理,2006,(06):15-18+32.

[7]秦緒偉,范玉順,尹朝萬.整車物流網絡規劃問題的混合粒子群算法研究[J].系統工程理論與實踐,2006(7):47-53.

[8]王婷,劉峰濤.整車汽車物流共同配送模式設計與仿真[J].計算機系統應用,2011,20(8):122-125.

[9]李軍,郭耀煌.物流配送車輛優化調度理論與方法[M].北京:中國物資出版社,2001.

[10]張磊,袁建清,鄭磊.汽車整車配載與運輸路線優化方案及算法研究[J].計算機技術與發展,2011,21(6):219-222.

[11]袁彬,劉建勝,錢丹,等.一種基于改進Dijkstra的物流網絡路徑優化算法分析[J].制造業自動化,2014,(09):86-88+105.