自動倉儲入出庫排程優化問題暨啟發式求解法

Abstract

本研究先定義自動倉儲系統的堆垛機入出庫排程優化問題，再提出經驗引導的啟發式求解法，以及遺傳演算優化求解法，以最短化堆垛機的作業時間。問題是在自動倉儲系統的儲存容量、入庫和出庫任務的存取位置、以及堆垛機的移動參數已知下，安排入、出庫任務執行順序。目標在規劃最佳的作業順序，讓堆垛機執行任務行走的總路徑最短，即執行完所有作任務耗用的時間最短；本問題本質是最短化作業時間的優化問題。本研究除了提出貪婪式經驗引導的啟發式求解法外，也研擬遺傳演算優化法。在遺傳演算法初始解中嘗試加入經驗法則的啟發解引導群體演化求得更佳的解。此外也考慮到演化的效率問題，嘗試在染色體編碼上進行分類，使入庫和出庫任務由不同的染色體代表，進行演化。因此研擬了兩段式染色體編碼法，以兩條染色體組成的機體來代表一個解。經數值範例測試，結果顯示本研究提出的兩段式染色體編碼法能顯著地降低堆垛機運送時間，也較經驗求解法求得更佳的解。為驗證實用性本研究也測試在不同倉儲規模情境下的運送作業時間最小化成果。

In this study, we first define the stacker crane inbound and outbound scheduling optimization problem for the Automated Storage and Retrieval System, and then propose an empirically guided heuristic solution method and a genetic algorithm optimization solution method to minimize the operating time of the stacker crane. The problem is to schedule the inbound and outbound tasks with known storage capacity of the automatic storage system, access locations of inbound and outbound tasks, and movement parameters of the stacker crane. The goal is to plan the optimal sequence of operations so that the stacker cranes can travel the shortest total path of tasks, i.e., the shortest time required to perform all tasks; the problem is essentially an optimization problem of minimizing operation time. In this study, in addition to the greedy experience-led heuristic solution method, the genetic algorithm optimization method is also developed. In the initial solution of the Genetic algorithm, we try to add the empirical law of the heuristic solution to guide the evolution of the group to find a better solution. In addition, considering the efficiency of evolution, we also try to classify the chromosome coding so that the incoming and outgoing tasks are represented by different chromosomes for evolution. Therefore, a two-stage chromosome coding method was developed, in which a solution is represented by an organism composed of two chromosomes. The results of numerical example tests show that the proposed two-stage chromosome coding method can significantly reduce the delivery time of the stacker and obtain better solutions than the empirical solution method. To verify the practicality, the results of minimizing the transportation time under different storage size scenarios were also tested.