Group Theoretic Approach to Metaheuristic Local Search for Partitioning Problems

摘要

Recent work has demonstrated the power of combining group theory with metaheuristic search methodologies to solve discrete optimization problems. Group theory provides tools to characterize the underlying structures in move neighborhoods, solution representations and solution landscapes. Exploiting these structures with group theoretic techniques produces highly effective and efficient search algorithms. Discrete optimization problems may be divided into three distinct groups: partitioning, ordering and partitioning- and-ordering problems. Partitioning problems such as set covering, knapsack and min-cut network flow problems have no ordering context and require only that the solution variables be placed into mutually exclusive sets. Ordering problems such as single-agent traveling salesman, single-machine job shop scheduling and single-vehicle routing problems require that a permutation of the solution variables be stipulated. Partitioning-and-ordering problems such as multiple- agent traveling salesmen, multiple-machine job shop scheduling and multiple-vehicle routing problems require that the solution variables be partitioned and ordered within each partition.