鐵路平車裝載問(wèn)題模型及算法

劉宏偉（軍事交通學(xué)院，天津 300161）

鐵路平車裝載問(wèn)題模型及算法

劉宏偉
（軍事交通學(xué)院，天津 300161）

將平車裝載問(wèn)題抽象為一維裝箱問(wèn)題。針對(duì)鐵路軍事運(yùn)輸中平車裝載問(wèn)題建立了數(shù)學(xué)模型，并采用Best Fit近似算法、First Fit近似算法和Next Fit近似算法分別求解并比較分析，得出分析結(jié)果。

平車裝載；算法；優(yōu)化

1 引言

鐵路運(yùn)輸具有運(yùn)量大、速度快、不易受天候和季節(jié)的影響,適合遠(yuǎn)距離運(yùn)輸?shù)葍?yōu)點(diǎn),在現(xiàn)代物流中承擔(dān)著重要的運(yùn)輸任務(wù),同時(shí)也是部隊(duì)兵力機(jī)動(dòng)采用的機(jī)動(dòng)方式之一。研究鐵路輸送中的列車裝載問(wèn)題模型與算法，并運(yùn)用于相應(yīng)的軍事輔助決策系統(tǒng)，是適應(yīng)未來(lái)戰(zhàn)場(chǎng)、提高指揮效能的客觀需要。在鐵路運(yùn)輸中經(jīng)常會(huì)遇到輪式（履帶式）車輛裝備的運(yùn)輸裝載問(wèn)題,為了方便裝備的裝載及加固,一般選用木質(zhì)底板的鐵路平車進(jìn)行裝運(yùn),有些特殊裝備對(duì)平板車還有專門的要求。在鐵路運(yùn)輸中,裝載輪式車輛裝備可采用順裝、跨裝、爬裝、橫裝等方式,大中型車輛裝備的裝載常采用的是順裝,而其它的裝載方式都有嚴(yán)格的限制。目前,對(duì)于鐵路運(yùn)輸中裝載方案的制定,通常由有關(guān)人員根據(jù)相關(guān)規(guī)定和經(jīng)驗(yàn),采用手工作業(yè)方法制定。這種傳統(tǒng)的手工作業(yè)方法,費(fèi)時(shí)費(fèi)力,且很難保證所制定的方案為最優(yōu)方案,有很大的局限性,很難適應(yīng)現(xiàn)代鐵路運(yùn)輸?shù)男枰?。改革傳統(tǒng)的手工作業(yè)方式,建立科學(xué)合理的模型,并運(yùn)用于相應(yīng)的輔助決策系統(tǒng)是一個(gè)迫切需求的問(wèn)題[1]。

2 主要研究方法和技術(shù)路線

鐵路軍事運(yùn)輸平車裝載主要考慮兩個(gè)因素：平車和裝備。平車方面主要考慮的有：平車的長(zhǎng)度、寬度，平車的載重量。裝備方面主要考慮的有：裝備的長(zhǎng)、寬、高，裝備的重量，裝備是否超限等。本文在建立模型時(shí)，對(duì)相關(guān)因素進(jìn)行了簡(jiǎn)化，只考慮最主要的因素即:平車的長(zhǎng)度和裝備的長(zhǎng)度。綜合平車和裝備中要考慮的各個(gè)因素，聯(lián)系數(shù)學(xué)建模理論，建立模型,并對(duì)模型進(jìn)行分析優(yōu)化，再使用計(jì)算機(jī)多種近似算法對(duì)其進(jìn)行計(jì)算，得出結(jié)論，并對(duì)結(jié)論進(jìn)行比較分析。

3 鐵路平車裝載問(wèn)題模型

