Path based algorithms for metro network design

Gilbert Laporte; Marta M.B. Pascoal

doi:10.1016/j.cor.2015.04.007

Path based algorithms for metro network design

Gilbert Laporte
, Marta M.B. Pascoal

CIRRELT
HEC Montréal
Institute for Systems Engineering and Computers - Coimbra (INESCC)
Universidade de Coimbra

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

36 Citations (SciVal)

Abstract

This paper proposes a practical methodology for the problem of designing a metro configuration under two criteria: population coverage and construction cost. It is assumed that a set of corridors defining a rough a priori geometric configuration is provided by the planners. The proposed algorithm consists of fine tuning the location of single alignments within each corridor. This is achieved by means of a bicriteria methodology that generates sets of non-dominated paths. These alignments are then combined to form a metro network by solving a bicriteria integer linear program. Extensive computational experiments confirm the efficiency of the proposed methodology.

Original language	English
Pages (from-to)	78-94
Number of pages	17
Journal	Computers and Operations Research
Volume	62
DOIs	https://doi.org/10.1016/j.cor.2015.04.007
Publication status	Published - 16 May 2015

Funding

This research was partially funded by the Canadian Natural Sciences and Engineering Research Council under Grant 39682-10 , and by the Portuguese Foundation for Science and Technology under project Grant UID/MULTI/00308/2013 . This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments.

Keywords

Bicriteria optimization
Metro network design
Path based algorithm

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research

Access to Document

10.1016/j.cor.2015.04.007

Cite this

@article{d821e7a61dbd44bf943fc577e7de7078,

title = "Path based algorithms for metro network design",

abstract = "This paper proposes a practical methodology for the problem of designing a metro configuration under two criteria: population coverage and construction cost. It is assumed that a set of corridors defining a rough a priori geometric configuration is provided by the planners. The proposed algorithm consists of fine tuning the location of single alignments within each corridor. This is achieved by means of a bicriteria methodology that generates sets of non-dominated paths. These alignments are then combined to form a metro network by solving a bicriteria integer linear program. Extensive computational experiments confirm the efficiency of the proposed methodology.",

keywords = "Bicriteria optimization, Metro network design, Path based algorithm",

author = "Gilbert Laporte and Pascoal, \{Marta M.B.\}",

year = "2015",

month = may,

day = "16",

doi = "10.1016/j.cor.2015.04.007",

language = "English",

volume = "62",

pages = "78--94",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

}

TY - JOUR

T1 - Path based algorithms for metro network design

AU - Laporte, Gilbert

AU - Pascoal, Marta M.B.

PY - 2015/5/16

Y1 - 2015/5/16

N2 - This paper proposes a practical methodology for the problem of designing a metro configuration under two criteria: population coverage and construction cost. It is assumed that a set of corridors defining a rough a priori geometric configuration is provided by the planners. The proposed algorithm consists of fine tuning the location of single alignments within each corridor. This is achieved by means of a bicriteria methodology that generates sets of non-dominated paths. These alignments are then combined to form a metro network by solving a bicriteria integer linear program. Extensive computational experiments confirm the efficiency of the proposed methodology.

AB - This paper proposes a practical methodology for the problem of designing a metro configuration under two criteria: population coverage and construction cost. It is assumed that a set of corridors defining a rough a priori geometric configuration is provided by the planners. The proposed algorithm consists of fine tuning the location of single alignments within each corridor. This is achieved by means of a bicriteria methodology that generates sets of non-dominated paths. These alignments are then combined to form a metro network by solving a bicriteria integer linear program. Extensive computational experiments confirm the efficiency of the proposed methodology.

KW - Bicriteria optimization

KW - Metro network design

KW - Path based algorithm

UR - https://www.scopus.com/pages/publications/84929377635

U2 - 10.1016/j.cor.2015.04.007

DO - 10.1016/j.cor.2015.04.007

M3 - Article

AN - SCOPUS:84929377635

SN - 0305-0548

VL - 62

SP - 78

EP - 94

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

Path based algorithms for metro network design

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this