Railway line planning with minimal passenger stops
by
Amie Albrecht
University of South Australia
Coauthors: Phil Howlett

The line planning problem (LPP) is crucial to the strategic design of passenger train services. The travel demand is defined by an origin-destination (OD) matrix which summarises the number of people who wish to travel between each pair of stations. The problem is to find, for a given OD matrix, set of train stopping patterns and train capacities, the number of services of each allowable pattern that best meets the demand. We consider a version of the LPP in which the objective is to minimise the number of unnecessary stops for passengers on a linear network.

In this presentation we describe fundamental results that define the concept of a maximal OD matrix which can be decomposed exactly into a sum of multiples of more elementary demand matrices. We use this insight to develop an analytic solution technique to solve this version of the LPP when there are no restrictions on the available stopping patterns. If there are restrictions, we currently use a mixed integer programming (MIP) solution technique (as is common in the literature). However, an analysis of small examples suggests an analytic solution procedure may also be possible, which would obviate the need for an MIP. We provide details of this approach. We illustrate our techniques with examples.

Date received: December 10, 2009