مشكلة إعادة جدولة السيارة
عودة للموسوعةمشكلة إعادة جدولة السيارة هي معضلة دمجية وتوافقية وبرمجية تسعى لخدمة العملاء في رحلة ما بعد حدوث تغير في الجدول إما نتيجة لتعطل السيارة أوأي تأخير لسبب ما . تم تقديم المشكلة من قبل لي وميرشانداني وبورنشتاين في عام 2007 لما لها من أهمية في مجالات النقل والخدمات اللوجستية.
تعتبر المشكلة ضمن مسائل NP الصعبة ويأتي حلها في التحسين الاندماجي، لذلك في الممارسة الفهمية يتم استخدام طرق ارشادية وحتمية لإيجاد حلول جيدة مقبولة للمشكلة.
نظرة عامة
توجد الكثير من الاختلافات والمجالات الخاصة بمشكلة إعادة جدولة السيارة:
- مشكلة إعادة جدولة السيارة ذات المستودع الواحد (SDVRSP): عدد من الرحلات يجب إعادة جدولتهم بسبب حدوث تأخير على الطريق أوعطل في السيارة أوأي سبب آخر.
الهدف هوالعثور على إعادة جدولة مثالية للأسطول الحالي، باستخدام مركبات إضافية من الممكن من المستودع، من أجل تقليل التأخير وتكاليف التشغيل. في المشكلة، يوجد مستودع واحد فقط يحتوي على جميع المركبات الإضافية، حيث تبدأ جميع سيارة وتنتهي وفقا لجدول خاص بها.
- مشكلة إعادة جدولة المركبات متعددة المستونادىت (MDVRSP): تتشابه مع معضلة المستودع الواحد في تعطل السيارات ووجوب إعادة جدولة لتقليل التأخير والحد من تكاليف التشغيل، لكن يوجد أكثر من مستودع للمساعدة بسيارات أكثر وفقا للجدول الخاص بها.
- مشكلة إعادة جدولة السيارة المفتوحة (OVRSP): المركبات غير مطلوبة للعودة إلى المستودع.
على الرغم من حتى معضلة إعادة جدولة السيارة مرتبطه بمشكلة جدولة المركبات الفردية ومشكلة جدولة المركبات متعددة المستونادىت، إلا حتى هناك فرقًا كبيرًا في متطلبات وقت التشغيل حيث يجب حل المشكلة في أسرع وقت للسماح بإعادة الجدولة أثناء العمليات، في حين حتى مشكلتي إعادة جدولة السيارة المفتوحة ومتعددة المستونادىت غالبا ماقد يكون باستخدام أساليب البرمجة الخطية طويلة المدى.
انظر أيضا
- استمثال توافقي
- مسائل NP صعبة
المصادر
- ^ Li, Jing-Quan; Mirchandani, Pitu B.; Borenstein, Denis (2007). "The vehicle rescheduling problem: Model and algorithms". Networks. 50 (3): 211–229. doi:10.1002/net.20199.
- ^ Pepin, Ann-Sophie; Desaulniers, Guy; Hertz, Alain; Huisman, Dennis (February 2009). "A comparison of five heuristics for the multiple depot vehicle scheduling problem". Journal of Scheduling. 12 (1): 17–30. doi:10.1007/s10951-008-0072-x.
- ^ Spliet, Remy; Gabor, Adriana F.; Dekker, Rommert (March 2014). "The vehicle rescheduling problem". Computers & Operations Research. 43: 129–136. doi:10.1016/j.cor.2013.09.009.
وصلات خارجية
- شرح معضلة إعادة جدولة السيارة.
- أمثلة على مشاكل إعادة جدولة السيارة.
التصنيفات: أقسام التعقيد الحسابي, استمثال توافقي, جدولة (حاسوب), مسائل كثيرة حدود غير قطعية كاملة, بوابة علم الحاسوب/مقالات متعلقة, بوابة رياضيات/مقالات متعلقة, جميع المقالات التي تستخدم شريط بوابات