امیرعلی زرین مهر - استادیار دانشگاه مازندران گروه مهندسی عمران دانشکده فنی و مهندسی دانشگاه مازندران

مساله طراحی شبکه گسسته حمل و نقل به دنبال آن است که ضمن حفظ محدودیت بودجه زیر مجموعه ای از پروژه های احداث معابر را در شبکه موجود در نظر بگیرد به گونهای که معیاری همچون مجموع کل زمان سفر استفاده کنندگان در شبکه به حداقل برسد. این مساله اصطلاحا NP-Hard بوده حل دقیق آن در ابعاد بزرگ امکان پذیر نیست با این حال در ابعاد متوسط میتوان برای حل این مساله از تکنیکهای نوین محاسباتی همچون پردازش موازی بهره گرفت. برای این منظور مطالعه حاضر با تمرکز بر الگوریتم دقیق پیشنهادی توسط مطالعه قدیمی لبلانک با در نظر گرفتن روش جستجوی از نوع اول بهترین" درخت شاخه و کرانه به گزارش نتایج موازی سازی این الگوریتم میپردازد نتایج این مقاله برای یک الگوی موازی سازی ارباب-کارگر و بر روی شبکه شهری شیکاگو با تعداد ۱۲ پروژه پیشنهادی گزارش میگردد براساس این نتایج الگوریتم جستجوی اول بهترین موازی برای ۱۶ پردازنده به تسریع معادل ۱۲٫۲۰ دست پیدا میکند که از مقدار مشابه جستجوی عمقی موازی (عدد (۱۱,۸۰) بالاتراست.

طراحی شبکه گسسته- الگوریتم شاخه و کرانه- پردازش موازی- جستجوی اول- بهترین