犧牲空間算法求解平板車裝貨問題

龐小琪

(成都工業(yè)學院 教務處，成都 610031)

“2輛鐵路平板車的裝貨問題”是福特汽車公司一個具體問題的修正與簡化，由佐治亞理工學院的J·Bartholdi［1］提供并作為1988年的美國大學生數(shù)學建模競賽題目。該題是解決7種規(guī)格的包裝箱要裝到2輛鐵路平板車上去的問題。以前對于此問題的討論，大多是應用數(shù)學分析方法，根據(jù)數(shù)據(jù)的一些特殊情況簡化后再進行計算。但分析過程比較復雜，且裝載貨物的情況比較特殊，而犧牲空間算法可以不用復雜的分析過程，一般情況下都能簡單而迅速地求解。

1 問題分析

“2輛鐵路平板車的裝貨問題”即在包裝箱的寬和高相同，但重量和厚度不同，且每種包裝箱的厚度、重量以及數(shù)量為已知的前提下，把7種規(guī)格的包裝箱(Ci表示第i種規(guī)格，具體見表1)裝到2輛平板車上去并使所占的空間最小。如圖1所示，每輛平板車有L m長的地方可用來裝包裝箱，載重為T t。由于當?shù)刎涍\的限制，對C5、C6、C7類的包裝箱的總的長度不能超過M cm。

圖1 平板車裝貨示意圖

表1 7種貨物的數(shù)量及規(guī)格

根據(jù)題目分析:7種包裝箱不可能全部裝到這2輛平板車上去，究竟怎樣把這些包裝箱分配在2輛平板車上，才能使浪費的空間最少?因此需考慮象面包片那樣裝載，問題就可以轉化為怎樣裝載才能使剩余空間最小。從表面上看，該問題是以裝載在2輛平板車上各種包裝箱的數(shù)量為決策變量，以裝載總厚度最大為目標的一個整數(shù)規(guī)劃問題。如果按照優(yōu)化模型的求解過程只能得到1組解，但實際上由于包裝箱堆放的位置不確定，如果只有1組解，很難作為實際裝載方案的參考，必須根據(jù)實際情況選擇不同的裝載方案以使剩余空間最小，所以需要找出多種裝載方案。

2 算法分析

2.1 窮舉法

窮舉法簡單易用、操作簡單，但是對于時間復雜度過大的情況則無法進行計算。本文所涉及的是將7種貨物裝載到2輛平板車上去的問題，由此分析可知，應有14個變量即擁有14重的循環(huán)。

以C1為例，該種貨物在2輛平板車的裝載數(shù)量為0～8，則14重循環(huán)的時間復雜度為(9×8×10×7×7×5×6)2=1.120 2e+012，這顯然是計算機無法承受的。又由題目條件對C5、C6、C7類的包裝箱的總長度不能超過M cm來進一步分析，可以發(fā)現(xiàn)，C1、C2、C3、C4這4種貨物必須全部裝完，從而就剩下10重循環(huán)，時間復雜度為9×8×10×7×(7×5×6)2=1.270 08e+09，雖然計算機勉強能夠運行，但計算速度緩慢。

2.2 啟發(fā)式算法

當窮舉法失效時，很容易想到啟發(fā)式算法。啟發(fā)式算法的優(yōu)點是迭代次數(shù)少、計算迅速［2］，但是該算法尋找的是近似解，不一定能夠找出最優(yōu)解，更不能找出全部的最優(yōu)解。所以對于該問題，要想找出所有平板車裝載的最優(yōu)方案是不可能的。

2.3 犧牲空間算法

算法復雜度分為時間復雜度和空間復雜度。時間復雜度是指度量算法執(zhí)行的時間長短;而空間復雜度是指度量算法所需存儲空間的大小。犧牲空間算法是以犧牲存儲空間為代價，換取較短的算法執(zhí)行時間［3］。

空間復雜度算法表示在計算機存儲器上所占用的存儲空間［3］，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間3個方面。雖然該算法對于時間復雜度較大的情況下可以考慮，但是也應該考慮到如果占用的存儲空間過大，會出現(xiàn)“Out of memory(內(nèi)存超過限制)”的錯誤。對于一個算法，其時間復雜度和空間復雜度往往是相互影響的。當追求一個較好的時間復雜度時，可能會使空間復雜度的性能變差，即可能導致占用較多的存儲空間;反之，當追求一個較好的空間復雜度時，可能會使時間復雜度的性能變差，即可能導致占用較長的運行時間。［5］然而，恰當?shù)貭奚邢薜拇鎯臻g來減少時間復雜度，從而實現(xiàn)對問題的求解是可行的。

