A genetic algorithm for the set covering problem

被引：25

作者：

AlSultan, KS

Hussain, MF

Nizami, JS

机构：

[1] KING FAHD UNIV PETR & MINERALS, DATA PROC CTR, DHAHRAN 31261, SAUDI ARABIA

[2] KING FAHD UNIV PETR & MINERALS, DEPT MECH ENGN, DHAHRAN 31261, SAUDI ARABIA

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 1996年 / 47卷 / 05期

关键词：

Chvatal's algorithm; genetic algorithm; implicit enumeration; Lagrangian heuristic; NP-complete problem; set-covering problem; 0-1 integer programs;

D O I：

10.1057/jors.1996.82

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, the set covering problem (SCP) is considered. Several algorithms have been suggested in the literature for solving it. We propose a new algorithm for solving the SCP which is based on the genetic technique. This algorithm has been implemented and tested on various standard and randomly generated test problems. Preliminary results are encouraging, and are better than the existing heuristics for the problem.

引用

页码：702 / 709

页数：8

共 25 条

[1]

[Anonymous], 1991, Handbook of genetic algorithms

[2] EFFICIENT HEURISTIC SOLUTIONS TO AN AIRLINE CREW SCHEDULING PROBLEM [J].

BAKER, EK ;

BODIN, LD ;

FINNEGAN, WF ;

PONDER, RJ .

AIIE TRANSACTIONS, 1979, 11 (02) :79-85

[3]

BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886

[4]

Balas E., 1979, Combinatorial optimization, P151

[5]

BEASLEY JE, 1990, NAV RES LOG, V37, P151, DOI 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO

[6]

2-2

[7] ENHANCING AN ALGORITHM FOR SET COVERING PROBLEMS [J].

BEASLEY, JE ;

JORNSTEN, K .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 58 (02) :293-300

[8] AN ALGORITHM FOR SET COVERING PROBLEM [J].

BEASLEY, JE .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1987, 31 (01) :85-93

[9] OR-LIBRARY - DISTRIBUTING TEST PROBLEMS BY ELECTRONIC MAIL [J].

BEASLEY, JE .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1990, 41 (11) :1069-1072

[10] COMPUTATIONAL SURVEY OF METHODS FOR SET COVERING PROBLEM [J].

CHRISTOFIDES, N ;

KORMAN, S .

MANAGEMENT SCIENCE SERIES A-THEORY, 1975, 21 (05) :591-599

← 1 2 3 →