Algorithms for very large scale Set Covering Problems.

摘要

The Set Covering Problem (SCP) is a classical combinatorial problem used to model a wide range of applications such as airline and railway crew scheduling, political districting, and truck routing, just to cite a few. The problem is NP-Hard and therefore heuristic algorithms have been developed to solve large scale instances.;This research presents a new one-pass constructive heuristic based on surrogate constraint normalization to rapidly generate a feasible solution after a single sweep through the data of the SCP. The proposed heuristic has been demonstrated to perform better than the most effective one-pass constructive heuristics for the solution of the SCP which is chiefly represented by the widely-used Chvatal method.;An extensive implementation of Lagrangian and Surrogate relaxation is also presented and subjected to computational testing. It is shown that surrogate relaxation, as well as Lagrangian relaxation, provides valuable information to generate core problems.;A new heuristic based upon combining mathematical relaxation and Tabu search is developed in this research as a form of the Relaxation Adaptive Memory Programming (RAMP) approach (Rego, 2005). It is observed that this RAMP algorithm is fast and provides high quality results for the available benchmark problems.;A Scatter Search stand alone algorithm for the SCP was developed as a mean to create a Primal-Dual RAMP approach (Rego, 2005).;Furthermore, this research includes a new deterministic algorithm based upon a Primal-Dual RAMP approach; which uses Surrogate relaxation and Tabu search on the dual side, and Scatter Search and Tabu search on the primal side. This algorithm was able to obtain all the best known solutions for all the benchmark problems, and improved one of the best known solutions for one of the largest problems. The computational times were smaller than the state of the art algorithms reported in the literature; they confirm the efficiency of the Primal-Dual RAMP framework, and suggest the development of more advanced RAMP approaches.