為了減少時間復雜度，可以通過犧牲一定的存儲空間來存放滿足條件的裝載方案，再從中尋找最優(yōu)的存儲方案。對于該問題，一輛平板車就只有7個變量即7重循環(huán)。7重循環(huán)的總循環(huán)次數(shù)只有1 058 400，計算機完全能夠承受。但是如果把所有滿足條件的放置在平板車的方案存儲下來，所需存儲空間是非常巨大的。因為要找的是使得剩余空間最小的最優(yōu)解，所以對于裝載貨物很少的方案可以不用考慮，即限定滿足條件方案的總長度在(L－ε，L)之間，其中L是一輛平板車的長度，ε為預計的剩余空間。ε取得太小，就找不到最優(yōu)解;ε取得太大會使存儲空間較大。這里不妨取ε=1，如果能找到最優(yōu)解則不用再調(diào)整了，如果不能找到最優(yōu)解可適當增加ε的值，直到找到最優(yōu)解為止。

然后，把已存儲的方案一一取出進行組合，判斷是否滿足貨物數(shù)量、重量，并進行比較找出剩余空間最少的所有方案。

3 算法實現(xiàn)

對于該問題L=10.20 m，ε=1，ti為第i種貨物的厚度，wi為第i種貨物的質(zhì)量，總質(zhì)量限制為40 t，則算法的具體實現(xiàn)為:

1)找出并存儲滿足條件的裝載方案

設1輛平板車裝載第i種貨物的數(shù)量為xi(i=1，2，…，7)，通過7重循環(huán)找出滿足條件的裝載方案:

①生成候選裝載方案

第1重循環(huán)x1從0到8取值，第2重循環(huán)x2從0到7取值，…，第7重循環(huán)x7從0到8取值，則裝載方案為［x1，x2，x3，x4，x5，x6，x7］;

②存儲滿足條件的方案

從而，可找出852種滿足條件的裝載方案，運行時間不到1 min。

2)把存儲的方案進行兩兩組合，使得各種貨物量不超過限制且剩余空間最小

通過步驟1)存儲的方案是滿足裝載方案的，因為是2輛平板車的裝貨問題，而存儲的裝載方案是在1輛車的裝載方案，則將存儲的裝載方案進行兩兩組合，并判斷各種貨物數(shù)量不超過限制且剩余空間最小這2個條件。即從852種方案每次取2種方案，運算次數(shù)為C2852=362 526，判斷各種貨物數(shù)量不超過限制且剩余空間最小這2個條件，從而可以很快地找出滿足條件的裝載方案。

設裝載方案Xi(i=1，2，…，852)，M為每一種貨物的數(shù)量上限，通過2重循環(huán)找出滿足條件的裝載方案，實現(xiàn)過程如圖3所示。

圖2 尋找滿足1輛車裝載方案的N-S圖

圖3 尋找滿足2輛車裝載方案的N-S圖

最后計算出最優(yōu)的裝載方案有60種，最小剩余空間0.6 cm，總運算次數(shù)1 058 400+362 526=1 420 926。

4 結語

通過犧牲空間算法大大提高了程序的運行時間，并且能夠把所有滿足條件的裝載方案都找出來，不會出現(xiàn)漏解。因為在存儲方案的選擇時去掉的只有不滿足條件或者達不到最優(yōu)解的方案，從而對該問題進行了比較完美的求解。犧牲空間算法不僅對于該問題適用，對于組合、優(yōu)化等類似問題同樣適用。

［1］BARTHOIDI J.The outstanding railroad flatcar papers［J］.The UMAP Journal，1988，9(4):399 －103.

［2］MOTWANI R，RAGHAVAN P.Randomized algorithms［M］.New York:Cambridge University Press，1995.

［3］APPLEBAUM B，SHAIY I，KUSHILEVITZ E.Cryptography in NC0［J］.S IAM Journal of Computing，2006，36(4):845 －888.

［4］石竑松，秦志光.保持空間復雜性的算法組合［J］.計算機應用研究，2010(6):2020－2023.

［5］算法的時間復雜度和空間復雜度［EB/OL］.［2012－12－01］.http://wenku.baidu.com/view/19634f5f804d2b160b4ec049.html