平車的裝載問(wèn)題可以描述為有m種裝備B1,B2,…,Bm需要裝車運(yùn)輸，已知各種裝備的數(shù)量為V1,V2,…,Vm，在平車上所占的長(zhǎng)度分別為l1,l2,…,lm，其重心距裝備前端的距離分別為d1,d2,…,dm,重量分別為W1,W2,…,Wm,設(shè)有Q種類型平車F1,F2,…,FQ可供使用,各種類型平車的數(shù)量分別為N1,N2,…,NQ,長(zhǎng)度分別為L(zhǎng)1,L2,…,LQ，車輛定距分別為S1,S2,…,SQ,載重量分別為Z1,Z2,…,ZQ,num為所使用平車的數(shù)量;xij為在所使用的平車序列中第 j輛平車上裝載第i種裝備的數(shù)量;D為相鄰兩裝備之間所允許的最小間距;aj為第 j輛平車上裝備總重心的縱向允許位移量;Yjτ為第 j輛平車上第τ件裝備重心到平車前端的距離;Wjτ為第 j輛平車上第τ件裝備的重量;ljr為第 j輛平車上第r件裝備的重心距其前端的距離;djτ為第 j輛平車上第τ件裝備在平車上所占的長(zhǎng)度;εj為第 j輛平車上第1件裝備的前端距車輛前端的距離[2]。采用順裝方式，可得如下關(guān)系：

滿足上述要求的可行裝載方案有多種,優(yōu)化的目標(biāo)就是從所有可行方案中尋求一種使用平車資源最省的方案。由于采用順裝,所以決定在一輛平車上裝載裝備的多少主要取決于平車和裝備的長(zhǎng)度。因此,這里可以用平車總長(zhǎng)度的利用率作為目標(biāo)函數(shù),即：

顯然，這是一個(gè)整數(shù)規(guī)劃問(wèn)題，而式(1)和式(7)中的求和上標(biāo)依賴于決策變量num，因此該問(wèn)題不是一個(gè)線性規(guī)劃問(wèn)題，也就無(wú)法使用傳統(tǒng)的分枝定界法來(lái)對(duì)問(wèn)題進(jìn)行求解，必須另外尋找解決問(wèn)題的辦法。該問(wèn)題可建模為裝箱問(wèn)題,利用BF(Best Fit)算法、FF(First Fit)算法和NF(Next Fit)算法等近似算法對(duì)該問(wèn)題求解。

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

鐵路平車裝載問(wèn)題實(shí)際上可以看作是一個(gè)裝箱問(wèn)題，它們?cè)诒举|(zhì)上是一致的，就是都是研究裝載同樣多的貨物，怎樣裝載能使用最少的平車或箱子。

裝箱問(wèn)題是NP完全問(wèn)題，在多項(xiàng)式時(shí)間內(nèi)不能保證找到最優(yōu)裝箱方案。因此，人們探索求解裝箱問(wèn)題的近似算法，這項(xiàng)工作較早地獲得了成功，由于近似算法在解決這類裝箱問(wèn)題中近似度比較小，所以很有實(shí)用價(jià)值。

大多數(shù)裝箱問(wèn)題的近似算法采用貪心策略，即把為了求優(yōu)化結(jié)果進(jìn)行的總體規(guī)劃簡(jiǎn)化為每一步驟的“貪心”處理，即為每次物品裝箱規(guī)定一種局部選擇方法，不同的貪心選擇方法產(chǎn)生不同的策略。由于實(shí)踐中裝箱問(wèn)題的輸入長(zhǎng)度n較大，近似算法的時(shí)間代價(jià)與解 的優(yōu)化程度之間的權(quán)衡是很受重視的。下面介紹三種不同的局部?jī)?yōu)化策略。

4.1 最佳適應(yīng)（Best Fit，BF）算法

BF策略總是把物品裝到能夠裝下它并且目前是最滿的箱子里[3]。

設(shè)Si為第i個(gè)物品的大小，Bj為第 j個(gè)箱子，used(j)為Bj已被占用的部分，則BF策略可描述為：

（1）第一個(gè)物品(S1≤1)裝到第一個(gè)（空）箱子B1中。

（2）下一個(gè)物品(Si≤1)裝到Bj中，其中Bj滿足：

（3）如果i＜n，轉(zhuǎn)到第二步，否則停止。

例如，n=10，S=(0.4，0.2，0.7，0.3，0.5，0.4，0.4，0.3，0.6，0.2)。

采用BF策略設(shè)計(jì)出的近似算法，其裝箱結(jié)果如圖1所示。

圖1 BF算法裝箱結(jié)果

BF策略的結(jié)果較好，但每次要在已裝物品的箱子中選取剩余空間最小者，比較麻煩。

Best Fit算法的中心思想是物品裝到能夠裝下它并且目前是最滿的箱子里。因此，對(duì)于平車裝載問(wèn)題，可以進(jìn)行如下的設(shè)計(jì)：

（1）定義變量和數(shù)組，準(zhǔn)備進(jìn)行裝載；

（2）取出一個(gè)裝備，準(zhǔn)備裝載，若無(wú)裝備了，跳至6；

（3）檢查現(xiàn)平車剩余換長(zhǎng)是否大于等于裝備換長(zhǎng)，如果是跳至4，不是跳至6；

（4）把裝備裝載到現(xiàn)檢查平車上，并把原平車剩余換長(zhǎng)減去裝備換長(zhǎng)的值賦于X；

（5）比較X與最小值S，如果X≥S，則跳至6，否則標(biāo)記當(dāng)前平車為最合適的平車，然后跳至6；

（6）若現(xiàn)檢查平車為最后一輛平車，則將裝備裝載在現(xiàn)最合適的平車上，現(xiàn)最合適平車的剩余換長(zhǎng)等于原剩余換長(zhǎng)減去裝備換長(zhǎng)，然后跳至2；若不是最后一輛平車則，換下一個(gè)平車，跳至3；

（7）裝載結(jié)束。

4.2 首先適應(yīng)（First Fit，F(xiàn)F）算法

FF策略是把下一個(gè)物品放入第一個(gè)可以裝下它的箱子里，F(xiàn)F策略可以描述為:

（1）第一個(gè)物品(S1≤1)放到第一個(gè)空箱子B1中(used(1)=0)。

（2）下一個(gè)物品，(Si≤1)放到Bj中，其中Bj滿足:

（3）如果i＜n，轉(zhuǎn)到第二步，否則停止。

例如，n=10，S=(0.4，0.2，0.7，0.3，0.5，0.4，0.4，0.3，0.6，0.2)。采用FF策略設(shè)計(jì)出的近似算法，其裝箱結(jié)果如圖2所示。

由圖2可見(jiàn)，F(xiàn)F策略的結(jié)果比BF策略多占用一個(gè)箱子，但算法執(zhí)行過(guò)程比前者簡(jiǎn)單。

First Fit算法的中心思想是把物品裝入到第一個(gè)可以裝下的箱子。因此，對(duì)于平車裝載問(wèn)題，可以進(jìn)行如下的設(shè)計(jì)：

圖2 FF算法裝箱結(jié)果

（1）定義變量和數(shù)組，準(zhǔn)備進(jìn)行裝載；

（2）取出一個(gè)裝備，準(zhǔn)備裝載，若無(wú)裝備了，跳至6；

（3）檢查現(xiàn)平車剩余換長(zhǎng)是否大于等于裝備換長(zhǎng)，如果是跳至4，不是跳至5；

（4）把裝備裝載到現(xiàn)檢查平車上，并把原平車剩余換長(zhǎng)減去裝備換長(zhǎng)的值賦于現(xiàn)平車裝備換長(zhǎng)，并跳至2；

（5）換下一個(gè)平車，跳至3；

（6）裝載結(jié)束。

4.3 當(dāng)前適應(yīng)（Next Fit，NF）算法

在NF策略中，下一個(gè)物品的裝入只考慮當(dāng)前的箱子或下一個(gè)箱子，這種方法對(duì)于所有箱子序列只進(jìn)行一趟掃描。算法過(guò)程描述如下：

（1）i=1,j=1；

（3）如果i＜n，轉(zhuǎn)到第二步，否則停止。

