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

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

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

مشخصات پژوهش

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

چکیده

در یکی از تعاریف رایج از مساله طراحی شبکه گسسته حمل ونقل، هدف آن است که با درنظرگرفتن محدودیت بودجه، زیرمجموعه ای از پروژه ها (معابر) پیشنهادی به شبکه اضافه گردد به گونه ای که مجموع کل زمان سفر استفاده کنندگان شبکه به حداقل برسد. این مساله دارای رده پیچیدگی مسائل اصطلاحا NP-Hard است که به منظور حل دقیق آن در ابعاد متوسط م توان از تکنیک های نوین محاسباتی همچون پردازش موازی بهره گرفت. برای این منظور، مطالعه حاضر، الگوریتم دقیق پیشنهادی توسط مطالعه قدیمی لبلانک را درنظرگرفته، به روش جستجوی عمقی در درخت شاخه وکرانه به موازی سازی این الگوریتم می پردازد. برای این منظور، از یک الگوی ارباب-کارگر استفاده شده، نتایج بر روی شبکه شهری شیکاگو با 933 گره و تعداد 12 پروژه پیشنهادی برای تعداد 1، 2، 4، 8، و 16 پردازنده گزارش می گردد. مطابق نتایج حاصله، الگوریتم موازی قادر است برای 16 پردازنده به مقدار تسریع معادل 11.80 دست پیدا کند.