宅配服務下雙門三維貨櫃裝載問題之研究

Abstract

對電子商務產業而言，宅配服務是最重要的成本驅動因子之一，也是影響一家電子商務公司是否經營成功或失敗的關鍵因素之一，本篇論文所探討研究主題為宅配服務下雙門三維度貨櫃裝載問題(Two-Door Three-dimensional container packing problem under home delivery; 3DCPP under home delivery)，此問題屬於三維度容器裝載問題(Three-dimensional container packing problem; 3DCPP)在現實生活中的一種應用。3DCPP是將一定數量的長方型物品或是箱子垂直完整地裝載到一個可堆疊的三維度長方形容器中，我們希望所有物品裝載完畢後可以使得裝載空間使用率達到最大，而宅配服務下3DCPP是假設送貨路徑也就是卸貨順序事前給定情況下將一定數量已裝箱好顧客上網所訂購產品裝載至三維度的宅配車櫃中，希望所有的產品裝載完畢後除了能最大化的使用宅配車櫃的裝載空間之外，在卸載產品時也能達到「零卸貨成本」，所謂「零卸貨成本」就是卸載產品時不會發生重複卸載並再次裝載其他不相關產品的情形。近幾年宅配車櫃的外型已逐漸由單門車櫃造型演進到雙門車櫃造型，然而過去有關宅配服務下三維度貨櫃裝載問題的研究都是只考慮貨品裝載在單門貨櫃的情形下討論，因此本研究想針對過去沒有討論過的宅配服務下「雙門」三維度貨櫃裝載問題做一個研究探討。本篇論文延伸貨品裝載在單門車櫃情形下的看不到(invisible)以及摸不到(untouchable)這兩個規則來精確的定義貨品裝載在雙門車櫃情況下有關卸貨成本的判斷計算，並以子空間法為基礎的來設計我們研究問題的演算法，其中在子空間的刪除行為上，我們提出了16種切割子空間的方法，使得我們的演算法能夠比單門貨櫃裝載問題演算法切割出更多的子空間來裝載更多的貨品，最後實驗比較會發現我們的演算法確實會優於過往宅配服務下單門貨櫃裝載問題演算法，除了大幅度的提升裝載空間使用率外，也更加符合現實生活有關宅配服務裝載行為的應用。

關鍵詞: 宅配服務、容器裝載問題、運輸、物流

Abstract Home delivery services is not only a key a driver of the e-commerce industry, but also a critical factor that determines the success or failure of an e-commerce business. This research paper investigates the application of Two-Door Three-dimensional container packing problem under home delivery (3DCPP under home delivery), itself a Three-dimensional container packing problem (3DCPP) problem, in solving real world problems. 3DCPP refers to the maximization of the packed volume when loading a subset of a given set of rectangular boxes into a rectangular container. In the context of home delivery services, online boxed orders are packed into the three dimensional cargo space of a delivery truck in a manner that satisfies the Zero Unload Cost Constraint while utilizing the maximum amount of available cargo space when the delivery route and hence the delivery drop-off sequence have already been predetermined. The Zero Unload Cost Constraint prohibits the unloading and subsequent reloading of boxes during the delivery drop-off process. In recent years, side cargo doors have been installed on delivery trucks in addition to the rear cargo door that results in two cargo doors. Yet, prior research of Three-dimensional container packing problem under home delivery (3DCPP under home delivery) only takes consider cases involving single cargo doors. Therefore this research focuses on the investigation of Two-Door Three-dimensional container packing problem under home delivery. This research extends the invisible and untouchable constraints from the One-Door Three-dimensional container packing problem to accurately define the calculation of costs in the Two-Door Three-dimensional container packing problem. The subspace method is used as a foundation to design the algorithms used in this research problem. In respect to the subspace deletion method, we propose 16 deletion and subdivision methods for subspaces that result in more subspaces to achieve higher levels of cargo space utilization. Last, a comparative experiment determined our algorithm will be better than preexisting algorithms for Three-dimensional container packing problem under home delivery. We have not only greatly increased the level of cargo space utilization, but also developed algorithms that better reflect the realities of loading and delivery drop-off processes for home delivery services.

Keywords: home delivery, container packing problem, transportation, logistics