An implicit enumeration algorithm for the passenger service planning problem: Application to the Taiwan Railways Administration line

Dung Ying Lin, Yu Hsiung Ku

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

In a passenger railroad system, the service planning problem determines the train stopping strategy, taking into consideration multiple train classes and customer origin-destination (OD) demand, to maximize the short-term operational profit of a rail company or the satisfaction levels of the passengers. The service plan is traditionally decided by rule of thumb, an approach that leaves much room for improvement. To systematically analyze this problem, we propose an integer program approach to determine the optimal service plan for a rail company. The formulated problem has a complex solution space, and commonly used commercial optimization packages are currently incapable of solving this problem efficiently, especially when problems of realistic sizes are considered. Therefore, we develop an implicit enumeration algorithm that incorporates intelligent branching and effective bounding strategies so that the solution space of this integer program can be explored efficiently. The numerical results show that the proposed implicit enumeration algorithm can solve real-world problems and can obtain service plans that are at least as good as those developed by the rail company.

Original languageEnglish
Pages (from-to)863-875
Number of pages13
JournalEuropean Journal of Operational Research
Volume238
Issue number3
DOIs
Publication statusPublished - 2014 Nov 1

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'An implicit enumeration algorithm for the passenger service planning problem: Application to the Taiwan Railways Administration line'. Together they form a unique fingerprint.

  • Cite this