基于图染色的铁路调车场调车问题研究
Research on Railway Shunting Problem Based on Graph Coloring
DOI: 10.12677/AAM.2021.102046, PDF,   
作者: 任怡林, 王 龙, 梁东岳, 张淑蓉, 杨卫华*：太原理工大学数学学院，山西 晋中
关键词: 调车场；调车；图染色；贪婪算法；Classification Yard； Shunting； Graph Coloring； Greedy Algorithm
摘要: 本文主要研究铁路调车场调车问题。与已有研究相比，本文同时考虑了调车场的股道数量限制与股道容量限制，更加符合实际情况。首先，我们将带股道数量限制与股道容量限制的调车场调车问题转化为一种特殊的图染色问题。接着，为该问题设计了一种贪婪算法，并通过数值实验说明该算法适合于实际应用。
Abstract: This paper mainly studies the shunting problem of railway shunting yard. Compared with the existing research, this paper considers both the number limit and the capacity limit of the shearing yard, which is more in line with the actual situation. Firstly, we transform the shunting problem of the shunting yard with the limitation of the number of channels and the limitation of the capacity of channels into a special pattern dyeing problem. Then, a greedy algorithm is designed for this problem, and the numerical experiment shows that the algorithm is suitable for practical application.
文章引用：任怡林, 王龙, 梁东岳, 张淑蓉, 杨卫华. 基于图染色的铁路调车场调车问题研究[J]. 应用数学进展, 2021, 10(2): 402-415. https://doi.org/10.12677/AAM.2021.102046

参考文献

[1] Nemani, A.K. and Ahuja, R.K. (2011) OR Models in Freight Railroad Industry. In: Cochran, J.J., Cox, L.A., Keskinocak, P., Kharoufeh, J.P. and Smith, J.C., Eds., Wiley Encyclopedia of Operations Research and Management Science, Wiley, London, 182. [Google Scholar] [CrossRef] 
[2] 赵星宇, 丁世飞. 深度强化学习研究综述[J]. 计算机科学, 2018, 45(7): 7-12.
[3] Levine, S., Pastor, P., Krizhevsky, A., et al. (2016) Learning Hand-Eye Coordination for Robotic Grasping with Large-Scale Data Collection. In: International Symposium on Experimental Robotics, Springer, Cham, 173-184. [Google Scholar] [CrossRef] 
[4] Zhang, M., Mccarthy, Z., Finn, C., et al. (2016) Learning Deep Neural Network Policies with Continuous Memory States. Proceedings of the International Conference on Robotics and Automation, Stockholm, 16-21 May 2016, 520-527. [Google Scholar] [CrossRef] 
[5] Lenz, S., Finn, C., Darrell, T., et al. (2016) End-to-End Training of Deep Visuomotor Policies. Journal of Machine Learning Research, 17, 1-40.
[6] Lenz, I., Knepper, R. and Saxena, A. (2015) Deepmpc: Learning Deep Latent Features for Model Predictive Control. Proceedings of the Robotics Science and Systems, Rome, 13-17 July 2015, 201-209. [Google Scholar] [CrossRef] 
[7] Satija, H. and Pineau, J. (2016) Simultaneous Machine Translation Using Deep Reinforcement Learning. Proceedings of the Workshops of International Conference on Machine Learning, New York, 20-22 June 2016, 110-119.
[8] Oh, J., Guo, X., Lee, H., et al. (2015) Action-Conditional Video Prediction Using Deep Networks in Atari Games. Annual Conference on Neural Information Processing Systems, Montreal, 7-12 December 2015, 2863-2871.
[9] Guo, H. (2015) Generating Text with Deep Reinforcement Learning. Proceedings of the Workshops of Advances in Neural Information Processing Systems, Montreal, 1-9.
[10] 马亮, 张晓霞, 郭进. 基于启发式回溯算法的铁路编组站调车场股道活用研究[J]. 铁道学报, 2016, 38(8): 16-22.
[11] Boysen, N., Emde, S. and Fliedner, M. (2015) The Basic Train Makeup Problem in Shunting Yards. OR Spectrum, 38, 207-233. [Google Scholar] [CrossRef] 
[12] Ivic, M., Markovic, M. and Markovic, A. (2007) Effects of the Application of Conventional Methods in the Process of Forming the Pick-Up Trains. Yugoslav Journal of Operations Research, 17, 245-256.
[13] König, H. and Schaltegger, P. (1967) Optimale Simultanformation von Nahguterzu-gen in Rangierbahnhöfen. Monatsschrift der Internationalen Eisenbahn Kongress-Vereinigung, 4, 1-18.
[14] Schaltegger, P. (1967) Optimierung eines Rangierverfahrens. Ablauf-und Planungsforschung, 8, 302-314.
[15] 马建峰. 关于图染色的算法[J]. 陕西师大学报(自然科学版), 1989(2): 12-15.
[16] 元野. 基于图着色模型的零担物流调度优化问题研究[D]: [博士学位论文]. 哈尔滨: 哈尔滨工业大学, 2015.
[17] 王浩. 基于图着色模型的物流道位优化调度问题研究[D]: [硕士学位论文]. 大连: 大连交通大学, 2016.
[18] Bohlin, M., Hansmann, R. and Zimmermann, U.T. (2018) Optimization of Railway Freight Shunting. In: Handbook of Optimization in the Railway Industry, Springer, Berlin, 181-212. [Google Scholar] [CrossRef] 

为你推荐