有重疊服務區域之多貨櫃裝載問題

Abstract

物流公司所提供之內陸卡車服務，每輛卡車皆有其負責配送之區域，當空間不足時，卡車之間會互相協助配送位於其鄰近區域之貨物。本研究將可由其他卡車協助區域視為區域間之「重疊服務區域」，位於重疊服務區域之貨物可負責其區域之任一輛卡車進行配送。在過去探討三維貨櫃裝載問題之文獻中，並無提出重疊服務區域之概念，故本研究提出「有重疊服務區域之多貨櫃裝載問題」，旨在探討如何將分屬不同服務區域且區域有重疊情形之長方體貨物正交裝載於多個長方體貨櫃內，使總貨櫃之空間使用率最大化。期望透過有效利用貨櫃之剩餘空間，來減少貨櫃之使用次數及委外幫忙載運之情形，達到降低整體運輸成本之目的。 本研究選擇以基因演算法求得近似最佳解，並結合子空間法作為解碼之機制，提出「基於子空間之基因演算法」(Subvolume-based GA)求解問題。演算法中之每條染色體由三部分編碼所組成，分別為貨物裝載順序、貨物擺放方向及重疊服務區域貨物分配，三段編碼分開進行交配及突變後再重新組合成一條染色體進行解碼，透過此方式能確保染色體之可行性。染色體透過子空間法將貨物堆疊至貨櫃中後產出裝載計畫(loading plan)。除此之外，本研究亦透過染色體編碼之順序來滿足多卸貨點限制之要求。最後，透過業界提供之真實數據進行實驗案例及分析，驗證加入重疊服務區域之設計確能提升貨櫃之空間使用率。

Logistics companies provide the inland truck service to customers, and each truck has its service region. When the loading space is insufficient, trucks will help each other to load the cargos in its adjacent areas. We consider the regions that can be assisted by other trucks as “overlapping service regions”, and the cargos, which belong to the overlapping service regions can be packed by any truck which serves the region. Therefore, this study proposes a “Multiple Containers Loading Problem with Overlapping Service Regions”. It is con-cerned how to packing a number of rectangular cargos orthogonally onto multiple rectan-gular container so that the utilization rate of the container space is maximized, and it is expected to reduce the overall transportation cost by effectively utilizing the remaining space of the containers. We choose the genetic algorithm to find the near optimum solution and combine with the sub-volume approach as the method of decoding. We develop a “Subvolume-based GA” to solve the problem and determine the loading pattern. In particular, the proposed ap-proach integrates the encoding based on cargo priority, cargo orientation type and the dis-tribution variables of the cargos in the overlapping service regions. It also meets the re-quirements of multi-drop constraint by encoding the order of the genes. At last, our ex-perimental results suggest our approach to be promising.