عنوان:
بازآرایی شبکه توزیع به‌منظور کاهش تلفات به کمک الگوریتم بلمن- فورد با استفاده از برنامه‌ریزی خطی عدد صحیح و حل کنندة اکتشافی
در هر شبکه توزیع برق، ریسک قطع برق ژنراتور یا سایر انواع خطاها در اجزاء شبکه و سیم‌ها وجود دارد. در چنین شرایطی، ممکن است به‌طور ناگهانی بارهای شبکه بیش از میزان توانی باشد که به آن‌ها عرضه‌شده است. در این تحقیق، یک روش سریع و کارآمد برای بازآرایی شبکه توزیع برق ارائه می‌دهیم. ابتدا، یک الگوریتم توزیع‌شده برای جمع‌آوری اطلاعات در مورد توپولوژی شبکه ارائه‌شده است. این الگوریتم مبتنی بر تغییر الگوریتم بلمن- فورد است. سپس، دو الگوریتم برای تخصیص خودکار منابع توان به بارها طبق رتبه‌بندی اهمیت (اولویت) ارائه‌شده است، که این بارها داده‌شده‌اند. اولین الگوریتم تخصیص توان، مبتنی بر فرمول برنامه‌ریزی خطی عدد صحیح است و الگوریتم دوم اکتشافی است. این دو الگوریتم به ترتیب تحت عنوان حل‌کننده‌ی برنامه‌ریزی خطی عدد صحیح و حل‌کننده‌ی اکتشافی نام‌گذاری شده‌اند. الگوریتم مورداستفاده برای فرموله کردن شبکه به‌عنوان یک مسئله برنامه‌نویسی خطی عدد صحیح می‌باشد. برنامه‌ریزی خطی عدد صحیح همواره به تخصیص بهینه بار برای ژنراتورها اشاره دارد، اما بسیار کندتر است و در شبکه‌هایی که بسیار بزرگ هستند، انتظار وجود راه‌حل غیرممکن است. این‌یک الگوریتم اکتشافی برای تخصیص منابع برای تأمین بارهای دارای بیشترین توان ممکن است، به ترتیب بارگذاری‌های دارای اولویت بالاتر نسبت به بارهای با اولویت کم‌تر صورت میگیرد. حل کنندة اکتشافی نتایج مشابه و گاه یکنواختی را بسته به پیچیدگی توپولوژی ارائه میکند و دستورات راه‌حل آن سریع‌تر از برنامه‌ریزی خطی عدد صحیح است. ارزیابی تجربی برای مقایسه عملکرد حل کنندة اکتشافی با برنامه‌ریزی خطی عدد صحیح پیشنهادی انجام‌شده است که درنهایت راه‌حل ایدهآل مشخص خواهد شد. برنامه‌نویسی خطی عدد صحیح یک مشکل انپی سخت است، بنابراین امکان اتکا به برنامه‌ریزی خطی عدد صحیح را برای راه‌حل‌های اختصاصی برق برای شبکه‌های پیچیده مختلف اندازه‌گیری خواهیم کرد. حل کنندة اکتشافی عمدتاً از یک روش به نام تطبیق مسیر افزایش‌یافته استفاده میکند که مانند الگوریتم بلمن- فورد از نظریه گراف ناشی می‌شود. به‌منظور توصیف راحت‌تر این الگوریتم‌ها، از واحدهای ساده استفاده می‌کنیم. فرض می‌کنیم که ظرفیت‌ها و سطوح اولویت به‌صورت اعداد کامل داده می‌شوند. الزامات بار ارزش واحد دارند. هر یک از این حل‌کننده‌ها می‌توانند به‌راحتی مقادیر ممیز نیم لگاریتمی را برای هر یک از این متغیرها محاسبه کنند، اما آن‌ها را محدود به مقادیر عددی کوچک می‌کنیم تا به‌سادگی اثربخشی این الگوریتم‌ها را نسبت به یکدیگر نشان دهند.
در این تحقیق، یک روش سریع و کارآمد برای تنظیم مجدد شبکه توزیع برق ارائه می‌دهیم. اولین الگوریتم تخصیص برق مبتنی بر فرمول برنامه‌ریزی خطی عدد صحیح[1] است و الگوریتم دوم اکتشافی[2] است. برنامه‌ریزی خطی عدد صحیح همواره به اختصاص بهینه ژنراتورها برای بارگیری اشاره دارد، اما بسیار کندتر است و در شبکه‌هایی که بسیار بزرگ هستند، انتظار برای راه‌حل غیرممکن است. حل کنندة اکتشافی نتایج مشابه و گاه یکنواختی را بسته به پیچیدگی توپولوژی ارائه میکند و دستورات راه‌حل آن سریع‌تر از برنامه‌ریزی خطی عدد صحیح است. ارزیابی تجربی برای مقایسه عملکرد حل کنندة اکتشافی با برنامه‌ریزی خطی عدد صحیح پیشنهادی انجام می‌شود که درنهایت راه‌حل ایدئال مشخص خواهد شد.
این یک الگوریتم اکتشافی[3] برای اختصاص دادن منابع برای تأمین بارهای دارای بیشترین توان ممکن است، به ترتیب بارگذاری‌های دارای اولویت بالاتر نسبت به بارهای با اولویت کم‌تر صورت می گرد. این الگوریتم به‌صورت حل کنندة اکتشافی اشاره خواهد شد. برای بررسی کیفیت راه‌حل‌هایی که حل کنندة اکتشافی ارائه میکند، با راه‌حل‌های تولیدشده توسط فرمول برنامه‌نویسی خطی عدد صحیح مقایسه می‌شود. الگوریتم مورداستفاده برای فرموله کردن شبکه به‌عنوان یک مسئله برنامه‌نویسی خطی عدد صحیح نامیده می‌شود.
برنامه‌ریزی خطی یک ابزار محبوب برای بهینه‌سازی درزمینه تحقیقات عملیاتی است که برای بهینه‌سازی نتایج مطلوب در یک مدل ریاضی به کار می‌رود. راه‌حل‌های تولیدشده توسط آن باید لزوماً مطلوب باشند. بااین‌حال، برنامه‌نویسی خطی عدد صحیح یک مشکل ان پی سخت است، بنابراین امکان اتکا به برنامه‌ریزی خطی عدد صحیح را برای راه‌حل‌های اختصاصی برق برای شبکه‌های پیچیده مختلف اندازه‌گیری خواهیم کرد. حل کنندة اکتشافی عمدتاً از یک روش به نام تطبیق مسیر افزایش‌یافته[4] استفاده میکند که مانند الگوریتم بلمن- فورد از نظریه گراف ناشی می‌شود [9].
به‌منظور توصیف راحت‌تر این الگوریتم‌ها، از واحدهای ساده استفاده می‌کنیم. فرض می‌کنیم که ظرفیت‌ها و سطوح اولویت به‌صورت اعداد کامل داده می‌شوند. الزامات بار ارزش واحد دارند. هر یک از این حل‌کننده‌ها می‌توانند به‌راحتی مقادیر ممیز نیم لگاریتمی[5] را برای هر یک از این متغیرها محاسبه کنند، اما آن‌ها را محدود به مقادیر عددی کوچک می‌کنیم تا به‌سادگی اثربخشی این الگوریتم‌ها را نسبت به یکدیگر نشان دهند. ما به واحدهایی مانند ولتاژ یا آمپر اشاره نمی‌کنیم – چراکه واحدهای انتزاعی هستند.
یکی دیگر از جزئیات مهم در مورد نتایج این است که این تعداد مناسبی برای مقایسه نسبی بین دو الگوریتم وجود دارد، برای دیدن اینکه چطور به‌صورت جداگانه بر روی هر وسیله اجرا می‌شوند، ضروری نیست. دو دلیل برای این مسئله وجود دارد: زبان و سخت‌افزار.
از نرم‌افزار پایتون[6] برای توسعه و آزمایش این حل‌کننده‌ها استفاده می‌شود که در زبان C بسیار سطح بالا نوشته‌شده است. پایتون برای توسعه سریع و تست بسیار عالی است، با توجه به اینکه ایجاد تغییرات با آن آسان است و آن را به یک‌زبان تفسیر کرده، به این معنی که کد منبع توسط مترجم پایتون در نقطه اجرا کامپایل می‌شود. ضعف این امکانات این است که یک‌زبان نسبتاً آهسته است. بسته به وظیفه، گاهی اوقات باید 10 یا 20 برابر اجرای یک برنامه مشابه با زبان C و تقریباً به‌اندازه اسمبلی اجرا شود.
در ابتدا به برنامه‌ریزی خطی عدد صحیح نگاه می‌کنیم. برنامه‌ریزی خطی عدد صحیح یک نوع برنامه‌ریزی خطی است. برنامه‌ریزی خطی عبارت است از حل یک سیستم معادلات که یک رابطه خطی برای پیدا کردن مقدار بهینه (حداقل یا حداکثر) برای یک تابع هدف‌دارند. محدودیت‌ها به سیستم برای متغیرهای محدود در محدوده‌های مشخص اضافه می‌شوند. برنامه‌ریزی خطی عدد صحیح فقط می‌گوید که متغیرها نیز باید اعداد صحیح باشند.
حل مسائل برنامه‌نویسی خطی به ماژول پایتون PuLP منتهی شده است که از حل‌کننده COIN-OR CBC استفاده میکند. [9] مرجع خوبی در مورد نحوة کار برنامه‌نویسی خطی ارائه میکند. برای اهداف این تحقیق، به نظر می‌رسد بهترین راه برای نشان دادن چگونگی استفاده از آن در برنامه‌ریزی خطی عدد صحیح، استفاده از مثال است. در اینجا دید کلی از یک شبکه که باید حل شود ارائه می‌شود:
به‌طورمعمول، باید هر لینک فعال و بار غیرفعال شوند، اما در این تنظیم اولیه هیچ بار یا لینک فعالی وجود ندارد. همان‌طور که نمودار نشان داده‌شده، دو منبع وجود دارد که پنج بار را عرضه می‌کنند. هر یک از منابع دارای ظرفیت 2 هستند، بدین معنا که هرکدام می‌توانند عرضه برق تا دو بار داشته باشند. بارها دارای اولویت‌های 1، 1، 2، 3 و 4 هستند، که 1 دارای کمترین رتبه و 4 بالاترین رتبه است. بدیهی است که با دو ژنراتور که قادر به تأمین حداکثر 2 بار هستند، کمبود عرضه وجود دارد. در بهترین حالت، می‌توانیم 4 بار از 5 بار را برای یک ژنراتور هماهنگ کنیم، که یکی از اولویت‌های بارگیری 1 حذف می‌شود.
[1] integer linear programming formulation
[2] heuristic
[3] heuristic algorithm
[4] augmented path matching
[5] floating point values
[6] Python 2.7
