تخصیص لکوموتیو و زمانبندی قطارهای باری در راه آهن ایران

نوع مقاله : علمی - پژوهشی

چکیده

مسأله تخصیص لکوموتیو و زمانبندی حرکت قطارهای باری، از جمله مهم‌ترین مسائل برنامه‌ریزی در راه‌آهن است که به دلیل هزینه زیاد ناشی از جابجاییهای غیرضروری لکوموتیو و هزینه‌های ناشی از تأخیر قطارهای باری، حل آن ها به‌طور همزمان و ترکیبی می‌تواند بر کاهش هزینه خدمات حمل و نقل ریلی در راه آهن  ایران، تأثیر بسزایی داشته باشد. مسأله تخصیص لکوموتیو شامل تخصیص لکوموتیوها به رامهای باری است، به‌گونه‌ای که ضمن حمل کلیه رامهای باری، کمترین جابجایی غیرفعال لکوموتیو و کمترین زمان انتظار رامهای باری را ممکن سازد. در راه آهن ایران، قطارهای مسافری طبق برنامه زمانی مشخص در شبکه حرکت می‌کنند. برنامه‌ریزی زمان حرکت قطارهای باری شامل تعیین توالی و زمان حرکت قطارهای باری، در فواصل زمانی بین قطارهای مسافری است، به‌گونه‌ای که تداخلی با قطارهای مسافری نداشته باشند و کمترین تأخیر زمانی ممکن در رسیدن این قطارها به مقصد ایجاد شود. در این مقاله مسئله تخصیص لکوموتیو و زمانبندی حرکت قطارهای باری برای راه آهن ایران ، در دو فاز، پیاده سازی شده است. ابتدا لوکوموتیو مورد نیاز برای حمل رامهای ‌ باری به آنها تخصیص داده می‌ شود و سپس برنامه زمانبندی حرکت قطارهای باری تشکیل شده، تعیین می‌گردد. در فاز اول، تخصیص لوکوموتیو به رامهای موجود با استفاده از الگوریتم ژنتیک صورت می‌گیرد. در فاز دوم، بهترین برنامه تخصیص لوکوموتیو که در فاز یک به دست آمده، در نظر گرفته شده و یک حد پایین برای زمان رسیدن قطارهای باری به مقصدشان محاسبه می‌شود. سپس مجدداً با استفاده از یک الگوریتم ژنتیک دیگر، زمانبندی قطارهای باری انجام می‌شود. برای ارزیابی روشهای بکار گرفته شده، یک مسئله ساده به صورت تفصیلی و 30 مسئله با ابعاد مختلف براساس شرایط شبکه راه آهن ایران حل و جوابهای آنها  ارایه شده است.

کلیدواژه‌ها


عنوان مقاله [English]

Locomotive Assignment and Freight Train Scheduling in Iranian Railways

چکیده [English]

Providing a cost-effective solution to the two-fold problems of assigning locomotives to trains and train scheduling is of high importance for most railway companies. Due to high cost of deadheading locomotives and tardiness of trains, solving these two problems simultaneously has a significant impact on decreasing transport expenses in Iranian railways. The locomotive assignment problem is to assign locomotives to a set of freight rakes in order to provide the hauling of all freight rakes while maintaining minimum possible movements of deadheading locomotives and minimum coupling delay of freight rakes. In Iranian railways, passenger trains run across the network according to a fixed schedule. Scheduling freight trains is to determine the departure time, arrival time and the movement sequence of freight trains during the intervals between passenger trains in the way that they do not interfere with passenger trains’ schedule and at the same time minimum delay of freight trains occurs. In this paper the problems of locomotive assignment and train timetabling have been solved in two phases. In the first phase, locomotives are assigned to freight rakes using a genetic algorithm. In the second phase, the best locomotive assignment solution which is the output of the first phase is selected and a lower bound for arrival time of freight trains on their destination is calculated. Then freight trains are scheduled using another genetic algorithm. Using the applied method, the results of 30 test problems of simultaneous locomotive assignment and freight-train scheduling are presented.

کلیدواژه‌ها [English]

  • Locomotive assignment
  • Train scheduling
  • freight trains
