Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Railway Timetabling Using Lagrangian Relaxation
KTH.
Linköping University.ORCID iD: 0000-0002-0258-7218
KTH.
Banverket.ORCID iD: 0000-0002-5814-917X
1998 (English)In: Transportation Science, ISSN 0041-1655, E-ISSN 1526-5447, Vol. 32, no 4, 358-369 p.Article in journal (Refereed) Published
Abstract [en]

We present a novel optimization approach for the timetabling problem of a railway company, i.e., scheduling of a set of trains to obtain a profit maximizing timetable, while not violating track capacity constraints. The scheduling decisions are based on estimates of the value of running different types of service at specified times. We model the problem as a very large integer programming problem. The model is flexible in that if allows for general cost functions. We have used a Lagrangian relaxation solution approach, in which the track capacity constraints are relaxed and assigned prices, so that the problem separates into one dynamic program for each physical train. The number of dual variables is very large. However, it turns out that only a small fraction of these are nonzero, wh ich one may take advantage of in the dual updating schemes. The approach has been, tested on a realistic example suggested by the Swedish National Railway Administration. This example contains 18 passenger trains and 8 freight trains to be scheduled during a day on a stretch of single track, consisting of 17 stations. The computation times are rather modest and the obtained timetables are within a few percent of optimality.

Place, publisher, year, edition, pages
1998. Vol. 32, no 4, 358-369 p.
Keyword [en]
Optimization, Mathematical model, Timetable, Rail bound transport
National Category
Mathematical Analysis
Research subject
Railway: General works, surveys, comprehensive works, Railway: Passenger transport
Identifiers
URN: urn:nbn:se:vti:diva-320DOI: 10.1287/trsc.32.4.358ISI: 000077142100004OAI: oai:DiVA.org:vti-320DiVA: diva2:666028
Available from: 2013-11-21 Created: 2013-11-21 Last updated: 2016-02-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lindberg, Per OlovNilsson, Jan-Eric
In the same journal
Transportation Science
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 123 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf