Improvement of column generation method for railway crew scheduling problems

Yuki Muroi; Tatsushi Nishi; Masahiro Inuiguchi

doi:10.1541/ieejeiss.130.275

Improvement of column generation method for railway crew scheduling problems

Yuki Muroi, Tatsushi Nishi, Masahiro Inuiguchi

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

The railway crew scheduling problem is to determine the assignment of crews to each traveling task to minimize the number of crews satisfying set covering constraints. Column generation method is often applied to solve railway crew scheduling problems. In this paper, we propose dual inequalities for railway crew scheduling problems to reduce the number of iterations in the column generation method. Three types of dual inequalities are generated from railway timetable data and they are added to the restricted master problem. Computational results show the effectiveness of the proposed method compared with the conventional column generation method.

Original language	English
Pages (from-to)	275-283
Number of pages	9
Journal	IEEJ Transactions on Electronics, Information and Systems
Volume	130
Issue number	2
DOIs	https://doi.org/10.1541/ieejeiss.130.275
Publication status	Published - 2010
Externally published	Yes

Keywords

Column generation
Combinatorial optimization
Dual inequality
Railway crew scheduling
Set covering problem

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1541/ieejeiss.130.275

Cite this

@article{95c6fc32aaae40f8b37bf492fbda1eaa,

title = "Improvement of column generation method for railway crew scheduling problems",

abstract = "The railway crew scheduling problem is to determine the assignment of crews to each traveling task to minimize the number of crews satisfying set covering constraints. Column generation method is often applied to solve railway crew scheduling problems. In this paper, we propose dual inequalities for railway crew scheduling problems to reduce the number of iterations in the column generation method. Three types of dual inequalities are generated from railway timetable data and they are added to the restricted master problem. Computational results show the effectiveness of the proposed method compared with the conventional column generation method.",

keywords = "Column generation, Combinatorial optimization, Dual inequality, Railway crew scheduling, Set covering problem",

author = "Yuki Muroi and Tatsushi Nishi and Masahiro Inuiguchi",

year = "2010",

doi = "10.1541/ieejeiss.130.275",

language = "English",

volume = "130",

pages = "275--283",

journal = "IEEJ Transactions on Electronics, Information and Systems",

issn = "0385-4221",

publisher = "The Institute of Electrical Engineers of Japan",

number = "2",

}

TY - JOUR

T1 - Improvement of column generation method for railway crew scheduling problems

AU - Muroi, Yuki

AU - Nishi, Tatsushi

AU - Inuiguchi, Masahiro

PY - 2010

Y1 - 2010

N2 - The railway crew scheduling problem is to determine the assignment of crews to each traveling task to minimize the number of crews satisfying set covering constraints. Column generation method is often applied to solve railway crew scheduling problems. In this paper, we propose dual inequalities for railway crew scheduling problems to reduce the number of iterations in the column generation method. Three types of dual inequalities are generated from railway timetable data and they are added to the restricted master problem. Computational results show the effectiveness of the proposed method compared with the conventional column generation method.

AB - The railway crew scheduling problem is to determine the assignment of crews to each traveling task to minimize the number of crews satisfying set covering constraints. Column generation method is often applied to solve railway crew scheduling problems. In this paper, we propose dual inequalities for railway crew scheduling problems to reduce the number of iterations in the column generation method. Three types of dual inequalities are generated from railway timetable data and they are added to the restricted master problem. Computational results show the effectiveness of the proposed method compared with the conventional column generation method.

KW - Column generation

KW - Combinatorial optimization

KW - Dual inequality

KW - Railway crew scheduling

KW - Set covering problem

UR - http://www.scopus.com/inward/record.url?scp=77949343909&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77949343909&partnerID=8YFLogxK

U2 - 10.1541/ieejeiss.130.275

DO - 10.1541/ieejeiss.130.275

M3 - Article

AN - SCOPUS:77949343909

SN - 0385-4221

VL - 130

SP - 275

EP - 283

JO - IEEJ Transactions on Electronics, Information and Systems

JF - IEEJ Transactions on Electronics, Information and Systems

IS - 2

ER -

Improvement of column generation method for railway crew scheduling problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this