زمانبندي حركت قطارها با استفاده از الگوريتم شاخه و حد و الگوريتم ابتكاري جستجوي پرتو- مطالعه موردي: مسيرهاي دوخطه ريلي ايران

Train Timetabling Problem: Branch and Bound Algorithm and Heuristic Beam Search Algorithms, Case Study: Double Track Railways in Iran

هدف از اين پژوهش، ارايه روشهاي دقيق و تقريبي جهت حل مسيله زمانبندي حركت قطارها در مسيرهاي دوخطه ريلي است. به منظور حل دقيق و يافتن جواب بهينه مسيله زمانبندي حركت قطارها، از بسته نرم افزاري CPLEX11 و نيز الگوريتم شاخه وحد زمانبندي حركت قطارها استفاده مي شود. مدل رياضي زمانبندي حركت قطارها در مسير دوخطه و نيز الگوريتم شاخه و حد پيشنهادي در نرم افزار جاوا پياده سازي شدند و مسايلي با ابعاد مختلف در مسيرهاي ريلي بافق-سيرجان و تهران-مشهد مورد آزمايش قرار گرفتند. مقايسه نتايج حاصل، نشان از برتري عملكرد الگوريتم شاخه و حد پيشنهادي نسبت به CPLEX بويژه در مواجهه با مسايل زمانبندي با ابعاد بزرگ دارد. نتايج نشان مي دهند كه CPLEX ، مسايل بزرگ را در زمانهاي خيلي طولاني حل مي كند؛ در حالي كه الگوريتم شاخه و حد مي تواند جواب بهينه اين گونه مسايل را در زمانهايي منطقي و بسيار كمتر از زمان حل CPLEX به دست آورد. همچنين در اين پژوهش، از پنج روش تقريبي حل مبتني بر الگوريتم جستجوي پرتو استفاده شد. نتايج بررسي روشهاي تقريبي براي مسايل با ابعاد مختلف در مسير تهران-مشهد حاكي از عملكرد مناسب تر روشهاي ابداع شده پژوهش حاضر در مقايسه با روشهاي قبلي به ويژه در مواجهه با مسايل با ابعاد بزرگ است؛ به طوري كه بسته به ميزان اهميت پارامتر دقت و سرعت در شرايط مختلف، روشهاي جستجوي پرتو جديد مي توانند جداول زمانبندي نزديك به بهينه را در زمان هاي منطقي و با اشغال كنترل شده فضاي حافظه ارايه كنند. با استفاده از نتايج اين پژوهش، امكان تهيه جداول زماني حركت قطارها در زمان هاي مناسب براي مسيرهاي دوخطه به ويژه مسيرهاي طولاني با تعداد زياد قطار فراهم مي شود.

The aim of this study is to develop the algorithms for solving train timetabling problems in the double-track railways. To find the optimal solution of the problems, the common software package CPLEX 11 was used in addition to a method based on branch and bound algorithm. Both the mathematical model and branch and bound algorithm were implemented in Java Software and some large-scale real problems were investigated. The problems are based on Bafgh-Sirjan and Tehran-Mashhad railways. Comparison of results show more efficient performance of the algorithm rather than CPLEX. The criterion to compare the performances was the solving time. Five methods were then used based on beam search algorithm to find near-optimal solutions in a rational amount of time. Three of these methods are considered as the innovations of the present research. The results of applying beam search methods demonstrate more impressive proficiency of the heuristic methods innovated compared to methods suggested in previous works especially when facing large-scale problems. Depending on the importance of accuracy and time in different conditions, the excogitated methods can generate the train timetable schedules. By using the results of the research, it is possible to prepare the optimal and near-optimal time-tables especially for the long railways with the large amount of trains.