A Branch and Bound Algorithm for the Exact Solution of the Problem of EMU Circulation Scheduling in Railway Network

Chao Lu, Lei-shan Zhou, Yi-xiang Yue and Ran Chen

Mathematical Problems in Engineering, 2016, vol. 2016, 1-14

Abstract:

This paper is concerned with the scheduling of Electrical Multiple Units (EMUs) under the condition of their utilization on one sector or within several interacting sectors. Based on the introduction of the train connection graph which describes the possible connection relationship between trains, the integer programming model of EMU circulation planning is constructed. In order to analyzing the resolution of the model, a heuristic which shares the characteristics with the existing methods is introduced first. This method consists of two stages: one is a greedy strategy to construct a feasible circulation plan fragment, and another is to apply a stochastic disturbance to it to generate a whole feasible solution or get a new feasible solution. Then, an exact branch and bound method which is based on graph designing is proposed. Due to the complexity, the lower bound is computed through a polynomial approximation algorithm which is a modification from the one solving the degree constraint minimum 1-tree problem. Then, a branching strategy is designed to cope with the maintenance constraints. Finally, we report extensive computational results on a railway corridor in which the sectors possess the basic feature of railway networks.

Date: 2016
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2016/8537089.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2016/8537089.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:8537089

DOI: 10.1155/2016/8537089

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().