MILP formulations and a TS algorithm for reliable last train timetabling with uncertain transfer flows

Abstract

This paper aims to develop reliable last train timetabling models for increasing number of successful transfer passengers and reducing total running time for metro corporations. The model development is based on an observation that real-world transfer flows capture the characteristics of randomness in a subway network. For systematically modelling uncertainty, a sample-based representation and two types of non-expected evaluation criteria, namely max–min reliability criterion and percentile reliability criterion are proposed to generate reliable timetables for last trains. The equivalent mixed integer linear programming formulations are deduced for the respective evaluation strategies by introducing auxiliary variables. Based upon the linearised models, an efficient tabu search (TS) algorithm incorporating solution generation method is presented. Finally, a number of small problem instances are solved using CPLEX for the linear models. The obtained results are also used as a platform for assessing the performance of proposed TS approach which is then tested on large Beijing Subway instances with promising results.

Keywords:

• Last train timetabling
• schedule synchronisation
• uncertain transfer flow
• mixed integer linear programming
• Tabu search algorithm

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the National Natural Science Foundation of China under [grant numbers 71422002, 71621001, 71631007 and 71701012], and the Fundamental Research Funds of Beijing Jiaotong University under [grant number 2015RC075].