A branch and bound algorithm and iterative reordering strategies for inserting additional trains in real time: a case study in Germany
type: Item
instance of: scholarly article
title: A branch and bound algorithm and iterative reordering strategies for inserting additional trains in real time: a case study in Germany
zbMATH Open document ID: 1394.90415
DOI: 10.1155/2015/289072
author: Yuyan Tan
author: Zhibin Jiang
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: With the aim of supporting the process of adapting railway infrastructure and future traffic needs, we have developed a method to insert additional trains efficiently to an existing timetable without introducing large consecutive delays to scheduled trains. In this work, the problem is characterized as a job-shop scheduling problem. In order to meet the limited time requirement and minimize deviations to the existing timetable, the modification that consists of retiming or reordering trains is implemented if and only if it potentially leads to a better solution. With these issues in mind, the problem of adding train paths is decomposed into two subproblems. One is finding the optimal insertion for a fixed order timetable and the other is reordering trains. The two subproblems are solved iteratively until no improvement is possible within a time limit of computation. An innovative branch and bound algorithm and iterative reordering strategy are proposed to solve this problem in real time. Unoccupied capacities are utilized as primary resources for additional trains and the transfer connections for passengers can be guaranteed in the new timetable. From numerical investigations, the proposed framework and associated techniques are tested and shown to be effective.
Mathematics Subject Classification ID: 90B90
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 6925966
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/289072
OpenAlex ID: W2000475015
Wikidata QID: Q59117872
cites work: Non-cyclic train timetabling and comparability graphs
cites work: A fuzzy optimization model for high-speed railway timetable rescheduling
cites work: Optimization based high-speed railway train rescheduling with speed restriction
cites work: Train stop scheduling in a high-speed rail network by utilizing a two-stage approach
cites work: An optimization to schedule train operations with phase-regular framework for intercity rail lines
cites work: A lower bound for the job insertion problem.
cites work: Feasible insertions in job shop scheduling, short cycles and stable sets
cites work: Feasible job insertions in the multi-processor-task job shop
cites work: A Genetic Algorithm for Railway Scheduling Problems
cites work: Experimental algorithms. 8th international symposium, SEA 2009, Dortmund, Germany, June 4--6, 2009. Proceedings
cites work: Q3585089
Recommended article: A branch and bound algorithm for scheduling trains in a railway network
Recommended article: A heuristic approach to solving the train traffic re-scheduling problem in real time
Recommended article: A Re-optimization Approach for Train Dispatching
Recommended article: Application of an iterative framework for real-time railway rescheduling
Recommended article: An Exact Decomposition Approach for the Real-Time Train Dispatching Problem
Recommended article: Using a general-purpose mixed-integer linear programming solver for the practical solution of real-time train rescheduling
Recommended article: An optimization to schedule train operations with phase-regular framework for intercity rail lines
Recommended article: A multi-objective optimization-simulation approach for real time rescheduling in dense railway systems
Recommended article: Branch-and-bound-based local search heuristics for train timetabling on single-track railway network
description: scientific article; zbMATH DE number 6925966