جستجوی عمقی درخت شاخه‌وکرانه در حل مساله طراحی شبکه گسسته حمل‌ونقل

چکیده در یکی از تعاریف رایج از مساله طراحی شبکه گسسته حمل‌ونقل، هدف آن است که با درنظرگرفتن محدودیت بودجه، زیرمجموعه‌ای از پروژه‌ها (معابر) پیشنهادی به شبکه اضافه گردد به‌گونه‌ای که مجموع کل زمان‌سفر استفاده‌کنندگان شبکه به حداقل برسد. این مساله دارای رده پیچیدگی مسائل اصطلاحا NP-Hard است که به منظور حل دقیق آن در ابعاد متوسط م‌توان از تکنیک‌های نوین محاسباتی همچون پردازش موازی بهره‌گرفت. برای این منظور، مطالعه حاضر، الگوریتم دقیق پیشنهادی توسط مطالعه قدیمی لبلانک را درنظرگرفته، به روش جستجوی عمقی در درخت شاخه‌وکرانه به موازی‌سازی این الگوریتم می‌پردازد. برای این منظور، از یک الگوی ارباب-کارگر استفاده شده، نتایج بر روی شبکه شهری شیکاگو با ۹۳۳ گره و تعداد ۱۲ پروژه پیشنهادی برای تعداد ۱، ۲، ۴، ۸، و ۱۶ پردازنده گزارش می‌گردد. مطابق نتایج حاصله، الگوریتم موازی قادر است برای ۱۶ پردازنده به مقدار تسریع معادل ۱۱.۸۰ دست پیدا کند. واژه‌های کلیدی طراحی شبکه گسسته، الگوریتم شاخه‌وکرانه، پردازش موازی.