多車型聯(lián)運(yùn)整車物流配送優(yōu)化模型及算法研究

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

（南昌大學(xué) 機(jī)電工程學(xué)院，南昌 330031）

0 引言

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

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

1 配送問題的數(shù)學(xué)描述

1.1 問題描述

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

1.2 數(shù)學(xué)模型

整車配載數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：

約束條件：

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

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

2 算法設(shè)計與分析

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

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

2.1 客戶目的地聚類

隨著業(yè)務(wù)不斷擴(kuò)展，客戶點(diǎn)越來越多，布局越來越散亂，為提高轎運(yùn)車的運(yùn)載效率，借鑒數(shù)據(jù)挖掘中聚類分析思想，需對客戶點(diǎn)進(jìn)行系統(tǒng)聚類，形成各個方向的客戶節(jié)點(diǎn)單元群，整體上按各中心客戶群方向配送，并在MATLAB中實(shí)現(xiàn)此算法。

步驟1：客戶節(jié)點(diǎn)N個，即有N個類，根據(jù)各個點(diǎn)之間的實(shí)際距離公里數(shù)，假設(shè)某兩節(jié)點(diǎn)間連通有障礙，設(shè)其距離為+∞，得到距離矩陣D0；

步驟2：合并距離最近的兩點(diǎn)歸為一個新類，計算各類之間的客戶節(jié)點(diǎn)個數(shù)；

步驟3：計算新類與當(dāng)前各類的距離，若類的個數(shù)等于1，轉(zhuǎn)步驟4，否則，轉(zhuǎn)步驟2；

步驟4：畫聚類圖；

步驟5：決定類的個數(shù)，及各類包含的客戶節(jié)點(diǎn)數(shù)。

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

2.2 啟發(fā)式配載優(yōu)化算法

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

步驟1：先求解整數(shù)規(guī)劃對應(yīng)的線性規(guī)劃，判斷是否有解，若全為整數(shù)解，則求解結(jié)束，否則選出非整數(shù)的決策變量xi和初目標(biāo)值z0；

步驟2：對每個非整數(shù)變量xi進(jìn)行下取整和上取整后的線性規(guī)劃，得出相應(yīng)的線性規(guī)劃的目標(biāo)值根據(jù)優(yōu)中取優(yōu)準(zhǔn)則，取最優(yōu)決策目標(biāo)，即取兩者中較小值；

2.3 基于改進(jìn)Dijkstra的車輛路徑算法

在同一方向的客戶節(jié)點(diǎn)單元群內(nèi)，節(jié)點(diǎn)間不同的車輛行駛線路和商品車裝卸，產(chǎn)生的運(yùn)送費(fèi)用也大不相同。為降低運(yùn)送支出成本，基于改進(jìn)Dijkstra[11]的路徑算法對客戶節(jié)點(diǎn)單元群內(nèi)各節(jié)點(diǎn)進(jìn)行排序處理，并在MATLAB中實(shí)現(xiàn)此算法。

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

步驟2：取do,t(t=1,2,…,n)中最大值的節(jié)點(diǎn)預(yù)設(shè)為最終節(jié)點(diǎn)；

步驟3：調(diào)用newdijkstra函數(shù)[11]，得出線路集RS和最短總公里數(shù)，及未經(jīng)節(jié)點(diǎn)集NS；

步驟4：判斷RS集合數(shù)是否為n+1，若是，轉(zhuǎn)步驟6，否則，轉(zhuǎn)步驟5；

步驟5：取NS的一個節(jié)點(diǎn)，將其插入RS中，重新計算加入新節(jié)點(diǎn)的線路集RS和最短總公里數(shù)，及剩余的未經(jīng)節(jié)點(diǎn)集NS；轉(zhuǎn)步驟4；

步驟6：輸出最終線路節(jié)點(diǎn)集。

圖2 車輛路徑優(yōu)化算法流程圖

表1 訂單信息表

表2 客戶節(jié)點(diǎn)距離表/km

3 數(shù)據(jù)仿真與結(jié)果分析

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

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

將下層曲面折算至平面后，承運(yùn)車參數(shù)如表3所示。

表3 承運(yùn)車參數(shù)表

商品車參數(shù)如表4所示。

表4 商品車參數(shù)表

3.1 客戶節(jié)點(diǎn)聚類圖

根據(jù)上述訂單及商品車、轎運(yùn)車信息，調(diào)用客戶節(jié)點(diǎn)的系統(tǒng)聚類算法對訂單的客戶目的地進(jìn)行聚類，結(jié)果如圖3所示。

3.2 配送計劃表

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

圖3 客戶節(jié)點(diǎn)聚類圖

每輛承運(yùn)車詳細(xì)配送信息如表6所示。

3.3 結(jié)果分析

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

4 結(jié)論

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

表5 承運(yùn)車配載信息表

表6 配送詳細(xì)信息表

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

[2]徐天亮,劉小群.多品種貨物配裝的優(yōu)化方法[J].華中科技大學(xué)學(xué)報:自然科學(xué)版,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]李瑩瑩.基于優(yōu)化粒子群算法的物流配送路徑問題研究[D].北京交通大學(xué),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].工業(yè)工程與管理,2006,(06):15-18+32.

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

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

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

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

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