8472

8472

خوشه بندي تاخيرات قطارهاي مسافري با استفاده از روش هاي فراابتكاري

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

راه آهن - حمل و نقل ريلي

زمستان 1389

زمستان 1389

دكتر مسعود يقيني- قهرماني

چكيده مسئله خوشه بندي به منظور كمينه كردن مجموع مجذور انحرافات، يك مسئله غيرخطي و غير محدب بوده و داراي تعداد زيادي نقاط بهينه محلي است. هدف از اين تحقيق، ارائه يك روش است كه قادر به حل K-means تركيبي دقيق مبتني بر الگوريتم ژنتيك، جستجوي ممنوعه و مسائل خوشهبندي با سرعت بالا مي باشد. محققين بسياري از الگوريتم ژنتيك به منظور خروج از بهينه محلي استفاده كرده اند، اما در اين تحقيق به جاي استفاده از روشهاي معمول براي عملگر استفاده شده است. منطق روش K-means جهش از تركيب الگوريتم جستجوي ممنوعه و پيشنهادي بر اين امر استوار است كه اگر عملگر جهش به جاي اين كه به طور تصادفي در فضاي جواب اعمال گردد در يك منطقه محدود با استفاده از الگوريتم جستجوي ممنوعه انجام شود به جوابهاي بهتري دست خواهيم يافت. نكته كليدي در الگوريتم جستجوي ممنوعهي پيشنهادي، ايجاد فضاي ممنوعه به منظور فرار از دام مينيمم محلي و پيدا كردن جوابهاي بهتر است. در اين مطالعه نتايج حاصل از پياده سازي الگوريتم پيشنهادي با نتايج حاصل از پياده سازي 3 الگوريتم ژنتيك، جستجوي ممنوعه و حركت دسته جمعي ذرات بر روي 7 مجموعه دادهي استاندارد و 2 مجموعه دادهي شبيه سازي شده مقايسه شد. علاوه بر اين نتايج الگوريتم پيشنهادي با نتايج منتشر شده توسط ساير محققين نيز مقايسه گرديد. نتايج حاكي از آن است كه الگوريتم پيشنهادي با دقت و سرعت بالاتري قادر به خوشهبندي دادهها است. در نهايت با توجه به اين كه يكي از دغدغههاي راه آهن جمهوري اسلامي ايران مسئله تاخير قطارهاي مسافري است و اين تاخيرها هم اعتماد مردم به اين نوع شيوه حمل و نقلي را كاهش مي دهد و هم هزينه هايي براي راه آهن در بردارد، تاخيرات قطارهاي مسافري با استفاده از الگوريتم پيشنهادي خوشه بندي و نتايج آن تحليل شد. بعد از تحليل خوشه ها قوانين حاكم بر مجموعه دادهي تاخيرات قطارهاي مسافري با استفاده از درخت تصميم استخراج گرديد. تاخيرات ،K-means ، واژه هاي كليدي: خوشهبندي، الگوريتم ژنتيك، الگوريتم جستجوي ممنوعه قطار هاي مسافري