National Transport Library Research Database

Optimering och tidtabelläggning. Förstudie (Optimization and timetabling. Feasibility study)

  • Nilsson, Jan-Eric
  • Statens väg- och transportforskningsinstitut (VTI), Statligt forskningsinstitut, 202100-0704
Sponsors, duration, budget: Trafikverket ; 2014-09-30 -- 2015-06-30 Registration number:
  • Trafikverket 2014/99289
Subject(s): Abstract: Sedan 20-talet år har frågan om att etablera en samhällsekonomiskt effektiv fördelning av tåglägen diskuterats. För att etablera en sådan lösning måste två utmaningar kunna hanteras. Den ena, optimeringsproblemet, består i att hitta lösningen på ett NP-komplett optimeringsproblem medan den andra, värderingsproblemet, innebär att få tillgång till information om värdet av de tåglägen de olika operatörerna efterfrågar. Det kan finnas flera tillvägagångssätt för att hitta lösningar som mer eller mindre väl hanterar värderingsproblemet. Oavsett vilken sådan lösning som väljs kan den inte implementeras med mindre än att det saknas lösningar till det andra problemet: Eftersom det idag saknas algoritmer som kan identifiera lösningar till järnvägens komplexa tidtabelläggningsproblem kommer inte ens en ”korrekt” uppsättning värden att kunna verkställas. För cirka femton år sedan genomfördes ett projekt med syfte att för en avgränsad del av det svenska järnvägsnätet utveckla en algoritm av denna art, sedermera publicerad som Brännlund et al (1998). De lösningar som prövades fungerade väl för det begränsade problem som studerades, men förutsättningarna för att tillämpa lösningen på ett större nätverk fanns inte. Sedan dess har utvecklingen gått snabbt i åtminstone två avseenden. Dels har förmågan att hantera den aktuella typen av optimeringsproblem förbättrats, och det finns ett antal forskningsuppsatser som kan ge uppslag till nya lösningar. Dessutom har datorkapaciteten för att hantera också mycket stora och komplexa frågor utvecklats på ett dramatiskt sätt. Syftet med denna förstudie är att inventera den aktuella litteraturen inom det aktuella området och med detta som utgångspunkt identifiera vilka möjligheter som finns att inom ramen för en huvudstudie ta fram en praktiskt fungerande optimeringsalgoritm. Om detta visar sig möjligt avslutas uppdraget med en skiss till beskrivning av en sådan huvudstudie. Arbetet genomförs i en grupp som dels består av två av medförfattarna till den ursprungliga studien, dels av ytterligare två personer som både har djup optimeringskunskap och dessutom är väl förtrogna med den information och de system som finns hos Trafikverket och som kan stödja en framtida utveckling. I gruppen ingår dessutom en företagare med omfattande erfarenhet av att utveckla system som hanterar stora informationsmängder. Brännlund, U., P.O. Lindberg, J-E. Nilsson, A. Nöu (1998). Railway Timetabling Using Lagrangian Relaxation. Transportation Science, Vol. 32, No. 4, November 1998.Abstract: Since the 20's years, the issue of establishing an economically efficient allocation of train paths discussed. To establish such a solution must be two challenges to be handled. One, the optimization problem consists in finding the solution to an NP-complete optimization problems, while the second, the valuation problem, means of access to information about the value of the paths the various operators are asking for. There could be several approaches to find solutions more or less well handles valuation problem. Whatever such a solution is adopted, it can not be implemented unless there is no solution to the second problem: Since there are currently no algorithms that can identify solutions to complex railway tidtabelläggningsproblem will not even have a "correct" set of values to be enforced. For about fifteen years ago, a project was implemented with the aim of a defined part of the Swedish railway network to develop an algorithm of this species, later published as Brännlund et al (1998). The solutions that were tested worked well for the small problems that were studied, but the conditions for applying the solution to a larger network was not. Since then things have moved fast in at least two respects. Second, the ability to handle the type of optimization problems improved, and there are a number of research papers that can provide ideas for new solutions. In addition, the computer capacity to handle also very large and complex issues evolved dramatically. The purpose of this study is to take stock of the current literature in the relevant field and with this as a starting point to identify the opportunities available as part of one main produce an operational optimization algorithm. If this proves possible, the mission ends with an outline description of such a main study. The work is done in a group, which combines two of the co-authors of the original study, and by a further two people who both have deep optimization knowledge and is also well acquainted with the information and the systems that are available from the Transport Administration and that can support future development. The group also includes a business owner with extensive experience in developing systems that manage large amounts of information. Brännlund, U., P. O. Lindberg, J-E. Nilsson, A. Nöu (1998). Railway Timetabling Using Lagrangian Relaxation. Transportation Science, Vol. 32, No. 4, November 1998.
Item type: