A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem. (November 2017)

• Record Type: Journal Article
• Authors: Liu, Liang; Dessouky, Maged
• Is Part Of: Computers & operations research. Volume 87(2017)
• Page Start: 165
• Page End: 182
• Publication Date: 2017-11
• Subjects: Train routing -- Scheduling -- Heuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.06.009
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Developed a mixed integer program for the integrated passenger and freight train scheduling problem. Decomposed the problem into several subproblems and each subproblem is solved either optimally or by a heuristic method. On a small network, the proposed heuristic compares favorably to the optimal solution. For a large rail network based on the rail configuration in the Los Angeles area, the proposed heuristic is shown to be effective in reducing freight train delays and improving passenger train punctuality. Abstract: We study the joint problem of scheduling passenger and freight trains for complex railway networks, where the objective is to minimize the tardiness of passenger trains at station stops and the delay of freight trains. We model the problem as a mixed integer program and propose a two-step decomposition heuristic to solve the problem. The heuristic first vertically decomposes the train schedules into a passenger train scheduling phase and then a freight train scheduling phase. In the freight train scheduling phase, we use a train-based decomposition to iteratively schedule each freight train. Experimental results show the efficiency and quality of the proposed heuristic algorithm on real world size problems.