Path based algorithms for metro network design. (October 2015)

• Record Type: Journal Article
• Authors: Laporte, Gilbert; Pascoal, Marta M.B.
• Is Part Of: Computers & operations research. Volume 62(2015)
• Page Start: 78
• Page End: 94
• Publication Date: 2015-10
• Subjects: Metro network design -- Path based algorithm -- Bicriteria optimization; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.04.007
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Abstract : Highlights: We propose a flexible and modular heuristic for the planning of metro networks. Two criteria are optimized jointly: population coverage and construction cost. Non-dominated lines are generated within corridors specified by the planners. These lines are then assembled into a network through mathematical programming. The algorithm is intuitive, flexible and computationally efficient.