Genetic Programming Hyper Heuristic With Elitist Mutation for Integrated Order Batching and Picker Routing Problem
针对智能制造中的集成订单分批与拣选员路径问题，提出一种遗传规划超启发式方法，自动演化高效启发式规则，并引入精英变异算子加速进化，实验表明其性能优于人工设计的算法。
Integrated order batching and picker routing (IOBPR) is a complex combinatorial optimization problem in real-world intelligent manufacturing systems. Heuristics are often used for solving such complex scheduling problems. Manually designing scheduling heuristics suffer from two limitations: 1) few problem features can be taken into account and 2) the design process is time consuming. Genetic programming hyper heuristic (GPHH) approaches have been proposed on many scheduling problems to automatically evolve effective heuristics. However, existing GPHH approaches are often problem specific and requires careful design of problem specific terminal sets and evolution operators. The aim of this work is to develop a GPHH approach to evolve heuristics for the IOBPR problem. In particular, we propose a novel terminal set (NT) with three types of terminals, and a GPHH with elitist mutation (GPHH-EM) algorithm. Extensive experiments demonstrate that the heuristics evolved by GPHH-EM can significantly outperform other state-of-the-art competing algorithms designed by human experts. Further analysis indicates that the three types of terminals effectively complement to improve evolved heuristics for decision making. Furthermore, the newly developed elitist mutation operator expedites the evolutionary process for GPHH to find high-quality heuristics.