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

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

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

?

【交通運(yùn)輸】

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

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

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

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

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

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

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

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

1 問(wèn)題描述

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

圖1 1-1型轎運(yùn)車(chē)Fig.1 Car carrier of type 1-1

圖2 1-2型轎運(yùn)車(chē)Fig.2 Car carrier of type 1-2

圖3 2-2型轎運(yùn)車(chē)Fig.3 Car carrier of type 2-2

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

2 模型構(gòu)建

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

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

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

(3)模型構(gòu)建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

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

不同的裝載方案對(duì)應(yīng)著不同的最優(yōu)轎運(yùn)車(chē)走行方案。下層優(yōu)化模型是在上層優(yōu)化模型的基礎(chǔ)上，即得出車(chē)輛的裝載方案以后，對(duì)轎運(yùn)車(chē)走行線(xiàn)路的優(yōu)化，使在滿(mǎn)足各個(gè)乘用車(chē)需求的同時(shí)，轎運(yùn)車(chē)總走行成本最小。

(1)模型假設(shè)：乘用車(chē)配送中心只有一個(gè)，配送中心擁有運(yùn)輸車(chē)輛和倉(cāng)庫(kù)，轎運(yùn)車(chē)到達(dá)目的地后原地待命，無(wú)須放空返回；車(chē)輛的最大行駛距離沒(méi)有限制；每輛轎運(yùn)車(chē)一旦到達(dá)乘用車(chē)需求地后，與該地需求相應(yīng)的乘用車(chē)全部卸下；卸車(chē)成本忽略不計(jì)。

(3)模型構(gòu)建

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

3 模型求解

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

3.1 染色體編碼

(23)

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

在求解下層模型前，首先需要對(duì)乘用車(chē)需求節(jié)點(diǎn)和轎運(yùn)車(chē)相關(guān)屬性進(jìn)行定義。

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

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

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

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

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

3.3 適應(yīng)度函數(shù)

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

3.4 遺傳算子的設(shè)計(jì)

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

為了保證產(chǎn)生新個(gè)體的多樣性，采用雙點(diǎn)逆轉(zhuǎn)交叉的方法，首先對(duì)群體進(jìn)行隨機(jī)配對(duì)，其次按照均勻分布隨機(jī)產(chǎn)生交叉位置，最后對(duì)配對(duì)染色體進(jìn)行交叉操作，產(chǎn)生新個(gè)體。

變異操作是對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因進(jìn)行改變，產(chǎn)生新的個(gè)體。在模型中，采用多點(diǎn)動(dòng)態(tài)變異的方法，變異點(diǎn)及其值在每個(gè)個(gè)體的每次變異中都是隨機(jī)產(chǎn)生的。

4 案例分析

4.1 相關(guān)數(shù)據(jù)

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

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

圖5 運(yùn)輸線(xiàn)路圖Fig.5 Transportation routing map

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

表2 轎運(yùn)車(chē)規(guī)格及供給數(shù)量

4.2 求解結(jié)果及分析

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

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

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

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

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

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

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

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

5 結(jié)論

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

[1]井祥鶴，周獻(xiàn)中，徐延勇. 多型號(hào)平車(chē)裝載問(wèn)題的混合遺傳算法[J]. 鐵道學(xué)報(bào), 2006, 28(6):10-15.

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

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

[4] 陳晨, 繆嘉嘉，李?lèi)?ài)平，等. 機(jī)動(dòng)車(chē)輛裝載問(wèn)題的一種混合遺傳算法實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究, 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] 李建, 張永. 一類(lèi)集散貨物路線(xiàn)問(wèn)題的禁忌搜索算法設(shè)計(jì)[J]. 系統(tǒng)工程理論與實(shí)踐, 2007 (6): 117-123.

[9] 劉欣萌, 何世偉, 陳勝波, 等.帶時(shí)間窗VRP問(wèn)題的多智能體進(jìn)化算法[J]. 交通運(yùn)輸工程學(xué)報(bào), 2014, 14(3): 105-110.

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

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

[12] 侯麗曉. 車(chē)輛裝載和路徑安排聯(lián)合優(yōu)化問(wèn)題研究[D]. 大連：大連海事大學(xué)，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—)，男，工程師，碩士，研究方向?yàn)檫\(yùn)輸組織現(xiàn)代化。E-mail: chensb@sutpc.com

U492.2

A

1002-4026(2017)03-0073-09