A Lagrangian-based heuristic for large-scale set covering problems

被引：102

作者：

Ceria, S ^{[1
]}

Nobili, P

Sassano, A

机构：

[1] Columbia Univ, Grad Sch Business, New York, NY 10027 USA

[2] CNR, Ist Anal Sistemi & Informat, I-00185 Rome, Italy

[3] Univ La Sapienza, Dipartimento Informat & Sistemist, I-00185 Rome, Italy

来源：

MATHEMATICAL PROGRAMMING | 1998年 / 81卷 / 02期

关键词：

set covering; crew scheduling; primal-dual Lagrangian; subgradient algorithms; 0-1; programming; approximate solutions; railways;

D O I：

10.1007/BF01581106

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present a new Lagrangian-based heuristic for solving large-scale set-covering problems arising from crew-scheduling at the Italian Railways (Ferrovie dello Stato). Our heuristic obtained impressive results when compared to state-of-the-art codes on a test-bed provided by the company, which includes instances with sizes ranging from 50,000 variables and 500 constraints to 1,000,000 variables and 5000 constraints. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

引用

页码：215 / 228

页数：14

共 15 条

[1] RECENT ADVANCES IN CREW-PAIRING OPTIMIZATION AT AMERICAN-AIRLINES [J].

ANBIL, R ;

GELMAN, E ;

PATTY, B ;

TANGA, R .

INTERFACES, 1991, 21 (01) :62-74

[2]

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

[3]

BALAS E, 1992, IN PRESS OPERATIONS

[4]

BARUTT J, 1990, SIAM NEWS, V23, P1

[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]

BEASLEY JE, 1994, GENETIC ALGORITHM SE

[8]

BORNEMANN DR, 1982, AGIFORS CRW MAN STUD

[9]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[10] A PROBABILISTIC HEURISTIC FOR A COMPUTATIONALLY DIFFICULT SET COVERING PROBLEM [J].

FEO, TA ;

RESENDE, MGC .

OPERATIONS RESEARCH LETTERS, 1989, 8 (02) :67-71

← 1 2 →