Algorithms for the Set Covering Problem

被引：14

作者：

Alberto Caprara

Paolo Toth

Matteo Fischetti

机构：

[1] University of Bologna,DEIS

[2] University of Padova,DEI

来源：

Annals of Operations Research | 2000年 / 98卷

关键词：

Important Application; Experimental Comparison; Covering Problem; Main Model; Effective Algorithm;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.

引用

页码：353 / 371

页数：18

共 40 条

[1]

Balas E.(1996)A dynamic subgradient-based branch-and-bound procedure for set covering Operations Research 44 875-890

[2]

Carrera M.C.(1987)An algorithm for set covering problems European Journal of Operational Research 31 85-93

[3]

Beasley J.E.(1990)A Lagrangian heuristic for set covering problems Naval Research Logistics 37 151-164

[4]

Beasley J.E.(1990)OR-Library: Distributing test problems by electronic mail Journal of the Operational Research Society 41 1069-1072

[5]

Beasley J.E.(1996)A genetic algorithm for the set covering problem European Journal of Operational Research 94 392-404

[6]

Beasley J.E.(1992)Enhancing an algorithm for set covering problems European Journal of Operational Research 58 293-300

[7]

Chu P.C.(1999)A morphing procedure to supplement a simulated annealing heuristic for cost-and coverage-correlated weighted set-covering problems Annals of Operations Research 86 611-627

[8]

Beasley J.E.(1999)A heuristic method for the set covering problem Operations Research 47 730-743

[9]

Jörnsten K.(1997)Algorithms for railway crew management Mathematical Programming 79 125-141

[10]

Brusco M.J.(1998)A Lagrangian-based heuristic for large-scale set covering problems Mathematical Programming 81 215-228

← 1 2 3 4 →