- یقینی، م.، لسان، ج (1389)”برنامه‌ریزی عملیات حمل و نقل ریلی” ، انتشارات دانشگاه علم و صنعت ایران.
- راه آهن جمهوری اسلامی ایران، دفتر آمار و فناوری اطلاعات(1379) «سالنامه آماری حمل‌ونقل ریلی کشور».
- Ahuja, R., Liu, J., Orlin, J. B., Sharma, D. and Shughart, L. A. (2005) “Solving real-life locomotive scheduling problems”, Transportation Science, 39, pp. 503-517.
- Booler, J. M. P. (1980) "The solution of a railway locomotive scheduling problem", Journal of the Operational Research Society, 31, pp. 943-943.
- Booler, J. M. P. (1995) "A note on the use of Lagrangean relaxation in Railway scheduling", Journal of the Operational Research Society, 46, pp. 123-127.
- Cacchiani, V., Caprara, A. and Toth, P. (2008) "A column generation approach to train timetabling on a corridor", 4 OR 6, pp. 125-142.
- Caprara, A., Monaci, M., Toth, P. and Guida, P. L. (2006) "A lagrangian heuristic algorithm for a real-word train timetabling problem", Discrete Applied Mathematics, 154, pp. 738-753.
- Carey, M. and  Lockwood, D. (1995) "A model, algorithms and strategy for train pathing", Journal of the Operational Research Society, 46, pp. 988-1005.
- Cordeu, J.-F., Desaulniers, G., Lingaya, N., Soumis, F. and Desrosiers, J. (2001) "Simultaneous locomotive and car assignment at VIA Rail Canada", Transportation Research- B35, pp. 767-787.
- Cordeu, J.-F., Soumis, F. and Desrosiers, J.         (2000) "A Benders decomposition approach for the locomotive and car assignment problem", Transportation Science, 34, (2), pp. 133-149.
- D’Angelo, G., Di Stefano, G. and  Navarra, A. ( 2009)  "Evaluation of recoverable –robust timetable on tree networks", 20th international workshop on Combinational Algorithms (IWOCA 2009), Lecture Notes in Computer Science, 5874, pp. 24-35.
- Dorfman, M. J. and  Medanic, J. (2004) "Scheduling trains on a railway network using a discrete event model of railway traffic", Transportation Research - B 38, (1) , pp. 81-98.
- Fischetti, M. and  Toth, P. (1997) “A package for locomotive scheduling”, Technical Report DEIS-OR-97-16, University of Bologna, Italy.
- Forbes, M. A., Holt, J. N. and Watts, A.M. (1991) "Exact solution of locomotive scheduling problems", Journal of the Operational Research Society, 42, (10), pp. 825-831.
- Ghoseiri, K. and  Ghandpour, S. F. (2010) “A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows”, Journal of Applied Soft Computing,10, pp. 53-65.
- Ghoseiri, K., Szidarovszky, F. and Asgharpour, M. J. (2004) "A multi objective train scheduling model and solution", Transportation Research- B 38, (10) , pp. 927-952.
-Godwin, T., Gopalan, R. and Narendran, T. T. (2006) "Locomotive assignment and freight train scheduling using genetic algorithms", International Transactions in Operational Research, 13, pp.299-332.
- Goldberg, D. E. (1989) "Genetic algorithms in search and optimization and machine learning", Addison-Wesley Publishers, Massachussets.
- Jovanovic, D. and  Harker, P.T. (1991) "Tactical scheduling of rail operations: the SCAN I system. Transportation Science 25, (1), pp. 46-64.
- Kraay, D., Harker, P.T. and Chen, B. (1991) "Optimal pacing of trains in freight railroads: model formulation and solution", Operations Research 39, (1), pp. 82-99.
- Kuo, C. C. and  Nicholls, G. M. (2007) “A mathematical modeling approaches to improving locomotive utilization at a freight railroad”, OMEGA, the International Journal of Management Science, 35, pp. 472-485.
- Noori, S. and  Ghannadpour, S. F. (2012) " Locomotive assignment problem with trains precedence using genetic algorithm", Journal of Industrial Engineering International, 8:9.
- Nou, A., Desrosiers, J. and Soumis, F. (1997) “Weekly locomotive scheduling at Swedish state railways”, Technical Report, G-97-35.Gerad, Canada.
- Orda, A. and  Rom,  R. (1990) "Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length", Jurnal of the Association for Computing Machinery 37, (3), pp. 607-625.
- Rouillon, S., Desaulniers, G. and Soumis, F. (2006) “An extended branch-and-bound method for locomotive assignment”, Transportation Research, 40, pp. 404-423.
- Salim, V. and Cai, X. (1997) "A genetic algorithm for railway scheduling with environmental considerations", Environmental modeling and Software 12, (4), pp.301-309.

- Shafia, M. A. , Jamili,  A. and  Pourseyedaghaee, M. (2010) "A new mathematical model for the job shop scheduling problem with uncertain processing times", International Journal of Industrial Engineering Computations, 2, pp. 295-306.
- Shafia, M. A., Pourseyedaghaee, M., Sajadi, S.J. and  Jamili, A. (2011) "Robust train timetabling problem: Mathematical model and Branch and bound algorithm", IEEE Transactions on Intelligent Transportation Systems, accepted manuscript.
- Shafia, M. A., Sajadi, S. J., Jamili, A., Tavakkoli-Moghaddam, R. and  Pourseyedaghaee, M. (2012) "The periodicity and robustness in a single-track train scheduling problem", Journal of Applied Soft Computing, 12, pp. 440-452.
- Vaidyanathan, B., Ahuja, R., Liu, J. and Shughart, L. (2008) “Real-life locomotive planning: New formulations and computational results”, Transportation research, 42, pp. 147-168.
- Wright, M. B. (1989) "Applying stochastic algorithms to a locomotive scheduling problem", Journal of the Operational Research Society 40, (2), pp. 187-192.
- Zhou, X. and  Zhong, M. (2005) "Bicriteria train scheduling for high-speed passenger railroad planning applications", European Journal of Operational Research 167, (3), pp. 752-771.
- Zhou, X. and  Zhong, M. (2007) "Single-track train timetabling with guaranteed optimally: Branch-and-bound algorithms with enhanced lower bound", Transportation Research: part B, 41, pp. 320-341.
- Ziarati, K., Soumis, F., Desrosiers, J., Gelinas, S. and Saintonge, A. (1997) “ Locomotive assignment with heterogeneous consists at CN North America”, European Journal of Operational Research, 97, pp. 281-292.
- Ziarati, K., Soumis, F., Desrosiers, J. and  Solomon, M. M. (1999) “A branch-first, cut second approach for locomotive assignment”, Management Science, 45, pp.1156-1168.