Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
A MILP-based heuristic for a commercial train timetabling problem
RISE - Research Institutes of Sweden, ICT, SICS.ORCID iD: 0000-0003-4456-9453
RISE - Research Institutes of Sweden, ICT, SICS.ORCID iD: 0000-0002-0236-783x
Linköping University, Sweden.
2017 (English)In: Transp. Res. Procedia, 2017, p. 569-576Conference paper, Published paper (Refereed)
Abstract [en]

Using mathematical methods to support the yearly timetable planning process has many advantages. Unfortunately, the train timetabling problem for large geographical areas and many trains is intractable for optimization models alone. In this paper, we therefore present a MILP-based heuristic that has been designed to generate good-enough timetables for large geographical areas and many trains. In the incremental fix and release heuristic (IFRH), trains are added to the timetable in batches. For each batch of trains, a reduced timetable problem is solved using a mathematical integer program and CPLEX. Based on the solution, the binary variables defining meeting locations and stops are fixed, and the next batch of trains is added to the timetable. If previously fixed variables make the problem infeasible, a recovery algorithm iteratively releases fixed variables to regain feasibility. The paper also introduces a simple improvement heuristic (IH) that uses the same idea of working with batches of trains. The heuristics are tested on a real case-study from Sweden consisting of both small problem instances (approximately 300 trains and 1400 possible interactions) and large problem instances (approximately 600 trains and 5500 possible interactions). IFRH returns a feasible timetable within 30 minutes for all problem instances, and after running IH the optimality gaps are less than 5%. Meanwhile, if CPLEX is used without the heuristic framework to solve the total optimization problem, a feasible timetable is not returned within 2 hours for the large problem instances. © 2017 The Authors.

Place, publisher, year, edition, pages
2017. p. 569-576
Keywords [en]
heuristic, MILP, optimization, Train timetabling
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:ri:diva-33204DOI: 10.1016/j.trpro.2017.12.118Scopus ID: 2-s2.0-85039939622OAI: oai:DiVA.org:ri-33204DiVA, id: diva2:1179231
Conference
Transportation Research Procedia
Available from: 2018-01-31 Created: 2018-01-31 Last updated: 2023-06-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gestrelius, SaraAronsson, Martin

Search in DiVA

By author/editor
Gestrelius, SaraAronsson, Martin
By organisation
SICS
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 53 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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