陳勝波，劉永平，何世偉，黎浩東

(1.深圳市城市交通規(guī)劃設計研究中心有限公司，廣東 深圳 518021；2.北京交通大學交通運輸學院，北京 100044)

?

【交通運輸】

整車物流雙層轎運車車輛裝載與路徑整合優(yōu)化研究

陳勝波1,2，劉永平1，何世偉2，黎浩東2

(1.深圳市城市交通規(guī)劃設計研究中心有限公司，廣東 深圳 518021；2.北京交通大學交通運輸學院，北京 100044)

根據啟發(fā)式算法思想，建立了雙層轎運車的車輛配載和路徑優(yōu)化的雙層規(guī)劃模型。在路徑優(yōu)化的求解中融入一定的啟發(fā)式搜索規(guī)則，設計了一種求解該雙層規(guī)劃模型的混合遺傳算法，并給出了算法的編碼方法、路徑搜索方法和適應度函數的定義。案例分析表明，當乘用車種數不超過3種時，采用LINGO商業(yè)優(yōu)化軟件能在1 min內求出最優(yōu)解；超過3種時求解時間呈指數增長。采用本文設計的混合遺傳算法，能在較快時間內求出最優(yōu)解，此模型和算法對編制大規(guī)模下的乘用車裝載和配送計劃具有較強的適用性和可行性。

物流工程；雙層轎運車運輸； 車輛裝載；路徑優(yōu)化；雙層規(guī)劃模型；混合遺傳算法

整車物流指的是按照客戶訂單對整車快速配送的全過程。隨著我國汽車工業(yè)的高速發(fā)展，整車物流量，特別是乘用車的整車物流量迅速增長。汽車整車的裝載(vehicle filling problem，VFP)和車輛運行的路徑規(guī)劃(vehicle routing problem，VRP)直接影響著企業(yè)的物流效益，一直以來也是業(yè)內專家的研究熱點。

無論是VFP還是VRP，都已被證明是NP難問題，規(guī)模較大時很難求出精確解。井祥鶴等[1]對集裝箱的裝載問題進行了研究，在基本遺傳算法和FFD算法的基礎上，提出了一種求解鐵路多車型平車的裝載問題的混合遺傳算法。許光濘等[2-4]分別采用自適應遺傳算法、模擬退火算法、混合遺傳算法等啟發(fā)式方法,對集裝箱和軍用物資的裝載問題進行了研究。Ganesh等[5-9]采用了聚類搜索啟發(fā)式算法、蟻群算法、動態(tài)規(guī)劃方法、禁忌搜索算法、多智能體進化搜索算法等對物流配送中的車輛路徑優(yōu)化問題進行了研究。在兩者的綜合優(yōu)化研究方面，張磊等[10-13]對車輛路徑及裝載的整合優(yōu)化問題進行了研究，其中文獻[10] 僅對單層情景下的整合優(yōu)化問題進行了研究，并且沒有考慮運輸車輛規(guī)格的影響；文獻[11]針對的是多品種貨物裝載及車輛路徑的整合優(yōu)化研究，并不適用于乘用車的配送問題。

目前關于路徑優(yōu)化、裝載或者兩者的綜合優(yōu)化問題的研究，絕大多數都是采用啟發(fā)式算法進行求解。但是單方面的研究較多，兩者的綜合研究特別是整車物流的車輛裝載和路徑整合優(yōu)化的研究較少，多數研究沒有考慮到雙層轎運車(運送汽車的車輛)對該問題的影響。而在現(xiàn)實生活中，很多物流公司在制定車輛的運輸計劃時主要依賴調度人員的經驗，在面對復雜的運輸任務時，往往效率較低，運輸成本較大。基于此，本文建立了基于雙層規(guī)劃的整車物流中的車輛裝載與路徑整合優(yōu)化模型，并針對大規(guī)模問題設計了混合遺傳算法進行求解。

1 問題描述

乘用車生產廠家根據全國客戶的購車訂單，向物流公司下達運輸乘用車到全國各地的任務，物流公司則根據下達的任務制定運輸計劃并配送這批乘用車。為此，物流公司首先要從可以調用的“轎運車”中選擇出若干輛轎運車，進而給出其中每一輛轎運車上乘用車的裝載方案和目的地，以保證運輸任務的完成。“轎運車”是通過公路來運輸乘用車整車的專用運輸車，根據型號的不同有單層和雙層兩種類型，由于單層轎運車實際中很少使用，本文僅考慮雙層轎運車。雙層轎運車又分為三種類型：上下層各裝載1列乘用車，記為1-1型(圖1)；下、上層分別裝載1、2列，記為1-2型(圖2)；上、下層各裝載2列，記為2-2型(圖3)。

