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

Direktlänk
Referera
Referensformat
  • apa
  • 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
Periodic Metro Scheduling
National Technical University of Athens.
2006 (Engelska)Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We introduce the { extsc{Periodic Metro Sched-ul-ing}} ({ extsc{PMS}}) problem, which aims in generating a periodic timetable for a given set of routes and a given time period, in such a way that the minimum time distance between any two successive trains that pass from the same point of the network is maximized. This can be particularly useful in cases where trains use the same rail segment quite often, as happens in metropolitan rail networks. We present exact algorithms for ({ extsc{PMS}}) in chain and spider networks, and constant ratio approximation algorithms for ring networks and for a special class of tree networks. Some of our algorithms are based on a reduction to the { extsc{Path Coloring}} problem, while others rely on techniques specially designed for the new problem.

Ort, förlag, år, upplaga, sidor
2006.
Nyckelord [en]
Train scheduling, path coloring, delay-tolerant scheduling, periodic timetabling
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:kth:diva-58594DOI: 10.4230/OASIcs.ATMOS.2006.684OAI: oai:DiVA.org:kth-58594DiVA, id: diva2:473396
Konferens
6th Workshop on Algorithmic Methods and Models for Optimization of Railways, (ATMOS'06)
Anmärkning

QC 20120117

Tillgänglig från: 2012-01-05 Skapad: 2012-01-05 Senast uppdaterad: 2022-06-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltexthttp://drops.dagstuhl.de/opus/volltexte/2006/684/pdf/06002.BampasEvangelos.Paper.684.pdf

Sök vidare i DiVA

Av författaren/redaktören
Lampis, Michael
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • 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