鐵路平車裝載問題模型及算法

劉宏偉（軍事交通學院，天津 300161）

鐵路平車裝載問題模型及算法

劉宏偉
（軍事交通學院，天津 300161）

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

平車裝載；算法；優化

1 引言

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

2 主要研究方法和技術路線

鐵路軍事運輸平車裝載主要考慮兩個因素：平車和裝備。平車方面主要考慮的有：平車的長度、寬度，平車的載重量。裝備方面主要考慮的有：裝備的長、寬、高，裝備的重量，裝備是否超限等。本文在建立模型時，對相關因素進行了簡化，只考慮最主要的因素即:平車的長度和裝備的長度。綜合平車和裝備中要考慮的各個因素，聯系數學建模理論，建立模型,并對模型進行分析優化，再使用計算機多種近似算法對其進行計算，得出結論，并對結論進行比較分析。

3 鐵路平車裝載問題模型

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

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

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

4 算法分析與設計

鐵路平車裝載問題實際上可以看作是一個裝箱問題，它們在本質上是一致的，就是都是研究裝載同樣多的貨物，怎樣裝載能使用最少的平車或箱子。

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

大多數裝箱問題的近似算法采用貪心策略，即把為了求優化結果進行的總體規劃簡化為每一步驟的“貪心”處理，即為每次物品裝箱規定一種局部選擇方法，不同的貪心選擇方法產生不同的策略。由于實踐中裝箱問題的輸入長度n較大，近似算法的時間代價與解 的優化程度之間的權衡是很受重視的。下面介紹三種不同的局部優化策略。

4.1 最佳適應（Best Fit，BF）算法

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

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

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

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

（3）如果i＜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策略設計出的近似算法，其裝箱結果如圖1所示。

圖1 BF算法裝箱結果

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

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

（1）定義變量和數組，準備進行裝載；

（2）取出一個裝備，準備裝載，若無裝備了，跳至6；

（3）檢查現平車剩余換長是否大于等于裝備換長，如果是跳至4，不是跳至6；

（4）把裝備裝載到現檢查平車上，并把原平車剩余換長減去裝備換長的值賦于X；

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

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

（7）裝載結束。

4.2 首先適應（First Fit，FF）算法

FF策略是把下一個物品放入第一個可以裝下它的箱子里，FF策略可以描述為:

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

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

（3）如果i＜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策略設計出的近似算法，其裝箱結果如圖2所示。

由圖2可見，FF策略的結果比BF策略多占用一個箱子，但算法執行過程比前者簡單。

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

圖2 FF算法裝箱結果

（1）定義變量和數組，準備進行裝載；

（2）取出一個裝備，準備裝載，若無裝備了，跳至6；

（3）檢查現平車剩余換長是否大于等于裝備換長，如果是跳至4，不是跳至5；

（4）把裝備裝載到現檢查平車上，并把原平車剩余換長減去裝備換長的值賦于現平車裝備換長，并跳至2；

（5）換下一個平車，跳至3；

（6）裝載結束。

4.3 當前適應（Next Fit，NF）算法

在NF策略中，下一個物品的裝入只考慮當前的箱子或下一個箱子，這種方法對于所有箱子序列只進行一趟掃描。算法過程描述如下：

（1）i=1,j=1；

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

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

圖3 NF算法裝箱結果

Next Fit算法的中心思想是物品的裝入只考慮當前的箱子或下一個箱子。因此，對于平車裝載問題，可以進行如下的設計：

（1）定義變量和數組，準備進行裝載；

（2）取出一個裝備，準備裝載，若無裝備了，跳至6；

（3）檢查現平車剩余換長是否大于等于裝備換長，如果是跳至4，不是跳至5；

（4）把裝備裝載到現檢查平車上，并把原平車剩余換長減去裝備換長的值賦于現平車裝備換長；

（5）換下一個平車，跳至4；

（6）裝載結束。

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

利用平車裝載算法演示軟件得到的結果見表1。

表1 平車裝載算法演示軟件結果

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

根據上一部分的數據，可以看出First Fit算法和Best Fit算法的結果都比較優秀。但是根據Best Fit算法的思路，最后得出的結果的平車所有未占用的換長之和是最小的，比較適合鐵路平車輸送的目標—用最少的平車裝載最多的裝備。

圖4 算法綜合比較

6 結論與展望

本文首先根據鐵路軍事運輸的要求，分析了建立鐵路平車裝載問題模型的必要性和可行性，在此基礎上初步建立了鐵路平車裝載模型，對建模所需的算法進行了設計，并對模型建立時采用的一些算法進行了分析，有以下結論：（1）建立鐵路平車裝載問題的模型是必要的，也是可行的；（2）在鐵路平車裝載問題模型的研究過程中，BF算法、FF算法、NF算法可以得到很好的應用；（3）經過初步的研究，BF算法比較適合用來解決平車裝載問題。

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

[2]井祥鶴,周獻中,徐延勇,多型號平車裝載問題的混合遺傳算法[J].鐵道學報,2006,(12).

[3]劉輝.裝箱問題的概率近似算法[J].科學技術與工程,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