圖1 1-1型轎運車Fig.1 Car carrier of type 1-1

圖2 1-2型轎運車Fig.2 Car carrier of type 1-2

圖3 2-2型轎運車Fig.3 Car carrier of type 2-2

在確保完成運輸任務的前提下，物流公司追求降低運輸成本。但由于轎運車、乘用車有多種規(guī)格，當前很多物流公司在制定運輸計劃時主要依賴調度人員的經驗，在面對復雜的運輸任務時，往往效率低下而且運輸成本不理想。在此種情況下，需要對乘用車的裝載以及轎運車的運輸路線進行優(yōu)化，并設計高效的求解算法。

2 模型構建

2.1 上層優(yōu)化模型

上層優(yōu)化模型是基于各類型乘用車需求數量，以及能夠提供的轎運車數量，在滿足相關裝載及約束條件下，使轎運車使用總成本最小。該成本是指每輛轎運車的購置及維修等固定使用成本，不包括走行費用的支出成本，假定乘用車數量足夠滿足需求。

(1)集合及參數定義：I為等待裝載的乘用車種類集合；ni(i∈I)為第i類乘用車的需求數量；li為第i類乘用車的長度；wi為第i類乘用車的寬度；hi為第i類乘用車的高度。K為轎用車種類集合；Pk為第k(k∈K)類轎運車的編號集合；ak表示第k(k∈K)類轎運車提供的數量；ck表示第k(k∈K)類轎運車的使用成本。G表示轎運車的層數集合，為了求解方便，根據能夠裝載的列數將轎運車層數分為4層，即將1-2型的上層看做2層，2-2型的上下層均視為2層進行求解；Lkg表示第k(k∈K)類轎運車第g(g∈G)層的裝載面長度；Wkg表示第k(k∈K)類轎運車第g(g∈G)層的裝載面寬度；Hkg表示第k(k∈K)類轎運車第g(g∈G)層的裝載面高度；Δl表示轎運車的縱向最小間隔；Δw表示轎運車的橫向最小間隔。

(3)模型構建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2.2 下層優(yōu)化模型

不同的裝載方案對應著不同的最優(yōu)轎運車走行方案。下層優(yōu)化模型是在上層優(yōu)化模型的基礎上，即得出車輛的裝載方案以后，對轎運車走行線路的優(yōu)化，使在滿足各個乘用車需求的同時，轎運車總走行成本最小。

(1)模型假設：乘用車配送中心只有一個，配送中心擁有運輸車輛和倉庫，轎運車到達目的地后原地待命，無須放空返回；車輛的最大行駛距離沒有限制；每輛轎運車一旦到達乘用車需求地后，與該地需求相應的乘用車全部卸下；卸車成本忽略不計。

(3)模型構建

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

3 模型求解

本文設計了相應的混合遺傳算法，即采用傳統(tǒng)的遺傳算法求解上層模型，然后結合現(xiàn)場經驗加入一定的啟發(fā)式搜索規(guī)則，求解下層模型得出路徑優(yōu)化方案。

3.1 染色體編碼

(23)

3.2 路徑優(yōu)化啟發(fā)式搜索

在求解下層模型前，首先需要對乘用車需求節(jié)點和轎運車相關屬性進行定義。

Step 1：采用Dijkstra算法求出任意兩點間的最短距離，并記錄每個節(jié)點n(n∈NS)和其他節(jié)點的最短距離。

Step 3：根據所求的轎運車使用情況及裝載方案，按照轎運車單位公里的走行成本從高到低排序，單位公里走行成本相同的乘用車隨機排序。

Step 7：若k>kmax，或者連續(xù)迭代30次，結果不變，程序結束，記錄下轎運車總的行駛成本v和對應的路徑方案r；否則執(zhí)行Step 2。

將裝載方案j下的最優(yōu)行駛成本與對應的裝載方案j的轎運車固定使用成本求和，帶入上層模型循環(huán)進行染色體適應度評估，同時將裝載方案對應的染色體進行選擇、交叉、變異等操作，生成的新一代染色體個體作為一個新的裝載方案執(zhí)行路徑優(yōu)化啟發(fā)式搜索，不斷記錄染色體評估適應度最優(yōu)值；若連續(xù)迭代30次或迭代次數超過300次值不變，則跳出循環(huán)，記錄的最終值則認為是最優(yōu)的裝載方案和最優(yōu)路徑方案。算法流程圖見圖4所示。

圖4 求解算法流程圖Fig.4 Solving algorithm flowchart

3.3 適應度函數

