Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Analysis of strengths & weaknesses of a MILP model for revising railway traffic timetables
Linköpings universitet, SWE.
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datalogi och datorsystemteknik.
2017 (Engelska)Ingår i: OpenAccess Series in Informatics, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017, Vol. 59, artikel-id 131022Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

A railway timetable is typically planned one year in advance, but may be revised several times prior to the time of operation in order to accommodate on-demand slot requests for inserting additional trains and network maintenance. Revising timetables is a computationally demanding task, given the many dependencies and details to consider. In this paper, we focus on the potential of using optimization-based scheduling approach for revising train timetables during short term planning, from one week to few hours before the actual operation. The approach relies on a MILP (Mixed Integer Linear Program) model which is solved by using the commercial solver Gurobi. In a previous experimental study, the MILP approach was used to revise a significant part of the annual timetable for a sub-network in Southern Sweden to insert additional trains and allocate time slots for urgent maintenance. The results showed that the proposed MILP approach in many cases generates feasible, good solutions rather fast. However, proving optimality was in several cases time-consuming, especially for larger problems. Thus, there is a need to investigate and develop strategies to improve the computational performance. In this paper, we present results from a study, where a number of valid inequalities has been selected and applied to the MILP model with the aim to reduce the computation time. The experimental evaluation of the selected valid inequalities showed that although they can provide a slight improvement with respect to computation time, they are also weakening the LP relaxation of the model.

Ort, förlag, år, upplaga, sidor
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017. Vol. 59, artikel-id 131022
Nyckelord [en]
Boosting methods, Railway, Short term planning, Timetable, Valid inequalities, Railroad transportation, Railroads, Scheduling, Transportation, Boosting method, Valid inequality, Integer programming
Nationell ämneskategori
Systemvetenskap, informationssystem och informatik
Identifikatorer
URN: urn:nbn:se:bth-15477DOI: 10.4230/OASIcs.ATMOS.2017.10Scopus ID: 2-s2.0-85032450178ISBN: 9783959770422 (tryckt)OAI: oai:DiVA.org:bth-15477DiVA, id: diva2:1156118
Konferens
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, (ATMOS), Vienna
Anmärkning

open access

Tillgänglig från: 2017-11-10 Skapad: 2017-11-10 Senast uppdaterad: 2018-01-13Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopusAnalysis of Strengths and Weaknesses of a MILP Model for Revising Railway Traffic Timetables

Personposter BETA

Törnquist Krasemann, Johanna

Sök vidare i DiVA

Av författaren/redaktören
Törnquist Krasemann, Johanna
Av organisationen
Institutionen för datalogi och datorsystemteknik
Systemvetenskap, informationssystem och informatik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 190 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf