Graph Partition Based Decomposition Approach for Large-Scale RailwayLocomotive Assignment

摘要

Locomotive assignment is a classic planning problem in railway industry. Different models and algorithms(e.g., network flow model, MIP model, adaptive dynamic programming) are proposed to solve this problem and have gotremarkable progress. In practice, the locomotives are usually in the size of hundreds to even more than a thousand. So assigningindividual locomotives to trains on railway network will result in too huge modeling space for the problem to besolved. Hence most existing research work takes a trade off to concern the types (or type combinations) of locomotives,which are usually in the size of tens at the most. This impedes the application value for being unable to consider the availabilityand maintenance requirement of individual locomotives. In this paper, a novel path-based MIP model is proposedfor modeling the locomotive assignment problem. By adopting graph partition method on the space-time network, theoriginal problem is decomposed into inter-connected multiple sub-problems. Then an iterative MIP solving algorithm isdevised to find the near optimized solution for the original problem. The approach proposed in this paper has been validatedin a railway bureau in China. The experiment shows that the approach has superior advantage in both scalability andperformance with reasonable cost of objective value.