نوع مقاله : مقاله پژوهشی

نویسنده

• محمدعلی موفق پور

دانشگاه صنعتی جندی شاپور دزفول، دزفول، ایران.

چکیده

در مساله مسیریابی پارامترهایی وجود دارد که قطعی و معین نیستند و معمولاً برای ساده‌سازی، بهترین برآوردی که از این پارامترها موجود است به‌عنوان داده قطعی استفاده می‌شود. در این رویکرد ممکن است، در عمل، برخی از محدودیت‌ها نقض شده و جواب بهینه به‌دست‌آمده دیگر موجه نباشد. در این تحقیق، یک مدل برنامه‌ریزی خطی عدد صحیح مخلوط برای مسیریابی با در نظر گرفتن بار ترکیبی، با استفاده از وسایل نقلیه ناهمگن و عدم قطعیت در زمان سفر ارائه شده است. برای رسیدن به جواب‌های استوار، یک الگوریتم ابتکاری برای تولید سناریوهای حدی توسعه داده شده است. پس از همگرا شدن الگوریتم تولید سناریو، زیرمجموعه‌ای از جواب‌ها که در بین جواب همه سناریوهای مختلف مشترکا باقی مانده باشد به‌عنوان قسمت استوار جواب معرفی می‌شود. در این تحقیق در برخی قسمت‌ها کل یک تور استوار باقی مانده است و در برخی حالات نیز فقط سفر بین دو گره جزو جواب استوار مشاهده شد. این اولین بار است که مفاهیم بهینه‌سازی استوار با استفاده از طرح تولید سناریوهای حدی پیاده‌سازی می‌شود. در هر تکرار از تولید سناریوهای حدی، متناقض‌ترین سناریو در برابر یک راه‌حل بهینه داده‌شده تولید می‌شود. مزیت اصلی این روش نسبت به سایر روش‌های بهینه‌سازی استوار موجود، تأکید بر حفظ موجه بودن جواب بهینه در هنگام مواجهه با متنوع‌ترین مجموعه سناریوهای عدم قطعیت است در حالی که هم‌زمان تلاش می‌شود تا حجم محاسبات مورد نیاز تا حد مطلوبی پایین نگه داشته شود.

کلیدواژه‌ها

• بارگیری مرکب
• بهینه سازی استوار
• عدم قطعیت
• وسایل نقلیه ناهمگن

موضوعات

• بهینه سازی استوار

عنوان مقاله [English]

Developing an Efficient Algorithm for Robust School Bus Routing with Heterogeneous Fleet

نویسنده [English]

• Mohamad A. Movafaghpour

Judi-Shapur Unniversity of Dezful,, Dezful, Irann

چکیده [English]

In many Real-world optimization problems, we are facing uncertainties in parameters describing the problem. In general, as a simplifying assumption, uncertainty is ignored. In the school bus routing problem there are uncertain parameters that are assumed to have deterministic values. As a result of this simplifying assumption, the obtained solutions may be mismatched with the real world. This issue arose by violating some hard constraints. In this research, a mixed linear integer programming for school bus routing with mixed loading by using a heterogeneous fleet is presented. The uncertainty of travel times is modeled as interval numbers. We propose a heuristic algorithm to generate extreme scenarios. Each scenario is generated in order to make the last found optimal solution into an infeasible one as much as possible. Experimental results show that deploying this novel algorithm for generating extreme scenarios, efficiently produces diverse scenarios. After the scenario generation algorithm is converged, the intersection of the feasible optimal solutions under diverse scenarios is extracted as robust sub-tours or robust trips. It is the first time to apply the notions of robust optimization using the extreme scenarios generation scheme. At each iteration of the extreme scenarios generation, the most conflicting scenario against a given optimum solution is generated. The main advantage of this method over other present robust optimization methods is its emphasis on maintaining the feasibility of the optimal solution when dealing with the most diverse set of uncertainty scenarios while keeping the computational effort needed as low as desired.

کلیدواژه‌ها [English]

• Uncertainty
• mix loading
• heterogeneous vehicle
• robust optimization