9237

9237

حل مسئله پوشش مجموعه اي و كاربرد آن در مكان يابي، مطالعه موردي راه آهن

كارشناسي ارشد

مهندسي حمل و نقل ريلي

تابستان 1390

تابستان 1390

دكتر مسعود يقيني

چكيده مسئله پوشش مجموعه اي از مسائل مشهور بهينه سازي تركيبي بوده كه در مدلسازي مسائل متعددي از جمله برنامه ريزي خدمه، انتخاب تامين كنندگان، مسير يابي و مكان يابي كاربرد دارد . در نتيجه حل اين مسئله نيز داراي اهميت بوده و تا كنون روش هاي حل زيادي براي آن ارائه شده است . در اين پايان نامه چند روش حل براي اين مسئله پيشنهاد مي گردد كه روش اول يك روش ابتكاري بوده كه قادر مي باشد در زمان بسيار كوتاه جواب شدني خوبي توليد كند . روش دوم يك روش جديد مبتني برالگوريتم شاخه زدن محلي بوده كه جواب اوليه آن نتيجه الگوريتم ابتكاري مذكور مي باشد . همچنين براي حل اين مسئله يك روش جديد ساختار همسايگي مبتني بر برنامه ر ي زي خط ي پيشنهاد مي گردد. الگوريتم هاي ارائه شده توسط مسائل استاندارد ارزيابي شده كه نتايج نشان دهنده كارا يي الگوريتم ها مي باشد. يكي از كاربردهاي مسئله پوشش مجموعه اي در مسائل مكان يابي مي باشد كه در اين پايان نامه با تمركز بر روي مكان يابي ايستگاههاي راه آهن به آن پرداخته مي شود و يك مدل براي مكان يابي ايستگاههاي راه آهن با رويكرد مسئله پوشش مجموعه اي ارائه مي شود. واژه هاي كليدي: مسئله پوشش مجموعه اي، مكان يابي، روش حل ابتكاري، الگوريتم شاخه ز دن محلي، ساختار همسايگي مبتني بر برنامه ريزي خطي