An application of genetic and tabu searches to the freight railroad operating plan problem

被引:87
作者
Michael Francis Gorman
机构
关键词
Cost Saving; Search Algorithm; Tabu Search; Plan Problem; Problem Size;
D O I
10.1023/A:1018906301828
中图分类号
学科分类号
摘要
This paper addresses the joint train-scheduling and demand-flow problem for a major US freight railroad. No efficient optimization techniques are known to solve the NP-hard combinatorial optimization problem. Genetic search is used to find acceptable solutions; however, its performance is found to deteriorate as the problem size grows. A "tabu-enhanced" genetic search algorithm is proposed to improve the genetic search performance. The searches are applied to test problems with known optima to gauge them for solution speed and nearness to optimality. The tabu-enhanced genetic search is found to take on average only 6% of the iterations required by genetic search, consistently achieves better approximations to the optimum and maintains its performance as the problem size grows. The tabu-enhanced search is then applied to the full-scale operating plan problem. Model results reveal a potential for 4% cost savings over the current railroad operating plan coupled with a 6% reduction in late service.
引用
收藏
页码:51 / 69
页数:18
相关论文
共 34 条
[1]  
Assad A.A.(1978)Multicommodity network flows - a survey Networks 8 37-91
[2]  
Assad A.A.(1980)Models for rail transportation Transportation Research A14 205-220
[3]  
Assad A.A.(1980)Modelling of rail networks: Toward a routing/makeup model Transportation Research B14 101-114
[4]  
Assad A.A.(1982)A class of train-scheduling problems Transportation Science 16 281-310
[5]  
Barnhart C.(1993)A network-based primal-dual heuristic for the solution of multicommodity network flow problems Transportation Science 27 102-117
[6]  
Sheffi Y.(1980)A model for the blocking of trains Transportation Research 14B 115-120
[7]  
Bodin L.D.(1989)The intermodal equipment distribution model Transportation Research Forum 29 97-103
[8]  
Golden B.L.(1984)A tactical planning model for rail freight transportation Transportation Science 18 165-184
[9]  
Schuster A.(1986)Multicommodity, multimode freight transportation: A general modelling and algorithmic framework for the service network design problem Transportation Research 208 225-242
[10]  
Romeg W.(1993)Integrating and accelerating tabu search, simulated annealing, and genetic algorithms Annals of Operations Research 41 47-67