A disjunctive graph model and framework for constructing new train schedules

作者：Burdett R L; Kozan E^*

来源：European Journal of Operational Research, 2010, 200(1): 85-98.

DOI：10.1016/j.ejor.2008.12.005

• Train scheduling
• Job shop scheduling

Train scheduling is a complex and time consuming task of vital importance in many countries. To create completely new train schedules that are more accurate and efficient than permitted by current techniques, a novel "hybrid" job shop approach is proposed and implemented in this paper. Unique characteristics of train scheduling are firstly incorporated into a disjunctive graph representation of the solution. Dedicated "stand-alone" constructive algorithms that utilise this representation are then developed. The modelling approach and the constructive algorithms are essential as they provide the basis for which meta-heuristics and other iterative refinement algorithms can be applied. A numerical investigation and case study is provided and demonstrates the viability of the modelling approach. Furthermore it is demonstrated that good quality solutions are provided with reasonable computational effort.

• 出版日期2010-1-1