Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems

摘要

Exact algorithms like column generation, the cutting plane algorithm and Lagrangian relaxation are some of the exact algorithms that can generate near-optimal solutions to combinatorial optimization problems. However, they are found to be inadequate in handling large-scale problems. Tabu search, generic algorithms and simulated annealing are some of the metaheuristic algorithms to solve large scale problems of this type. Metaheuristic is used to guide the search process which is problem-specific where the objective is efficient exploration of search space to reach a near-optimal solution. The study focuses on the set covering problem (SCP) by introducing the cost of subset. The SCP finds the least costly subset such that one element of the set belongs to at least one subset. The NP-hard problems, like the vehicle routing problem (VRP) and the crew pairing problem (CPP), can be reformulated as an SCP and subsequently solved using any of the SCP methodologies. This paper proposes a generic algorithm referred to as MetaOpt that integrates metaheuristic and exact algorithms through a decision support mechanism.