錢(qián) 丹，劉建勝，袁 彬，羅大海

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

0 引言

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

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

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

1.1 問(wèn)題描述

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

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

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

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

約束條件：

其中：m為轎運(yùn)車數(shù)量，第k()輛轎運(yùn)車的排數(shù)為T(mén)k，自重為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種商品車的收入單價(jià)為cij，數(shù)量為xij，重量為wij，長(zhǎng)度為lij；第j排長(zhǎng)度為L(zhǎng)j。

式(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)車每排長(zhǎng)度約束；式(7)表示每種商品車數(shù)量約束；式(8)表示每輛轎運(yùn)車下層高度約束；式(9)表示每輛轎運(yùn)車最大重量約束。

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

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

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

2.1 客戶目的地聚類

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

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

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

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

步驟4：畫(huà)聚類圖；

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

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

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

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

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

步驟2：對(duì)每個(gè)非整數(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]的路徑算法對(duì)客戶節(jié)點(diǎn)單元群內(nèi)各節(jié)點(diǎn)進(jìn)行排序處理，并在MATLAB中實(shí)現(xiàn)此算法。

步驟1：根據(jù)裝車庫(kù)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的一個(gè)節(jié)點(diǎn)，將其插入RS中，重新計(jì)算加入新節(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è)某批從裝車庫(kù)d0至某省13個(gè)目的地di的訂單信息如表1所示。

裝車庫(kù)與各目的地之間高速公路距離如表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)聚類算法對(duì)訂單的客戶目的地進(jìn)行聚類，結(jié)果如圖3所示。

3.2 配送計(jì)劃表

從客戶目的地聚類圖中，可大致將客戶目的地分為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)車盡可能將同一個(gè)目的地的客戶訂單及同一客戶群的訂單配載在一起，符合實(shí)際整車物流管理需求。

4 結(jié)論

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

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

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

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

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

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

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

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

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

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