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

نویسنده

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

10.22105/dmor.2022.335870.1595

چکیده

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

کلیدواژه‌ها

موضوعات

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

Developing an efficient algorithm for robust school bus routing with heterogeneous fleet

نویسنده [English]

  • Mohamad Ali Movafaghpour

Jundi-Shapur University of Technology, Dezful, Iran.

چکیده [English]

Purpose: 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.
Methodology: 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.
Findings: 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.
Originality/Value: It is the first time to apply the notions of robust optimization using the extreme scenarios generation scheme. At each iteration of the extreme scenario’s 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
[1]   Soyster, A. L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154–1157.
[2]    Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of operations research, 23(4), 769–805.
[3]    Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations research letters, 25(1), 1–13.
[4]  Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming, 88, 411–424.
[5]   El Ghaoui, L., & Lebret, H. (1997). Robust solutions to least-squares problems with uncertain data. SIAM journal on matrix analysis and applications, 18(4), 1035–1064. DOI:10.1137/S0895479896298130
[6]   El Ghaoui, L., Oustry, F., & Lebret, H. (1998). Robust solutions to uncertain semidefinite programs. SIAM journal on optimization, 9(1), 33–52. DOI:10.1137/S1052623496305717
[7]   Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35–53. DOI:10.1287/opre.1030.0065
[8]   Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. Iie transactions, 40(5), 509–523.
[9]    Yan, Y., Meng, Q., Wang, S., & Guo, X. (2012). Robust optimization model of schedule design for a fixed bus route. Transportation research part C: emerging technologies, 25, 113–121. DOI:10.1016/j.trc.2012.05.006
[10] Agra, A., Christiansen, M., Figueiredo, R., Hvattum, L. M., Poss, M., & Requejo, C. (2013). The robust vehicle routing problem with time windows. Computers & operations research, 40(3), 856–866.
[11] Movafaghpour, M. A. (2016). Project sequence scheduling with interval uncertainty on activities [presentation]. International conference on industrial engineering and management. (In Persian). https://civilica.com/doc/504368
[12] Park, J., Tae, H., & Kim, B. I. (2012). A post-improvement procedure for the mixed load school bus routing problem. European journal of operational research, 217(1), 204–213. DOI:10.1016/j.ejor.2011.08.022