利用二元整數規劃求解多卸貨點之三維背包裝載問題

Translated title of the thesis: Binary-Integer Programming for the Three Dimensional Multi-Drop Situations Knapsack Loading Problem
  • 朱 培萱

Student thesis: Master's Thesis

Abstract

三維裝箱問題能有效幫助物流、運輸、製造業等產業管理或解決存貨、運輸、提升空間利用率等問題,在實務上非常有研究意義。本研究探討的問題為三維裝箱問題中的背包裝載問題,問題限制類型為多卸貨點,其實務上之應用為物流配送問題。連鎖門市或宅配的配送方式與一般背包裝載問題?盡相同,主要原因為?鎖門市或宅配在配送時有一定的送貨路程,故有一定的卸貨順序,如果隨意堆疊或未依照順序?放,將造成卸貨時間增加,且?發生搬動失誤。故本研究考量貨物下方支撐率、運輸穩定性,以及卸貨效率,包含卸貨人員在卸貨時之可行性及方便性,以期達到在不需挪移其他卸貨點的貨物之情形下即可完成卸貨。 過去文獻對三維裝箱中的背包裝載問題,大多採用啟發式演算法來求解,優點是可解決規模較大的問題,缺點則是求出的解不一定為最佳解。本研究針對三維背包裝載問題中之一特殊情況限制-多卸貨點問題,提出一個二元整數規劃模式(全排法)進行求解,期望在一容器空間中,找出最大總利潤的?放方式,並在問題規模較大導致二元整數規劃模型無法在限定時間內求出最佳解時,採用斜層排列啟發式演算法(斜排法)進行求解,以期提升貨物運輸穩定性,亦更接近總體最佳解的?貨方式。 本研究先以小問題比較三種演算法-全排法、層排法、斜排法之執行效率及求解品質,發現全排法雖可求得全域最佳解,在問題規模增加時,求解時間遠大於其他兩種方法。在斜排法及層排法比較中可發現,斜排法求解結果更接近全域最佳解,求解時間亦較短。在參數分析中,可以發現不論是當貨物及容器之相對體積增加、箱子種類增加、卸貨點個數減少、箱子數量增加,都會造成執行時間增加,主要原因都是貨物之排列組合方式增加,使迭代運算時間上升。
Date of Award2016 Jun 22
Original languageChinese
SupervisorShiow-Yun Chang (Supervisor)

Cite this

利用二元整數規劃求解多卸貨點之三維背包裝載問題
培萱, 朱. (Author). 2016 Jun 22

Student thesis: Master's Thesis