# ارایه یک مدل ابتکاری مبتنی بر سیستم اجتماع مورچه ها برای حل مسئله زمان بندی حرکت قطار

نویسندگان

1 استادیار، دانشکده راه‌آهن، دانشگاه علم و صنعت ایران، تهران، ایران

2 کارشناس، دانشکده راه‌آهن، دانشگاه علم و صنعت ایران، تهران، ایران

چکیده

در این مقاله با توسعه الگوریتم فوق ابتکاری سیستم اجتماع مورچه‌ها2(ACS) الگوریتمی برای زمان بندی حرکت قطار معرفی شده است. ابتدا نوعی از مسئله زمان بندی حرکت قطار در قالب یک برنامه ریزی ریاضی مدلسازی و سپس الگوریتمی مبتنی بر ACS برای حل آن پیشنهاد شده است. با این فرض که هر قطار در مسئله زمان بندی حرکت قطار معادل یک شهر در مسئله فروشنده دوره گرد3(TSP) باشد، ACS بر روی گراف مسئله TSP، توالی حرکت قطارها را مشخص می کند. بر اساس این توالی و رفع تلاقی در برخورد قطارها، زمان بندی حرکت مشخص خواهد شد. مثالهای عددی در ابعاد کوچک و متوسط برای بررسی صحت و کیفیت جوابها توسط الگوریتم حل شده و نتایج حاصله با حل دقیق بهینه آنها مقایسه شده اند. از مقایسه نتایج حل دقیق مسائل و حل آنها توسط الگوریتم پیشنهادی صرفه جویی های زمانی و پاسخی با کیفیت خوب به دست آمده است. در انتها برای توصیف نحوه محاسبات نیز یک مطالعه موردی ارائه شده است.

کلیدواژه‌ها

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

### An Ant Colony System Heuristic for Train Scheduling Problem

نویسندگان [English]

• <P>K. Ghoseiri 1
• F. Morshedsolouk 2
1 Assistant Professor, Department of Railway Engineering, Iran University of Science and Technology, Tehran, Iran.
2 BS., Department of Railway Engineering, Iran University of Science and Technology, Tehran, Iran,16846-13114</P>
چکیده [English]

Train scheduling problem is one of the severe problems in rail transport planning. Mathematical programming, simulation, expert systems, heuristic and meta-heuristic methods, and combinational methods are amongst techniques for train scheduling. This paper develops an algorithm to train scheduling problem using Ant Colony System meta-heuristic. At first, a kind of train scheduling problem is formulated in a mathematical model and then the algorithm based ACS is presented to solve the problem. The problem is considered as a traveling salesman problem wherein cities represent the trains.ACS determines sequence of trains dispatched on the graph of TSP. According to the sequence as well as removing trains collisions incurred, train scheduling is determined. Numerical examples in small and medium size are solved by using the algorithm and compared to exact optimum solutions to check for the quality and accuracy. To analyze the solution results obtained, they are compared with those of exact optimization method of the train scheduling model. For this purpose, computations are carried out for 45 problems including 3 to 8 trains and 2 to 8 track sections. Comparison of the solutions shows good enough quality and time savings. Sensitivity of the run times of the algorithm with respect to variation of number of track sections as well as with respect to variation of number of trains have been shown and compared with those of exact optimization method. To clarify use of the proposed algorithm, a problem with 30 trains and 4 track sections is solved to illustrate the solution. Structure of the paper is as follows: section 1 presents a hierarchical process of rail transport planning and ant’s behavior which gives inspiration for ant algorithms, is presented. Section 2 reviews the literature of the train scheduling problem and then the manner of creating, developing and applying the ant algorithms is put forward. Section 3 presents the proposed ACS-based model and solution method using ACS for train scheduling. In this section a mathematical model for train scheduling on a single track line is presented. Section 4 illustrates the analysis of the model. This chapter compares the solution results obtained from the model with those of exact optimization method of the train scheduling. Section 5 presents a case study that supports the qualified results of the model. This section describes how to determine the ACS algorithm parameters and section 6 summarizes the paper

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

• ant colony system
• train scheduling problem
• Traveling Salesman Problem
• mathematical programming
• rail transport planning