螞蟻演算法應用於駁運式排程問題

Abstract

駁運式排程(Cross-Docking Scheduling)，又稱為越庫作業，其定義是貨物由供應商經過物流中心送至顧客端，貨物不進行儲存於物流中心的一種作業觀念，如此可以減少貨物於物流中心的停留時間而使配送更加快速減少顧客等待時間。在生產製造中，兩階段流線式生產加上其相互關係也可把問題視為駁運式排程問題。由於駁運式排程問題為一排序問題，而螞蟻演算法(Ant Colony Optimization, ACO)在排序問題上的搜尋能力及求解過程相較於其他巨集啟發式演算法具有優勢。因此，本研究採用螞蟻演算法作為求解方法。首先，透過螞蟻演算法產生客戶的指派順序，而此排序只為客戶單一車輛排序。根據此排序再藉由指派法則，進一步排序出供應商與客戶排序。由數值測試可知，本研究之啟發式演算法與文獻中採用強生法則之研究相較，能有效提升求解品質。

The Cross-Docking Scheduling Problem (CDSP) determines the schedule of the inbound (supplier) and outbound (customer) vehicles for a distribution center under the cross-docking operation, in which only sorting and consolidating (but no storage) is involved to improve the customer service by minimizing the time waste. As for the manufacturing industry, the two-staged flowshop scheduling problem with the precedence requirement can be formulated as a CDSP, too. Owing to the nature of the sequencing decision problem associated with the CDSP, this study chooses the Ant Colony Optimization (ACO), which has some inherited advantages over other meta-heuristics due to its sequential framework for the searching process and the solution building procedure. This study designs an ant-based algorithm to generate the outbound sequence under the condition of one single vehicle. Based on this ant-generated sequence, several heuristic steps are used to make the scheduling decision of both inbound and outbound vehicles under the multiple-vehicle situation. In the numerical experiment, the developed algorithm is compared with a solution algorithm based on the classic Johnson’s Rule in the literature. It is found that the developed ant-based algorithm is promising for solving the CDSP.