1403/01/24
امیر علی زرین مهر

امیر علی زرین مهر

مرتبه علمی: استادیار
ارکید:
تحصیلات: دکترای تخصصی
اسکاپوس:
دانشکده: دانشکده مهندسی و فناوری
نشانی:
تلفن: 011-35302903

مشخصات پژوهش

عنوان
نتایج الگوریتم موازی جستجوی-اول-بهترین در حل مساله طراحی شبکه گسسته حمل‌ونقل
نوع پژوهش
مقاله ارائه شده
کلیدواژه‌ها
طراحی شبکه گسسته، الگوریتم شاخه‌وکرانه، پردازش موازی، جستجوی اول-بهترین
سال 1401
پژوهشگران امیر علی زرین مهر

چکیده

مساله طراحی شبکه گسسته حمل‌ونقل به دنبال آن است که ضمن حفظ محدودیت بودجه، زیرمجموعه‌ای از پروژه‌های احداث معابر را در شبکه موجود درنظربگیرد، به‌گونه‌ای که معیاری همچون مجموع کل زمان‌سفر استفاده‌کنندگان در شبکه به حداقل برسد. این مساله اصطلاحا NP-Hard بوده، حل دقیق آن در ابعاد بزرگ امکان پذیر نیست. با این حال، در ابعاد متوسط میتوان برای حل این مساله از تکنیک‌های نوین محاسباتی همچون پردازش موازی بهره‌گرفت. برای این منظور، مطالعه حاضر، با تمرکز بر الگوریتم دقیق پیشنهادی توسط مطالعه قدیمی لبلانک، با درنظرگرفتن روش جستجوی از نوع "اول-بهترینِ" درخت شاخه‌وکرانه، به گزارش نتایج موازی‌سازی این الگوریتم می‌پردازد. نتایج این مقاله، برای یک الگوی موازی‌سازی ارباب-کارگر و بر روی شبکه شهری شیکاگو با تعداد 12 پروژه پیشنهادی گزارش می‌گردد. براساس این نتایج، الگوریتم جستجوی اول-بهترین موازی برای 16 پردازنده به تسریع معادل 12.20 دست پیدا می‌کند، که از مقدار مشابه جستجوی عمقی موازی (عدد 11.80) بالاتر است.