集装优化

维基百科,自由的百科全书
跳转至: 导航搜索

集装优化,又名裝箱問題是一個利用運籌學去解決實際生活的的經典問題。簡單來說,就是把大量小盒子裝進大箱子並"塞滿滿"的學問。但現實中要如何才能裝得多又快? 而物體的重量、性質、保存條件等都不相同,加上取出的順序要能有效提高速度,又不會使運輸工具失去重心,因此集裝優化在效率至上運輸界中是十分重要的。

傳統上,數學家開發的演算法是啟發式演算法,也就是基於一些準則,比如兩個小箱子一樣寬,將把寬的一邊對齊,這樣的好處是算得快,缺點是很多可能性(或者叫可行解)根本就沒有去搜索到。在應用上,工人們會憑藉經驗估計,但是難以估計準,也給運輸計劃的制定帶來困難。

拓撲學亦可用於解決這個問題。我們可以把集裝箱內擺放座向不同的小箱子視為一個點,把這些點之間的關係記錄為一個個不同的拓撲結構。利用電腦的幫助,計算不同的拓撲結構下的可能裝箱方案,然後得出裝得多的方案,使集裝箱的空間利用率得以提高。

參考[编辑]

  • Yue, Minyi, A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm//A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, 1991-10, 7 (4): 321–331, doi:10.1007/BF02009683, ISSN 0168-9673 

參看[编辑]