مشكلة جدولة الشحن لشبكات المركبات الكهربائية

المركبة الكهربائية (EV) هي وسيلة نقل واعدة مع العديد من المزايا، مثل انخفاض انبعاث الكربون، وكفاءة عالية في استهلاك الطاقة. ومع ذلك، فإنها تتطلب شحنًا متكررًا وطويلًا. في محطات الشحن العامة، تقضي المركبات الكهربائية وقتًا طويلاً في الانتظار خاصة خلال ساعات الذروة. لذلك، تحتاج إلى طريقة فعالة لتقليل إجمالي وقت الشحن للمركبات الكهربائية. ندرس في هذه الورقة مشكلة جدولة شحن المركبات الكهربائية (EVCS). أولاً، نثبت أن EVCS هي NP-Complete، والتي يمكن تقليلها من مشكلة جدولة آلة متوازية (PMS). ثم تم اقتراح خوارزميتين زكومنديتين: خوارزمية وقت البداية المبكر (EST)، وخوارزمية وقت الانتهاء المبكر (EFT). تحاول خوارزمية EST تقديم وقت بدء الشحن لخدمة العملاء في أقرب وقت ممكن، بينما تركز خوارزمية EFT على وقت الانتهاء المحتمل للشحن لخدمة العملاء في أسرع وقت ممكن. أخيرًا، تظهر المحاكيات أن الخوارزميات المقترحة تتفوق على خوارزمية الجدولة الجشعة الكلاسيكية: تعيين كل مركبة كهربائية لأقرب محطة شحن لها، ثم اختيار المخرج حيث يوجد أقل عدد من المركبات الكهربائية في الانتظار. عادة، تحت إعدادات المحاكاة لدينا، يمكن تقليل متوسط وقت الانتهاء والحد الأقصى لوقت الانتهاء بحوالي ساعة واحدة، وست ساعات على التوالي.