ارايه روش حلي بر مبناي الگوريتم ژنتيك براي مسئله يكپارچه انتخاب و زمان بندي پروژه هاي سرمايه گذاري حمل و نقل

A Genetic Algorithm to Solve Integrated Problem of Selecting and Scheduling Transportation Investment Projects

يكي از مهمترين مسائلي كه متوليان حوزه حمل و نقل همواره درگير آن هستند، انتخاب پروژه هاي سرمايه گذاري به منظور توسعه شبكه حمل و نقل است. البته با توجه به محدوديت هاي منابع در دست، اجراي پروژه هاي انتخاب شده مستلزم زمان بندي آن ها در طول افق برنامه ريزي مي باشد. يكپارچه سازي انتخاب و زمان بندي پروژه ها در قالب يك مدل، هر چند پيچيدگي حل مدل را افزايش مي دهد اما صحت و دقت نتايج را نيز بالا مي برد. در اين مقاله، مدل يكپارچه انتخاب و زمان بندي پروژه هاي سرمايه گذاري حمل و نقل در قالب يك مسئله طراحي شبكه گسسته(DNDP) دو سطحي معرفي شده است. در اين مدل براي هر يك از پروژه هاي پيشنهادي مدت زمان اجرا و ميزان سرمايه گذاري ساليانه، در ابتدا به صورت دقيق مشخص نيست و با حل مدل مقادير آن ها مشخص مي شود. همچنين يك شاخص جديد به منظور ارزيابي پروژه ها با توجه به آستانه ي رضايتمندي استفاده كنندگان سيستم توسعه داده شده است كه در تركيب با شاخص«زمان سفر طي شده در شبكه»، تابع هدف سطح بالايي مدل را تشكيل مي دهد. با توجه به پيچيدگي حل دقيق مدل و زمان فرسا بودن آن، يك الگوريتم ژنتيك براي حل مدل در مدت زمان منطقي ارايه شده است. همچنين جهت بهينه كردن مقادير پارامترهاي الگوريتم، روش طراحي آزمايش هاي تاگوچي بكار برده شده است. به منظور ارزيابي عملكرد الگوريتم ارايه شده، سه مسئله نمونه بر مبناي شبكه ي حمل و نقل شهري سوفالز در مقياس هاي مختلف توليد گرديده است و از الگوريتم ژنتيك و همچنين روش شمارش كامل براي حل آن ها استفاده شده است. نتايج نشان دهنده آن است كه الگوريتم ژنتيك ارايه شده چه از جنبه كيفيت جواب و چه از جنبه زمان حل عملكرد قابل قبولي، به ويژه در مسائل بزرگ، داشته است.

One of the most important issues which transportation authorities are always confronted with is investment projects selection. After projects selection، due to resource constraints، selected projects require to be scheduled during the planning horizon. Integration of selecting and scheduling projects in a single model increases the accuracy of the results، but on the other hand increases complexity. In this paper، integrated model of selecting and scheduling transportation investment projects is introduced as a bi-level discrete network design problem. In this model، duration time and annual costs of candidate projects are unknown at first، but they will be determined by solving the model. A new measure to evaluate projects according to the threshold of user satisfaction is developed that in combination with the total travel time form the upper level objective function. Given the great complexity of the exact solution، a genetic algorithm (GA) is proposed to solve the model in a reasonable time. Also to optimize the GA parameters، the Taguchi method has been used. In order to evaluate the performance of the proposed algorithm، Sioux Falls urban transportation network is considered and three sample problems in different scales have been produced. The proposed GA and complete count method used to solve the problems. Numerical results show that proposed GA has an acceptable performance in both solution quality and solution time، especially in the large-scale problem.