Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

22.07.2017 | Ausgabe 3/2018

Journal of Scheduling 3/2018

Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem

Zeitschrift:
Journal of Scheduling > Ausgabe 3/2018
Autoren:
Lunce Fu, Maged Dessouky

Abstract

We study the state-dependent shortest path problem and focus on its application to the Single Train Routing Problem consisting of a rail network with only double-track segments, where the objective is to route one train through an empty network as fast as possible. We show that the Single Train Routing Problem is NP-hard. We investigate the solution properties and present sufficient conditions for optimality. Different conditions on the parameters are given to guarantee that certain local route selection is optimal. Then, a dynamic programming heuristic is introduced and conditions when the proposed heuristic can obtain the optimal solution in polynomial time are also discussed. Experimental results show the efficiency of the proposed heuristics for general problem settings.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 3/2018

Journal of Scheduling 3/2018 Zur Ausgabe

Premium Partner

    Bildnachweise