NF算法可能會(huì)占用較多箱子，但算法最為簡(jiǎn)單。例如，n=10，S=(0.4,0.2，0.7,0.3,0.5,0.4,0.4,0.3,0.6,0.2)。采用NF策略設(shè)計(jì)出的近似算法，其裝箱結(jié)果如圖3所示。

圖3 NF算法裝箱結(jié)果

Next Fit算法的中心思想是物品的裝入只考慮當(dāng)前的箱子或下一個(gè)箱子。因此，對(duì)于平車裝載問(wèn)題，可以進(jìn)行如下的設(shè)計(jì)：

（1）定義變量和數(shù)組，準(zhǔn)備進(jìn)行裝載；

（2）取出一個(gè)裝備，準(zhǔn)備裝載，若無(wú)裝備了，跳至6；

（3）檢查現(xiàn)平車剩余換長(zhǎng)是否大于等于裝備換長(zhǎng)，如果是跳至4，不是跳至5；

（4）把裝備裝載到現(xiàn)檢查平車上，并把原平車剩余換長(zhǎng)減去裝備換長(zhǎng)的值賦于現(xiàn)平車裝備換長(zhǎng)；

（5）換下一個(gè)平車，跳至4；

（6）裝載結(jié)束。

5 三種算法的綜合比較分析

利用平車裝載算法演示軟件得到的結(jié)果見(jiàn)表1。

表1 平車裝載算法演示軟件結(jié)果

由圖4可以看出，在相同數(shù)量和類型的裝備的情況下，使用First Fit算法和Best Fit算法所用車數(shù)較少。

根據(jù)上一部分的數(shù)據(jù)，可以看出First Fit算法和Best Fit算法的結(jié)果都比較優(yōu)秀。但是根據(jù)Best Fit算法的思路，最后得出的結(jié)果的平車所有未占用的換長(zhǎng)之和是最小的，比較適合鐵路平車輸送的目標(biāo)—用最少的平車裝載最多的裝備。

圖4 算法綜合比較

6 結(jié)論與展望

本文首先根據(jù)鐵路軍事運(yùn)輸?shù)囊?，分析了建立鐵路平車裝載問(wèn)題模型的必要性和可行性，在此基礎(chǔ)上初步建立了鐵路平車裝載模型，對(duì)建模所需的算法進(jìn)行了設(shè)計(jì)，并對(duì)模型建立時(shí)采用的一些算法進(jìn)行了分析，有以下結(jié)論：（1）建立鐵路平車裝載問(wèn)題的模型是必要的，也是可行的；（2）在鐵路平車裝載問(wèn)題模型的研究過(guò)程中，BF算法、FF算法、NF算法可以得到很好的應(yīng)用；（3）經(jīng)過(guò)初步的研究，BF算法比較適合用來(lái)解決平車裝載問(wèn)題。

[1]井祥鶴,周獻(xiàn)中,徐延勇,等.鐵路輸送中平車裝載問(wèn)題的模型與算法[J].計(jì)算機(jī)工程,2006,(9).

[2]井祥鶴,周獻(xiàn)中,徐延勇,多型號(hào)平車裝載問(wèn)題的混合遺傳算法[J].鐵道學(xué)報(bào),2006,(12).

[3]劉輝.裝箱問(wèn)題的概率近似算法[J].科學(xué)技術(shù)與工程,2007, (13).

Model and A lgorithm for Railway Flat Wagon Loading Problem

Liu Hongwei
(Military Transportation Academy,Tianjin 300161,China)

In this paper,in view of the flat wagon loading problem in railway military transportation which we demonstrated could be abstracted into a one-dimension packing problem,we built the corresponding mathematical model,employed respectively the Best Fit approximation algorithm,First Fit approximation algorithm and Next Fit approximation algorithm to solve the model and at the end,analyzed the resultyielded.

flatwagon loading;algorithm;optimization

U294.1;O141.4

A

1005-152X(2017)04-0108-04

2017-03-04

劉宏偉，男，江蘇南通人，研究方向：軍事交通指揮與工程。

doi∶10.3969/j.issn.1005-152X.2017.04.025