کاربرد روش گرم و سرد کردن شبیه سازی شده در حل مسئله مکانیابی پایانه های شبکه اتوبوسرانی
نویسنده
چکیده
هدف این تحقیق بررسی سایر روشهای حل و انتخاب روشی کاراتر است. از جمله تکنیکهای مورد نظر، روش گرم و سرد کردن شبیه سازی شده (SA) است، که روشی کارا برای حل مسائل پیچیده برنامه‌ریزی ریاضی است. در این تحقیق با توجه به مشخصات مسئله مکانیابی پایانه‌های شبکه اتوبوسرانی، پارامترهای مورد نیاز روش SA تعیین شده و با تنظیم برنامه‌ای براساس الگوریتم این روش، مسئله مذکور حل شده است. علاوه بر روش SA، مسئله مکانیابی پایانه‌ها توسط روش شمارش ضمنی نیز حل شده است.
در این مقاله نتایج حاصل از به کارگیری سه روش بالا برای شبکه اتوبوسرانی شهر مشهد، با یکدیگر مقایسه شده است. معیار بررسی کارایی روشها، زمان اجرا و دقت جواب بوده است. از نظر مقدار تابع هدف، روش SA در تمامی موارد جوابی برابر یا بهتر از روشهای شاخه و کرانه، و شمارش ضمنی به دست می‌دهد. زمان اجرای آن نیز بسیار کمتر از دو روش دیگر است، به طوری که روش SA حدود 150 برابر سریعتر از نرم‌افزار عمومی GAMS و حدود 50 برابر سریعتر از روش شمارش ضمنی است. نتایج ارائه شده از کاربرد روش SA برای شبکه اتوبوسرانی تهران، کارایی این روش را در حل مسائل بسیار بزرگ نیز نشان می‌دهد.
واژگان کلیدی : شبکه اتوبوسرانی، مکانیابی پایانه‌ها، شمارش ضمنی، شبیه‌سازی به روش سرد و گرم و شمارش ضمنی
کلیدواژه‌ها
عنوان مقاله [English]
Solving Bus Terminal Location Problem Using Simulated Annealing Method
نویسنده [English]
- H. Z. Aashtiani and B. Hejazi
Bus network design is an important problem in public transportation. A main step to this design is determining the number of required terminals and their locations. This is a special type of facility location problem, which is a time-consuming, large scale, combinatorial problem. In a previous attempt by the authors, this problem had been solved by GAMS, based on a branch and bound algorithm.
In this research, different techniques for solving the problem are investigated to choose the best one. One of these methods is Simulated Annealing (SA), which is an efficient algorithm for solving complex optimization problems. SA’s parameters vary from one problem to another. Here, for the bus terminal location problem, SA’s parameters are determined, then the problem is solved. Another algorithm is the Implicit Enumeration method.
In this paper, the results obtained from the above 3 techniques are compared. The criteria for this comparison are the CPU time and the accuracy of the solution. In all the cases studied, SA gave the most accurate results. Its CPU time is lower than the others, too. Solving the bus terminal location problem for the Mashhad network shows that SA is about 150 times faster than GAMS and 50 times faster than Implicit Enumeration. Moreover, bus terminal location problem for the network of the city of Tehran, which is a more difficult problem, has been solved by the SA algorithm successfully.
Keywords: Bus network, Lacation problem, Heuristic, Simulated Annealing, Implicit Enumeration
کلیدواژه‌ها [English]
- Bus network
- Lacation problem
- Heuristic
- Simulated Annealing
- Implicit Enumeration
)