10042

10042

ارائه روشي مبتني بر روش شاخه و برش براي حل مسائل طراحي شبكه هاي چند كالايي

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

راه آهن گرايش حمل و نقل ريلي

خردادماه 1391

خردادماه 1391

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

چكيده مسائل طراحي شبكه هاي چند كالايي ظرفيت دار جزء مسائل NP-hard به شمار مي آيند به دليل اينكه با استفاده از روش هاي دقيق در يك زمان منطقي نمي توان جواب بهينه براي اين نوع مسائل به دست آورد.به همين دليل روش هاي فرا ابتكاري و ابتكاري زيادي ارائه شده است تا جواب هاي نزديك بهينه را در زمان قابل قبولي بدست بياورند در اين روش ها تضميني براي بدست آوردن جواب بهينه وجود ندارد . ما در اين پايان نامه به دنبال ارائه يك روشي مبتني بر روش شاخه و برش هستيم كه بتوانيم با گنجاندن روش هاي ابتكاري و فرا ابتكاري در داخل الگوريتم شاخه و برش جواب هاي بهينه را در زمان مناسب براي اين مسائل بدست بياوريم. ابتدا پارامترهاي موثر دركارايي الگوريتم شاخه وحد را شناسايي كرديم سپس روش¬هاي مختلفي كه قبلا براي هر كدام از اين پارامترها ارائه شده بود و روش هاي جديدي كه خودمان ارائه داده ايم را پياده سازي كرديم و در نهايت با استفاده از طراحي آزمايش¬ها بهترين تركيب را براي مسائل طراحي شبكه هاي چند كالايي ظرفيت دار كه در ادبيات موضوع استفاده شده بود آورديم . واژه‌هاي كليدي: برنامه ريزي مخلوط ،طراحي شبكه هاي چند كالايي، شاخه و برش