上層模型中是考慮每輛轎運車如何裝載使得總的轎運車固定使用成本最低，下層模型是最優(yōu)化每輛轎運車的配送路徑，使得總的配送成本最低。由于兩者單位相同，并且數量級相差不大。因此將上下層面模型所得目標函數值相加作為適應度函數。

3.4 遺傳算子的設計

選擇算子設計如下：首先將群體中的個體按照適應度值從大到小的順序進行排序，然后將排列在前面的個體復制兩份，將排列在中間部分的個體復制一份，排列在后面的個體不復制。這樣保證了在進化過程中每一代都能使適應度好的個體被選擇復制到新的種群中。

為了保證產生新個體的多樣性，采用雙點逆轉交叉的方法，首先對群體進行隨機配對，其次按照均勻分布隨機產生交叉位置，最后對配對染色體進行交叉操作，產生新個體。

變異操作是對個體的某一個或某一些基因座上的基因進行改變，產生新的個體。在模型中，采用多點動態(tài)變異的方法，變異點及其值在每個個體的每次變異中都是隨機產生的。

4 案例分析

4.1 相關數據

某物流公司要運輸的乘用車的規(guī)格及各地需求數量如表1所示，具體路線見圖5，其中點O是乘用車供給地，A、B、C、D是乘用車需求地；各段長度：OD=160 km，DC=76 km，DA=200 km，DB=120 km，BE=104 km，AE=60 km。

表1 乘用車規(guī)格及各需求地的需求數量

圖5 運輸線路圖Fig.5 Transportation routing map

表2是可調用的轎運車類型(含序號)、數量和裝載區(qū)域大小。1-1型及2-2型轎運車上、下層裝載區(qū)域相同；1-2型轎運車上、下層裝載區(qū)域長度相同，但上層比下層寬0.8 m。此外2-2型轎運車因為層高較低，上、下層均不能裝載高度超過1.7 m的乘用車。每輛轎運車能夠裝載的乘用車數量最小為6，最大為27輛；1-2型轎運車使用數量不能超過1-1型轎運車的20%；1-1型、1-2型以及1-3型轎運車單位公里的走行費用分別為1元、2元、2.5元；乘用車在裝載時，橫向與縱向最小間隔均不能低于0.1 m，由于是分為4層考慮，因此Δw=0.05，Δl=0.1。

表2 轎運車規(guī)格及供給數量

4.2 求解結果及分析

取種群規(guī)模為100，交叉概率為0.8，變異概率0.01，最大迭代次數為400次，采用C#編程在CPU頻率2.8 GHZ，內存2 G，操作系統(tǒng)Windows XP環(huán)境下實現(xiàn)上述混合遺傳算法。經過多次測試，最快在第223代得出最優(yōu)解347.422 8萬元。按照以上算法求解出的裝載方案如表3所示，1-1型轎運車總的需求數量為10輛，1-2型為12輛，2-2型為1輛。1-2型轎運車使用數量沒有超過1-1型轎運車使用數的20%，車輛的使用成本為346萬元，其中1-1型轎運車固定使用成本為100萬元，1-2型為216萬元，2-2型為30萬元；每輛轎運車的配送方案如表4所示，需求地的所有乘用車需求均能滿足，轎運車總運營成本為14 228元。

表3 裝載方案優(yōu)化結果

注： “/”左右表示同一層的兩列擺放方式； “A(B)”中的B表示乘用車編號，A表示乘用車裝載數量。

表4 配送方案優(yōu)化結果

注： “A(B )”中的B表示乘用車編號，A表示乘用車配送數量；表中需求地A、B、C、D下的每一列表示每輛轎運車在該地的配送方案，如表中的第二行第三列“1(1)/1(4)/4(6)”表示編號為1的1-1型轎運車配送給A地1輛編號為1的乘用車，1輛編號為4的乘用車和4輛編號為6的乘用車。

為了驗證遺傳算法求解上層模型的高效性，針對不同的乘用車車種數量，分別采用了LINGO優(yōu)化軟件和遺傳算法進行對比。結果如圖6和圖7所示，當乘用車車種不超過5種時，LINGO優(yōu)化軟件(圖6)在1 min內(最長52 s)都能得出最優(yōu)解；單一車種求解時，0.1 s即可得出最優(yōu)解；一旦車種超過3種時，求解時間呈指數增長。當乘用車車種個數超過5種時，在15 min內都難以得出最優(yōu)解。而采用混合遺傳算法時，對本案例的車種個數都進行了驗證(圖7)，雖然單一車種時求解時間比LINGO時間長，約為13 s，但是隨著規(guī)模的擴大，求解時間并沒有呈現(xiàn)指數增長的形式，而且當車種個數為9種時，最快452 s即可得出最優(yōu)解，體現(xiàn)了混合遺傳算法在求解此類大規(guī)模問題時的高效性。

