بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ﲠینه سازی همزمان چراغ راهنما و ﲣصیص ترافیک بر اساس مدﳍای شبکه
چکیده
بهینه سازی مقادیر پارامترهای کنترلی شبکه حمل و نقل نظیر چراغ راهنما از اهداف طراحی یک سیستم مدیریت شبکه است. لیکن این مساله در ارتباطی دو طرفه با میزان جریانهای تعادلی شبکه مورد نظر است. هدف در این مقاله پیادهسازی توام مساله تنظیم چراغ راهنما و جریانهای تعادلی کاربر در قالب یک برنامه ریزی دو سطحی و سپس بهکارگیری مدلهای شبکه نظیر مدل کمترین هزینه انتقال چند محموله ای و آلگوریتم نقطه درونی برای بسط یک روش برای یافتن مقادیر بهینه زمان چراغ راهنما و جریانهای تعادل کاربر به صورت همزمان است.
کلمات کلیدی
زمانهای چراغ راهنما، مساله تخصیص ترافیک، بهینهسازی دو سطحی، مدل کمترین هزینه انتقال جریانهای چند محموله ای، آلگوریتم نقطه درونی.
۲. مقدمه
با افزایش روز افزون سیستمهای اطلاعات مسافرتی١ (ATIS) و خیزش عظیم سیستمهای ماهوارهای (GPS) که به مسافران برای یافتن مسیر بهینه کمک میکند، میتوان انتظار داشت که مفاهیمی نظیر مسیر بهینه و انتخاب بهینه که اساس مدلهای تخصیص است از حالت شبه-تئوری به مرحله واقعیت برسد. از این رو کار کردن روی این مقوله نه تنها جالب بلکه لازم مینماید . از سوی دیگر اثر گذاری سیاستهای کنترلی مدیریت شبکه نظیر زمانهای چراغ راهنما روی مسیر بهینه غیر قابل انکار است. برای بالا بردن سطح سرویس و برآورده کردن رضایت کاربران شبکه انجام عملیات بهینهسازی روی پارامترهای شبکه ضروری به نظر میرسد که در راستای آن، نرم افزارهای گوناگونی نیز نظیر TRANSYT و SCOOP و SIGNAL به بازار عرضه شده است. لیکن به دلیل ارتباط دو طرفه میان سیاست های کنترل ترافیک و جریانهای بهینه تعادلی، یافتن مقادیر بهینه هر یک بایستی با توجه به دیگری باشد. وجود ارتباط دوری میان این دو مساله نخستین بار بوسیله پاوسه ٢ در ١٩٦٨ مورد تاکید قرار گرفت ٣. وی برای هر تقاطع تابعی فرموله کرد که وابسته به جریانهای ترافیک نزدیک شونده به آن تقاطع بود. نتیجه کار وی این بود که حجم عظیمی تحقیق روی این مساله به وقوع پیوست. در ابتدا پیکان توجهات به سمت یافتن روشی مبتنی بر تجربه برای تنظیم چراغ راهنما بود. اسمیت ٤ در ١٩٨٠ مثالهایی ارائه نمود که نشان میداد سیاستهای متداول سنتی نظیر هم-اشباعی ٥ میتوانند شبکه را به سمت تعادل ناپایدار سوق دهند و گاهی بدترین شرایط ترافیکی را ایجاد نمایند. بیش از این وی نشان داد در بعضی از حالتهای حقیقی آزمایش شده که تنظیم چراغ راهنما تحت تاثیر مستقیم جریانهای ترافیکی وارد شده به تقاطع صورت میگیرد زمان مسافرت حتی تا ٣٠% طولانیتر میشود. لذا وی سیاست جدید دیگری برای تنظیم چراغ راهنما به نام پو ٦ ارائه نمود که هدف در آن بیشینهسازی ظرفیت تقاطع و اطمینان از پایداری تعادل کاربر بود. تقریباﹰ در همین دوره پروفسر آلسوﭖ و همکارش چارلسورث ١ آلگوریتمی ریاضی برای بهینهسازی چراغ راهنما ارائه نمودند . ایشان در مقاله خود در ١٩٧٧ این مساله را برای شبکه با اندازه متوسط حل نمودند. این عملیات بدین شکل انجام میشد که زمان چراغ راهنما و جریان روی کمان متناوباﹰ معین میشد . به این ترتیب که در هر تکرار با ثابت گرفتن مدت زمان چراغهای راهنما، مساله تخصیص تعادل کاربر حل میشد و با جریانهای پیدا شده روی کمانها زمانهای بهینه چراغ راهنما به دست میآمد. ایشان برای به دست آوردن تابع کارایی شبکه نیز از ایده ابرمدلها استفاده نمودند. به این صورت که در هر گام برای یک مقدار ثابت پارامتر کنترلی، چندین مقدار متفاوت جریان به کار برده میشد و سپس با برازش نقاط به دست آمده متناظر با مجموع تاخیرها، در قالب یک تابع چندجمله ای، تابع کارایی سیستم به دست می آمد و روی آن عملیات بهینهسازی محقق میشد. این ایده انقلابی دانشمندان بعدی را برای تحقیق درباره درستی یا نادرستی این آلگوریتم به مبارزه طلبید. در این راستا گرشوین و تان ٢ در ١٩٧٩ نشان دادند که در حالت کلی زمانهای چراغ راهنما و جریان تعادلی کمانها که از آلگوریتم آلسوﭖ به دست می آمد، بهینه نبودند. به موازات این عملیات مارکوتی ٣ نیز در ۱۸۹۱ و ۳۸۹۱ یک روش دقیق و چندین روش ابتکاری برای حل مساله تنظیم چراغ راهنما به کار برد و نتایج خوبی از شبکه کوچک آزمایشی به دست آورد.
جهش دیگر در سیر تکاملی این مساله با کار اسمیت پدید آمد. وی در مقاله ۳۹۹۱ خود به جمعآوری پایههای ریاضی لازم برای این مساله پرداخت. در دهه ۰۹۹۱ کوششهای زیادی در این راستا و در زیر چتر برنامهریزی دو سطحی به وقوع پیوست. هیدکر و خو ٤ در ١٩٩٠ یک تقریب خطی برای تخصیص ترافیک متعادل ارائه نمودند و مساله را به صورت دنباله وار با تقریبهای خطی حل نمودند. یانگ و یاگر ٥ در ١٩٩٥ با ایده جالب و متفاوتتری بر پایه تحلیل حساسیت، آلگوریتمی برای تنظیم چراغ راهنما و تخصیص ترافیک ارائه نمودند. در کار ایشان یک زیر مساله خطیسازی شده با یک تنظیم خاص چراغ راهنما فرموله میشد. کاسکتا ١ در همین زمان روی این گروه از مسائل متمرکز بود. وی دو سری شرایط کنترلی متفاوت که منجر به دو مساله مجزا میشد مطرح نمود. در دسته اول هدف یافتن کمینه سراسری تابع کارایی شبکه ٢ بود. یک دستهبندی روی روشهایی که بهینه سراسری این مساله را به دست میداد، توسط مارکوتی ٣ و نیز توسط کانتارلا ٤ صورت پذیرفته بود. دسته دوم شامل طرحهایی بود که روی مساله تنظیم چراغهای راهنما یک آلگوریتم بهینهیابی موضعی با توجه به پاسخهای جریان شبکه به مدت زمان چراغ راهنما به کار می گرفتند. در این طرح هر کدام از مسائل مستقلاﹰ تابع هدف موضعی خودشان را کمینه مینمودند و یا از سیاستهای تنظیم چراغ راهنما نظیر هم-اشباعی یا پو استفاده مینمودند.
در به کار گیری برنامهریزی غیر خطی برای تنظیم چراغ راهنما میتوان به کارهای اسمیت و همکارانش در ۸۹۹۱ و کلگ ٥ در ۱۰۰۲ اشاره نمود. ایشان از روش تندترین شیب در محاسبه زمانهای چراغ راهنما بهره بردند. همچنین توزیع سراسری ترافیک را در حالت تعادل در نظر گرفتند. چیو ٦ در ١٩٩٩ فرآیند جستجوی مخلوط را برای این مساله به کار برد. وی در آلگوریتم خود از گرادیان تصویر شده استفاده نمود که قبل از وی بوسیله شفی و پاول ٧ به کار رفته بود.
کار جالب دیگر در این زمینه آزمایشهای کاسکتا ٨، لی و ماشمهل ٩ بود که نشان داد روشهای گوناگون جواب و همچنین نقاط شروع متفاوت میتواند منجر به جوابهای گوناگون شود که این خود دلیلی محکم بر نامحدب بودن مساله بود. همچنین ایشان نشان دادند هرچه اندازه شبکه بزرگتر شود درجه اشباع نیز بیشتر خواهد شد.
ایده دیگر استفاده از بهینهسازی-شبیهسازی روی این مساله است که ما حصل ترکیب روشهای بهینهسازی ابتکاری نظیر آلگوریتم ﮊنتیک و نرم افزارهای شبیه سازی است. سیلان و بل ١ در ۴۰۰۲ و ۵۰۰۲ مقالات خود را با چنین دیدی ارائه نمودند.
هدف در این مقاله ترکیب بهینهسازی پارامترهای کنترلی نظیر زمان سبز چراغ راهنما با مساله تخصیص تعادل کاربر در قالب یک طرح دو لایه ای است . در لایه بیرونی اقدام به بهینهسازی روی پارامترهای کنترلی میشود و نتایج این لایه به صورت دستورالعملهایی به لایه درونی منعکس شده و در لایه درونی بر اساس این مقادیر، جریانهای تعادل کاربری محاسبه میشود. این مقادیر به لایه بیرونی گزارش میشود تا مجدداﹰ در بهینهسازی روی مقادیر کنترلی مورد استفاده قرار گیرد. این پروسه تا حصول همگرایی به پیش میرود. برای بهینهسازی روی لایه بیرونی از یک آلگوریتم تندترین شیب که در آزمایشهای قبلی سیپریانی ٢ نتایج خوبی به همراه داشته استفاده میشود. برای یافتن میزان جریانهای تعادلی نیز از یک مدل کمترین هزینه انتقال چند محموله ای با به کارگیری آلگوریتم نقطه درونی بهرهبرداری میشود.
۳. زمانهای چراغ راهنما
ایمنی و توانایی یک راه برای عبور دادن تعداد کافی خودرو با حداقل تاخیر و ایجاد ناراحتی برای استفاده کنندگان، به نظم و ترتیب جریان آمد و شد بستگی مستقیم دارد. در صورتی این نظم را میتوان در جاده و خیابان حاکم گردانید که علایم رانندگان را به طور دقیق و صحیح راهنمایی کنند. وسایل کنترل ترافیک به دو گروه کلی تقسیم میگردند.
الف. علائم عمودی مانند تابلوها، چراغهای راهنما، علایم هادی و سایر تجهیزات ب. علائم افقی مانند خط کشیها، نوشتهها، نقشها و علایم منعکس کننده هدف در این تحقیق بررسی نقش و جایگاه چراغ راهنماست. واگذاری تقدم عبور به جهتهای مختلف حرکت که توسط چراغهای راهنما انجام میشود در بهبود کیفیت ترافیک تاثیر بسیار زیادی دارد. چراغ راهنمایی که در محل مناسب قرار گرفته باشد و به خوبی عمل نماید دارای فوایدی به شرح زیر است.
برقراری حرکت منظم ترافیک افزایش ظرفیت تقاطع
جلوگیری از تصادفها به ویﮊه تصادفهای با زاویه قائمه ایجاد جریان عبور بدون توقف در کلیه تقاطعها برای خودروهایی که با سرعت تعیین شده حرکت کنند، در شرایط مطلوب و با هماهنگ کردن چراغها.
قطع جریان ترافیک در تقاطعهایی که یکی از خیابانهای آنها دارای بار سنگین ترافیک است و فراهم کردن فرصتی که اجازه عبور به خودروها و پیادهروها در خیابان متقاطع داده شود.
نخستین موضوعی که درباره چراغهای راهنمایی میتواند مطرح شود، ضرورت قرار دادن یا ندادن آنها در یک تقاطع به خصوص است. به عبارت دیگر توجیه نصب چراغهای راهنمایی باید بر اساس ایمنی، زمانهای عبور، عدالت اجتماعی، آلودگی هوا و سایر م وارد باشد.
اما به فرض قرار دادن چراغراهنما پارامترهای آن بایستی در جهت بهبود وضعیت سیستم تنظیم گردد. پارامترهای اصلی چراغ راهنما به شرح زیر است:
الف. چرخه (زمان چرخه یا طول چرخه) : یک دوره علامتدهی چراغ راهنمایی.
فاز یا مرحله (فاز چراغراهنما) : بخشی از یک چرخه که به ترکیبی از حرکات به طور همزمان حق تقدم میدهد، در حالی که سایر جریانها متوقف می شوند. ملاحظات ایمنی حکم میکند که در هر فاز فقط جریانهای ترافیکی سهیم باشند که مسیرهای آنها یکدیگر را قطع نمیکنند. در این صورت میتوان یک مساله رنگ آمیزی گراف برای یافتن تعداد و فازهای حرکت در یک تقاطع پیچیده به کار برد. لیکن در عمل از برخی برخوردها چشمپوشی میشود. شکل زیر نمودار فازبندی را برای یک تقاطع دو خیابانی نشان میدهد. در این شکل عابران پیاده و وسایل نقلیه در حال گردش به راست و چﭖ میتوانند از سبز به طور همزمان استفاده کنند. اغلب در شکافهایی که در جریان در حال حرکت در مسیر مخالف به وجود میآید، تخلیه تقاطع از طریق گردش به چﭖ اجازه داده میشود.
شکل ۱. فازهای چراغ راهنما در یک تقاطع
در طراحی فازهای چراغ راهنما، ترتیبی برای فازهای متعددی که به دنبال یکدیگر می آیند مشخص میشود، که ایمنی (جلوگیری از برخورد) و کیفیت خدمات بهبود یابد. توسعه نمودار فازبندی با در نظر گرفتن طرح هندسی تقاطع و خطوط دلخواه حرکت در تقاطع به طور همزمان صورت میگیرد.
وقفه زمانی : بخش یا بخشهایی از یک چرخه که طی آن، علامت چراغ راهنمایی تغییر نمیکند.
بین دو سبز (وقفه تخلیه) : فاصله زمانی بین پایان علامت سبز برای یک فاز و شروع یک علامت سبز برای فاز بعدی را زمان تخلیه گویند. در این دوره چراغ زرد نشان داده میشود و به دنبال آن قرمز می آید. در صورتی که زمان تخلیه محاسبه شده طولانی باشد، به جای آن، از ترکیبی از زرد و یک وقفه تمام قرمز میتوان استفاده نمود.
سطح سرویس (خدمت دهی) یا تابع کارایی : معیاری برای اندازهگیری میزان بهره بری سیستم حمل و نقل که می تواند بر اساس تحرک پذیری تقاطع که به وسیله میزان تاخیر وسیله نقلیه یا کل زمان تلف شده در سیستم تعیین میشود.
۴. تنظیم چراغ راهنما
کنترلکنندههای چراغ راهنما عبارتند از دستگاههای الکترومکانیکی یا الکترونیکی که طول زمان و توالی علامتها را در یک تقاطع تنظیم می کنند. این کنترل کننده ها به چندین دسته تقسیم میشوند:
الف. کنترل کنندههای ثابت : این دسته از وسایل کنترلی برای حرکتهای خاص ترافیکی، زمان ثابتی در نظر می گیرند. زمانبندی بر اساس الگوهای جریان ترافیک تقاطع در گذشته صورت می گیرد.
ب. کنترل کنندههای قابل تنظیم: این گروه از تجهیزات قادر به دریافت اطلاعات درباره الگوهای جریان ترافیک از دستگاههای اندازهگیری مختلف در فواصل زمانی از پیش تعیین شده میباشند. از این اطلاعات برای انتخاب یکی از چند برنامه زمانبندی که در حافظه کنترل کننده قرار دارد، استفاده میشود.
ج. کنترل کنندههای متغیر: این نوع از ابزارهای کنترلی نیز از تعدادی دستگاههای شناسگر برای تغییر طول یا توالی نشانههای چراغ راهنما استفاده می کنند. اما بر خلاف کنترل کنندههای قابل تنظیم، آنها نسبت به ورود هر وسیله نقلیه به تقاطع عکس العمل نشان میدهند، نه تغییر در الگوهای تجمعی ترافیک.
هدف در این قسمت بررسی آلگوریتمهایی است که زمانهای بهینه چراغراهنما برای کنترل کنندههای ثابت ارائه نماید . برای این کار فرم کلی زیر را در نظر می گیریم:
جایی که بردار پارامترهای کنترلی شبکه، تابع کارایی سیستم متناظر با بردار کنترلی و میزان جریان f است. f * نیز جریان تعادلی شبکه است. در حل این مساله ساده سه بحث مطرح است :
١ : شناخت تابع کارایی شبکه حمل و نقل ٢ : تعبیر جریانهای تعادلی
٣ : چگونگی ارتباط مساله تعادل با مساله تنظیم به طور کلی اساس هر الگوریتم تنظیم چراغ راهنما و هدف نهایی مدیریت سیستم بالا بردن یک معیار
کارایی است. با توجه به پدیدههایی که از دید مدیریت سیستم مهم تلقی میشود میتوان به تابع کارایی سیستم دست یافت. سه ایده پرکاربرد برای تعریف تابع کارایی به شرح زیر است:
الف. میزان تاخیر یا انتظار در سیستم: این پارامتر به ازای مقادیر مختلف پارامترهای کنترل و مقادیر مختلف میزان کاربران شبکه تعریف میشود. این مقدار به ندرت با آزمایش عملی و جمعآوری داده های آماری قابل محاسبه است. در عوض با آزمایشهای شبیهسازی میتوان این مقادیر را با صرف مدت زمان معقول به دست آورد.
ب. به دست آوردن ترکیب خطی وزندار از میزان تاخیر در یالهای شبکه و تعداد ایستها پشت چراغهای قرمز: این کمیت نیز مانند کمیت سابق بر اساس برنامههای شبیه سازی قابل محاسبه است . این معیار که از مقبولترین معیارهای کارایی است در مدل ترافیکی " TRANSYT " که توسط رابرتسون ١ در ١٩٦٩ ارائه گردید، به کار گرفته شده است. فرم ریاضی این تابع به صورت زیر است.
در این تابع W و K نماد درجه اهمیت انتظار در یالها و تعداد ایستها در پایانه یالهاست. همچنین مقادیر مشابه برای فاز هستند . بردار نیز نماینده پارامترهای کنترل شبکه و و به ترتیب نمایش بردار میزان جریان در شبکه، میزان انتظار و تعداد ایست در فاز است.
ج. زمان کل مسافرت: این گونه تعریف از تاب ع کارایی در ۳۸۹۱ توسط مارکوتی پیشنهاد شد و دارای فرم ریاضی زیر است.
در این تابع Ce هزینه پیمایش یال و a فاز متناظر به یال e است.
حسن اساسی این تابع آن است که به صورت تحلیلی قابل محاسبه است و میتواند در الگوریتمهایی که از روشهای کلاسیک استفاده میکنند، مورد استفاده قرار گیرد.
د. تعداد افراد منتظر در صف: وی ٢ در ٢٠٠٠ ایده ای مبتنی بر نظریه صف برای بیان تابع کارایی سیستم مطرح نمود. بر اساس این پیشنهاد چنانچه به ترتیب، تعداد افراد منتظر در صف فاز i ام در تقاطع n ام و میزان انتظار متناظر باشد، در این صورت تابع کارایی به صورت مجموع منتظرین در صف تعریف میشود و داریم:
از سوی دیگر در مساله تنظیم چراغ راهنما چندین سوال میتواند مطرح شود: مدت زمان چراغ سبز برای هر فاز چقدر باشد؟
مدت زمان چراغ راهنما در ساعتهای اوج و غیر اوج به چه ترتیبی تغییر میکند؟ طول یک دور هر کدام از چراغهای راهنمای شبکه چقدر باشد؟
ترتیب فازهای چراغ راهنما چگونه بایستی طراحی شود؟
توالی زمانهای بین دو چراغراهنمای پشت سر هم چگونه باشد تا کاربر دچار ایستهای پیاپی پشت هر کدام از اینها نشود؟
جواب دادن به این سوالها و سوالهای مشابه به طور همزمان تحت یک برنامهریزی ریاضی کار آسانی نیست. لذا در این مقاله ما سوال اول را به شرط ثابت بودن سایر موارد پاسخ خواهیم گفت. به علاوه توجه داریم که اگر مدت زمان بهینه چراغ راهنما معلوم باشد، با توجه به سرعت مجاز در هر یال با قدری مسامحه و اندازه ای تقریب میتوان چراغهای پشت سر هم را به نحوی تنظیم کرد که به مشکل ایستهای متوالی گرفتار نیاییم.
بیش از این ترتیب فازهای واقع در یک چرخه را ثابت می انگاریم.
به طور کلی سه دسته آلگوریتم برای تنظیم چراغهای راهنما با توجه به ساختار مدل چراغ راهنما در دست است. دسته اول الگوریتمهای ابتکاری (ابر مکاشفهای ١) است. اولین و مهمترین دلیل استفاده از این آلگوریتمها نامحدب بودن تابع کارایی شبکه است. این آلگوریتمها اکثراﹰ بر روی مدلهای شبیه سازی به کار گرفته میشوند و به آنها بهینهسازی-شبیهسازی گفته میشود. دسته دوم آلگوریتمهای تحلیلی کلاسیک است که از جهت یافتن بهینه موضعی تضمینهای مناسبی در اختیار می گذارند. این الگوریتمها یا اساساﹰ بدون استفاده از مشتقگیری کار میکنند ویا اگر ذاتاﹰ از مشتق گیری استفاده میکنند، به فرمهای مشتق گیری عددی تقلیل مییابند. دسته سوم آلگوریتمهایی هستند که بر روی مدلهای با متغیرهای صحیح کار میکنند. این گونه مسائل معمولاﹰ در مدلسازیهای پویا به وجود میآیند. اگر بتوان آلگوریتمهای شبکه را بر روی این گروه از مسائل به کار برد، ارجحیت دارد و الا از روشهایی مانند شاخه و کران یا شمارش ضمنی میتوان برای حل مساله استفاده نمود. ما در اینجا با استفاده از یکی از روشهای موجود در دسته دوم به نام روش تندترین شیب که از سوی مهندسین حمل و نقل بیشتر مورد استفاده قرار گرفته است، زمانهای بهینه چراغ راهنما را تنظیم مینماییم. این آلگوریتم نخست به وسیله مولف و محقق بزرگ شفی و همکارش پاول ١ در ١٩٨٣ ارائه شد و در ادامه به وسیله کاسکته و همکارانش در ١٩٩٨ و لی و ماشمهل در ١٩٩٩ به کار رفت . اگرچه این آلگوریتم تضمینی برای پیدا کردن کمینه سراسری ندارد، لیکن در بدترین حالت کمینه موضعی را مییابد . اساس این روش به کارگیری رابطه بازگشتی زیر است:
جایی که تابع معیار کارایی شبکه است
مهمترین نکته در پیادهسازی این آلگوریتم نحوه محاسبه مشتق زیر است.
جایی که میزان تغییر در تابع کارایی در فاز b نسبت به تغییر در پارامتر کنترلی است.
به فرض آنکه مدت زمان چراغها از یکدیگر مستقل باشند، فقط برای a = b بخش دوم مقدار غیر صفر خو اهد داشت و لذا داریم
جایی که b ,a نمایش دو یال شبکه متناظر با دو فاز مساله باشند.
از آنجا که z (b ) ممکن است، دارای مشتق ناپیوسته در تعدادی متناهی از نقاط باشد، لذا گرادیان به صورت تفاضل متناهی روی نقاط گسسته محاسبه میگردد. در محاسبه مقدار فوق سختترین قسمت محاسبه مقدار نرخ تغییرات جریان تعادلی روی یالa با توجه به مقدار زمان چراغراهنما روی یال b یعنی است که به صورت تحلیلی غیر قابل محاسبه است.
برای محاسبه این مشتق به روش عددی شفی و پاول پیشنهاد کردند که مقدار زمان چراغ سبز در هر فاز قدری آشفته شود و یک مساله تخصیص تعادلی کامل برای هر آشفتگی حل گردد. در این صورت اگر مقدار جریان تعادلی اولیه روی کمان باشد و زمان چراغ سبز در پایانه کمان b به اندازه تغییر کند و بر اساس آن جریان تعادلی جدید روی کمان a به صورت درآید. در این صورت مشتق جزئی با عبارت زیر محاسبه می گردد:
لذا در هر گام آلگوریتم در محاسبه جهت نزول بایستی برای هر دو فاز مستقل یک مساله تخصیص تعادلی حل شود . (به این عمل تحلیل حساسیت نیز گفته می شود .) لذا این طرح فقط برای شبکه های کوچک قابل اجراست و برای شبکههای بزرگ غیر عملی است.
یک گرفتاری نسبتاﹰ متفاوت در محاسبه محاسبه عددی است که لازمه آن تقریبی مـشابه عبارت زیر است .
با توجه به این گرفتاریها در محاسبه گرادیان به این روش، به کارگیری روش کاملاﹰ عددی ذیل مناسبتر به نظر میرسد که توسط سیپریانی در ۴۰۰۲ به کار گرفته شده است . در این دیدگاه جدید قرار میدهیم:
بحث اساسی دیگر در این قسمت روی اندازه پای حرکت دور میزند. برای تخمین طول گام آلگوریتمهای گوناگونی وجود دارد. استفا ده از روشهای جستجوی تکبعدی نظیر جستجوی طلایی و یا فیبوناچی، پیشنهاد ارزنده ای است. قاعده کاهش طولگام به صورت متوالی، که در آن طول گام ثابتی در تکرارهای متوالی با فاکتوری معین کم و کمتر می شود، نیز برای این مساله به کار برده شده است . نقص اساسی این روش آن است که کاهش طول گام مستقل از مقدار فعلی تابع هدف است . این پدیده موجب میشود که سرعت کـل آلگوریتم پایین بیاید و موجب میشود که حتی در یک کمینه موضعی ضعیف توقف صـورت گیـرد. یـک آلگوریتم که امید میرود کارایی بهتری داشته باشد بر اساس قانون آرمیجو ١ توسعه یافته است. این تکنیک به
صورت زیر مطرح میگردد .
برای اسکالرهای ثابت طول گام i امین تکرار آلگوریتم از رابطه زیر به دست می آید:
جایی که mi نخستین عدد صحیح نامنفی است که عبارت زیر را بر آورده سازد.
جاییکه جهت نزولی بهبود بخش در مرحله k ام باشد.
از آنجا که مساله حداقل سازی است، لذا در صورتی بهبود بخش ارزیابی میشود که داشته باشیم:
. مخصوصا اگر این شرط به بهترین نحو تامین است. در این صورتتعبیری که از قانون آرمیجو به دست میآید بدین صورت است که همیشه مقدار تابع هدف در طول تکرارهای متوالی حداکثر به اندازه کنترلشدهای از مقدار قبلی میتواند تجاوز نماید، به امید آنکه در تکرارهای بعدی بهبود بیشتری حاصل شود.
برای انتخاب مناسب ترین مقادیر برای پارامترهای الگوریتم توجه داریم که تـاثیر اساسـی در تعـداد تکرارهای آلگوریتم دارد. در حالی که به طور وارون وابستگی به دقت جواب نهایی دارد.
یک طرح آلگوریتمیک برای مساله تنظیم چراغ راهنما به شکل زیر ارائه میشود.
آلگوریتم ١ . بهینهسازی زمانهای چراغراهنما
گام ١. (آمادهسازی) قرار دهید k = 0 و s را به عنوان طول گام و به عنوان کران توقف ثابت بگیرید . یک بردار چراغ راهنمای شدنی گرفته و با تخصیص تعادل کاربر، شار برای یالهای شبکه یافته و مقدار تابع هدف را تایین کنید.
گام ۲. (محاسبه جهت نزول) قرار دهید . k k 1 جهت عکس بردار گرادیان تابع هدف z را به صورت عددی و با کمک به کارگیری تخصیص تعادلی کاربر برای هر یال a بر اساس رابطه زیر به دست آورید:
جایی که مقدار تابع هدف به ازای بردار چراغ راهنمای و نیز مقدار تابع هدف متناظر با
تغییر کوچک در aامین مولفه بردار چراغ راهنما یعنی بردار است
گام ۳. (محاسبه طول گام) اعداد را ثابت بگیرید. طول گام به وسیله فرمول به دست می آید. جایی که mi نخستین عدد صحیح نامنفی است که در عبارت زیر صدق نماید:
گام ۴. (محاسبه جواب جدید) جواب جدید از رابطه زیر به دست میآید:
به شرطی که
گام ۴. (به هنگام کردن تابع هدف) با تخصیص تعادل کاربر با بردار جدید مقدار جدید تابع هدف یعنی را بیابید.
گام ۵. (آزمون همگرایی ) اگر در این صورت توقف کنید و الا به گام ۲ بازگردید.
۵. فرمول بندی مساله ترکیبی تنظیم چراغ راهنما و تخصیص ترافیک به صورت شبکه
در این قسمت با استفاده از ایده اساسی برنامهریزی دو سطحی راهبردی برای مساله ترکیب ارائه می گردد. به عبارت دیگر در لایه بیرونی به کمک یکی از آلگوریتمهای بهینهسازی نظیر آلگوریتم تندترین شیب پارامترهای کنترلی مساله با توجه به جریانهای داده شده، بهینه میشوند. سپس در لایه درونی با داشتن مقادیر ثابت پارامترهای کنترلی جریانها روی کوتاهترین مسیرها انتقال مییابند و مجدداﹰ میزان بهینه جریانها به لایه بالایی گزارش میشود و آلگوریتم تا حصول همگرایی ادامه مییابد. برای پیاده سازی تاخیر پشت چراغهای قرمز نیز از یک تبدیل شبکهای ساده بهره برده میشود. برای بیان این نوع از تبدیل به مثال زیر توجه شود.
شکل ۲. شکل سمت راست یک تقاطع چهار خیابانی و شکل سمت چﭖ شبکه متناظر با آن را نمایش می دهد.
در این شکل یک تقاطع چهار خیابانی که خیابان سمت راست آن یک طرفه و سایر خیابانهای آن دو طرفه است و نیز گراف متناظر با آن دیده میشود.
با توجه به زمانهای چراغ راهنما هم میتوان به صورت بدترین حالت، طول هر کمان متناظر را به اندازه طول دوره قرمز بودن در نظر گرفت. یعنی به این صورت فرض کرد که همیشه وقتی راننده به تقاطع میرسد که فاز دلخواه او تازه قرمز شده باشد. همچنین میتوان با به کار گیری یک متغیر تصادفی نمایی به شکل کاراتری این زمان را پیادهسازی نمود . در این مقاله برای سادگی از روش اول بهره برده میشود.
با به کار گیری تبدیلی مانند آنچه در فوق ارائه شد، شبکه خیابانهای شهری به یک شبکه مظروف تغییر شکل میدهد که در آن برخی از نقاط تولید کننده جمعیت خاص (به تعبیر ما یک محموله خاص) هستند که باید به برخی نقاط خاص دیگر با کمترین هزینه ( مثلاﹰ کمترین زمان ممکن ) منتقل شوند. بدین صورت یک فرم از مساله کلاسیک چند محموله ای به دست آمده است.
۶. مقدمهای بر مساله کمترین هزینه چند محمولهای کلاسیک
در این نوع مساله شبکه ای را در نظر میگیریم که بیش از یک محموله را از خود عبور میدهد . این پدیده در اکثر مسائل کاربردی در حمل و نقل و مخابرات پیش میآید. اگر به هیچ نحو محمولهها بر روی هم اثر نداشته باشند میتوان به تعداد محموله ها مسایل تک-محموله ای را حل نمود. اما از آنجا که محمولهها در بهرهبرداری از یکسری امکانات شبکه مشترک هستند لذا مساله را نمیتوان به صورت تک محموله ای حل نمود. برای این منظور فرم کلی مساله را برای K محموله به صورت زیر در نظر میگیریم.
در این فرمولبندی اشاره به میزان جریانی از محموله k ام دارد که روی کمان (i, j) در حرکت است. نیز به ترتیب بردارهای جریان و هزینه یک واحد از محموله k ام هستند. به دسته اول قیود، قیود دسته ای و به دسته دوم قیود جریان شبکه گفته می شود. همچنین راحتتر آن است که قیود دسته ای به صورت تساوی درآید. لذا قرار میدهیم:
میزان ظرفیتی از کمان (i, j) که مورد استفاده قرار نمیگیرد. همچنین این مدل ظرفیت را برای یالها در نظر میگیرد نه برای گره ها . بدیهی است که اگر گرهها نیز ظرفیت داشته باشند میتوان از یک کمان مجازی ظرفیتدار به همراه گره مربوطه استفاده نمود. علاوه بر این در این مساله فرضیات زیر را میپذیریم.
فرض شبیه بودن کالاها. به این معنی که هر واحد جریان از هر یک از محموله ها یک واحد ظرفیت هر یال را اشغال مینماید. در کاربرد فعلی در این مقاله این فرض به این معنی است که مساحت اشغال شده توسط هر وسیله نقلیه با سایر وسایط یکسان در نظر گرفته میشود.
فرض عدم تراکم. به این معنا که ظرفیت روی هر کمان ثابت فرض میشود و همچنین هزینه بر روی هر کمان به صورت خطی با میزان جریان روی کمان تغییر میکند. به این معنا که در ساعتهای مختلف به کار گیری شبکه، حجم خیابانها یکسان باقی میماند.
فرض تقسیم ناپذیری کالاها. این فرض بر این موضوع دلالت دارد که متغیرهای جریان نمیتوانند گویا باشند. مثلاﹰ جریان ۵/۳۱ واحد بی معنی میباشد. در حالتهایی که برنامهریزی خطی تقریب خوبی از مدل برنامه ریزی صحیح نباشد با ترکیب آن با روش شاخه و کران میتوان الگوریتمهای کارایی به دست آورد. یک تفاوت اساسی میان مسائل تک محموله و چند محموله ای آن است که در مسائل تک محموله ای چنانچـه همه داده های عرضه و تقاضا و ظرفیتها صحیح باشند متغیر جریان بهینه مساله نیز صـحیح اسـت. در حالیکه در مسایل چند محموله ای این خصوصیت برقرار نیست .
برای سادگی فرض کنیم هر محموله k تنها یک مبدا و یک مقصد داشته باشد ( توجه داریم که شرط برای مساله تخصیص ما برقرار است . زیرا هر نوع از جمعیت از یک نقطه خاص حرکت و قصد رفتن به یک نقطه خاص دیگر دارند.) میزان تقاضای این محموله را فرض می کنیم. همچنین بـرای سادگی فرض کنیم ظرفیت روی محمولهها به صورت انفـرادی نباشـد، یعنـی در اینجـا از آلگوریتمهای نقطه درونی برای حل این مساله سود می بریم. آلگوریتمهای نقطه درونی در پاسخ به نیـاز نسبت به آلگوریتمهایی با زمان چند جمله ای برای برنامهریزی خطی به وجود آمدند. این نیاز وقتی احساس شد که معلوم شد تعداد تکرارهای آلگوریتم سیمپلکس در بعضی از مثالها به صورت نمایی رشد می کند.
نخستین کسی که به این نیاز پاسخ مثبت داد خاشیان ١ با ارائه آلگوریتم بیضوی بود. لیکن از جهت محاسباتی آلگوریتم وی یارای رقابت با آلگوریتم سیمپلکس را نداشت. کمی بعدکارمارکار ٢ با استفاده از ایده آلگوریتمهای نقطه درونی که پیش از این در برنامهریزیهای غیرخطی کاربرد داشت، توانست آغازگر یک دسته مهم به نام آلگوریتمهای نقطه درونی برای مساله برنامهریزی خطی و همچنین برای برنامهریزی محدب شود. خصوصیت کلی این روشها رشد کند تعداد تکرارها بر اساس بالارفتن اندازه مساله برخلاف روش سیمپلکس است. این خصوصیت استفاده از این روش بر روی مسایل بزرگ مقیاس مانند مسایل طراحی شهری، هموار میسازد و آن را به عنوان جانشینی کاراتر از سیمپلکس مطرح مینماید. آنچه در ادامه این بخش می آید، نحوه پیادهسازی این دسته از آلگوریتمها روی مسایل شبکه از جمله مساله چند محمولهای است که تحقیقات عمده روی آن مربوط به رسنده و ویگا ١ در دهه ۰۹۹۱ است. ما در اینجا به تحلیل روی آلگوریتم دوگان آفین مقیاس شده ( DAS ٢) خواهیم پرداخت. این آلگوریتم نخستین روش نقطه درونی بود که از جهات محاسباتی با آلگوریتم سیمپلکس قابل مقایسه شد. برای پیادهسازی این آلگوریتم فرض کنیم A ماتریسی m.n و c ، u و x بردارهای n تایی و b یک بردار m تایی باشند. در این صورت آلگوریتم
