liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
SICS RISE AB, Box 1263, SE-164 29 Kista, Sweden.ORCID iD: 0000-0003-4456-9453
SICS RISE AB, Box 1263, SE-164 29 Kista, Sweden.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering. (Trafiksystem, Traffic Systems)ORCID iD: 0000-0001-6880-8549
2017 (English)In: Transportation Research Procedia, 2017, Vol. 27, 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.

Place, publisher, year, edition, pages
2017. Vol. 27, p. 569-576
Keywords [en]
Train timetabling; MILP; optimization; heuristic
National Category
Transport Systems and Logistics
Identifiers
URN: urn:nbn:se:liu:diva-144529DOI: 10.1016/j.trpro.2017.12.118OAI: oai:DiVA.org:liu-144529DiVA, id: diva2:1177554
Conference
20th EURO Working Group on Transportation Meeting, EWGT 2017, 4-6 September 2017, Budapest, Hungary
Funder
Swedish Transport Administration, TRV 2014/5233Available from: 2018-01-25 Created: 2018-01-25 Last updated: 2018-02-01

Open Access in DiVA

fulltext(406 kB)6 downloads
File information
File name FULLTEXT01.pdfFile size 406 kBChecksum SHA-512
49007c192035581e5ef2a48f719a20350620672cc3a4b1b113b77327d4e583b7104781fbd36041dd2ad64150238333aa7a48a2bf8ebcbd82b3bdbcb0669258b3
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Gestrelius, SaraPeterson, Anders
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
Transport Systems and Logistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 6 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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