圖6 Lingo軟件求解Fig.6 Solving results by Lingo software

圖7 混合遺傳算法求解Fig.7 Solving results by HGA

5 結論

轎運車的裝載和配送過程中的路徑優(yōu)化是影響物流企業(yè)經營效益的主要問題。本文針對雙層轎運車的裝載和路徑優(yōu)化問題進行了研究，構建了配裝與路徑同時優(yōu)化的雙層規(guī)劃模型。采用遺傳算法得出轎運車的配載方案，在此基礎上結合人工經驗，采用一定的啟發(fā)式規(guī)則對轎運車的行駛路徑進行優(yōu)化，最后通過案例分析，說明了本文設計的雙層規(guī)劃模型及算法對求解大規(guī)模整車物流配送問題具有較強的適用性。探索更高效率的求解算法是以后需要進一步研究的問題。

[1]井祥鶴，周獻中，徐延勇. 多型號平車裝載問題的混合遺傳算法[J]. 鐵道學報, 2006, 28(6):10-15.

[2]許光濘，肖志勇，俞金壽. 應用自適應遺傳算法解決集裝箱裝載問題[J]. 控制與決策, 2007, 22(11): 1280-1283.

[3] 張德富，彭煜，朱文興，等. 求解三維裝箱問題的混合模擬退火算法[J]. 計算機學報, 2009, 32(11)：2147-2156.

[4] 陳晨, 繆嘉嘉，李愛平，等. 機動車輛裝載問題的一種混合遺傳算法實現(xiàn)[J]. 計算機應用研究, 2007, 24(9)：34-36.

[5] GANESH K, NARENDRAN T T. CLOVES：A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up[J]. European Journal of Operational Research, 2007, 178(3): 699-717.

[6] REED M, YIANNAKOU A, EVERING R. An ant colony algorithm for the multi-compartment vehicle routing problem[J]. Applied Soft Computing, 2014, 15: 169-176.

[7] NOVOAAB C，STORER R. An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[J]. European Journal of Operational Research, 2009, 196(2): 509-515.

[8] 李建, 張永. 一類集散貨物路線問題的禁忌搜索算法設計[J]. 系統(tǒng)工程理論與實踐, 2007 (6): 117-123.

[9] 劉欣萌, 何世偉, 陳勝波, 等.帶時間窗VRP問題的多智能體進化算法[J]. 交通運輸工程學報, 2014, 14(3): 105-110.

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

[11] 牟欣. 物流配送中的車輛路徑與車輛裝載整合優(yōu)化問題研究[D]. 重慶: 重慶大學，2008.

[12] 侯麗曉. 車輛裝載和路徑安排聯(lián)合優(yōu)化問題研究[D]. 大連：大連海事大學，2010.

[13] ZHAO P, PAN W W, YUAN J X. Research for integrated vehicle scheduling and filling problem in logistics systems[EB/OL].[2016-04-05]. http://ascelibrary.org/doi/10.1061/40996%28330%29499.

Research on integrated optimization of double stack car carriers based vehicle loading and routing problems in vehicle logistics

CHEN Sheng-bo1,2, LIU Yong-ping1, HE Shi-wei2, LI Hao-dong2

(1.Shenzhen Urban Transport Planning Center, Shenzhen 518021, China; 2.Traffic and Transportation School of Beijing Jiaotong University, Beijing 100044, China)

∶Based on the heuristic algorithm, a double-decker programming model was established, in which both routing and filling problems of the double stack car carriers were considered. A hybrid genetic algorithm was proposed for solving double-decker programming model and a heuristic search principle was integrated in this algorithm to get the optimized routing. The coding method, routing search method and the dual fitness function were also defined. Finally, the empirical example reveal that when the number of type of cars what to be loaded is less than 3, LINGO software can be used to obtain the optimal solution within 1 minute. However, the solution time may be increased exponentially when the number is 3 or more. Using the hybrid genetic algorithm designed in this paper can get the optimal solution in a short time, which can prove the effectiveness and practicability of this model and algorithm in loading and distribution planning of passenger cars on large scales.

∶logistics engineering; double stack car transportation；vehicle filling; routing optimization; double-decker programming model; hybrid genetic algorithm

10.3976/j.issn.1002-4026.2017.03.013

2016-09-03

陳勝波(1990—)，男，工程師，碩士，研究方向為運輸組織現(xiàn)代化。E-mail: chensb@sutpc.com

U492.2

A

1002-4026(2017)03-0073-09