بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه ي یک مدل بهینه سازي و براي زمان بندي قطارهاي مترو: مطالعه ي موردي متروي تهران
چکیده
زمانبندي بهینهي حرکت قطارهاي مترو با توجه به هزینههاي بالاي بهرهبرداري و همچنین نیاز به سوق دادن تقاضاي حملونقل به سوي حملونقل عمومی، از اهمیت بسیار بالایی برخوردار است. در تحقیق پیش رو مسأله زمان بندي حرکت قطارهایی که در آنها تقاضاي مسافر به صورت پویا میباشد به طور عام و مسأله زمانبندي حرکت قطارهاي مترو به طور خاص مورد بررسی قرار گرفتهاست. هدف اصلی در این مسأله کمینه کردن زمان انتظار مسافران در ایستگاهها میباشد. کاربرد اصلی این نوع مسائل در برنامه ریزي قطارهاي مترو است. این مسأله در این مقاله به صورت یک مدل بهینهسازي ریاضی فرموله و در ادامه یک روش شاخهزنی محلی براي حل مسأله مورد بررسی، طراحی و پیادهسازي شدهاست. جهت بررسی قابلیت و اثر بخشی مدل ارائه شده، یک سري مثال شبیهسازي شده و همچنین یک مثال موردي در ابعاد خط 2 متروي تهران مورد بررسی قرار گرفتهاست. نتایج پیاده سازي و حل مدل براي مثال موردي در ادامه آورده شده و قابلیت و اثربخشی مدل به نمایش در آمده است.
کلید واژه: زمان بندي حرکت قطارها، متروي تهران، الگوریتم شاخه زنی محلی، مدلسازي ریاضی
1 مقدمه
حمل و نقل ریلی به طور کلی شامل انتقال مسافر یا بار یا انتقال هم زمان آنها توسط راهآهن میگردد. از آنجایی که ضریب اصطکاك میان آهن و آهن در شبکهي ریلی از ضریب اصطکاك چرخ و جاده در شبکهي جادهاي بسیار پایین تر است، حمل و نقل مقدار مشخصی از بار یا تعداد مشخصی مسافر در شبکهي ریلی بسیار کمهزینهتر از شبکهي جادهاي است. بنابراین، حمل و نقل ریلی را میتوان به عنوان کاراترین سیستم حملونقل زمینی از لحاظ مصرف انرژي به حساب آورد.[1] با این وجود حمل و نقل ریلی نیازمند سرمایهگذاري بسیار بالاتري نسبت به شبکهي حمل و نقل جادهاي است؛ چرا که هزینهي ساختوساز و نگهداري و تعمیرات در راهآهن بسیار بالاتر است. به همین دلیل بهبود در سیستمهاي ریلی منجر به صرفهجویی سرمایهاي بالایی خواهد شد.
برنامه ریزي در شبکههاي ریلی شامل زیرمسألههاي گوناگونی میشود که به عنوان نمونه میتوان به مسائل پیشبینی تقاضا، طراحی شبکه، طراحی خصوط، زمانبندي حرکت قطارها، برنامهریزي وسایل نقلیه و زمان بندي خدمه اشاره نمود.
مسأله اصلی مورد بررسی در این مقاله، زمانبندي حرکت قطارها و علیالخصوص زمان بندي حرکت قطارها در فضاي تقاضاي مسافري پویا میباشد که با شبکههاي مترو تطابق دارد.
1-1 بیان مسأله
هدف مسأله زمانبندي حرکت قطارها تعیین یک برنامه زمانبندي براي یک مجموعه قطار است که با توجه به محدودیتهاي ظرفیت شبکه تعیین شدهاست و هم چنین یک سري محدودیتهاي عملیاتی را نقض نمینماید.[2] این مسأله از ابعاد مخالفی تقسیمبندي و مورد بررسی قرار گرفتهاست. مسأله مورد بررسی در مقالهي پیش رو به زمان بندي حرکت قطارها در شبکههاي ریلی با تقاضاي مسافري پویا و به طور خاص مترو مربوط است. هدف اصلی در این مسأله به دست آوردن زمان اعزام قطارها از هر ایستگاه، زمان رسیدن قطارها به هر ایستگاه و زمان توقف در هر ایستگاه میباشد. این زمانها بایستی با توجه به محدودیتهاي مانور و اعزام (حداقل سرفاصله زمانی بین اعزام دو قطار متوالی)، محدودیتهاي سرعت (حداقل و حداکثر سرعت) و سایر محدودیتهاي عملیاتی، با هدف کمینه کردن زمان انتظار مسافران در ایستگاه براي سوار شدن به قطار تعیین شوند. از آنجایی که با شبکهي مترو مواجه هستیم، محدودیتهاي مربوط به سبقت و تلاقی موضوعیتی نخواهند داشت چرا که در شبکههاي مترو اکثرا قطارها از یک جنس بوده و همچنین در ایستگاهها امکانات زیرساختی براي تلاقی و یا سبقت دو قطار وجود ندارد.
2-1 اهمیت و اهداف مسأله
حجم بالاي مسافرانی که از مترو استفاده میکنند از یک سو و هزینههاي هنگفت بهرهبرداري از شبکه ریلی درونشهري از سوي دیگر موجب گردیدهاست تا صرفهجویی اندکی در زمان مسافران باعث گردد مسافران بیشتري ترغیب به استفاده از این وسیلهي حمل و نقل عمومی گردند که این امر علاوه بر این که منجر به سودآوري بیشتر براي شرکت بهرهبردار خواهد شد، به ارتقاي فرهنگ استفاده از وسایل حمل و نقل عمومی و نتیجتاً آلودگی کمتر هوا، کاهش ترافیک و بسیاري مزایاي دیگر نیز خواهد انجامید.
در حال حاضر زمانبندي حرکت قطارهاي متروي تهران به این صورت است که ابتدا سرفاصلههاي زمانی توسط کارشناسان تعیین گردیده و زمان بندي به صورت دستی (با ابزار کامپیوتر) انجام میپذیرد. در این فرایند امکان اشتباه انسانی و اعمال نظرات شخصی بسیار بالاست، لذا پیاده سازي یک سامانهي برنامه ریزي حرکت قطارها که تعیین سرفاصلههاي زمانی و همچنین زمان اعزام و قبول و توقف قطارها در ایستگاهها را مشخص کند میتواند کمک شایانی به بهرهبردار در جهت ارتقاي سطح خدمت ارائهشده و در نهایت رضایت بالاتر مسافران بنماید.
3-1 مروري بر منابع
در این بخش کارهاي ارائه شده در حوزهي زمانبندي حرکت قطارها و به خصوص در حوزهي زمانبندي حرکت قطارها با تقاضاي مسافري پویا و زمانبندي قطارهاي شهري و مترو مورد بررسی قرار میگیرد. از آنجایی که رویکرد اصلی در این مقاله مدلسازي ریاضی میباشد، مواردي از ادبیات موضوع انتخاب شده و مورد بحث قرار گرفتهاند که رویکرد مشابه این مقاله داشتهاند.
هیگینز و همکاران [3] در مطالعهخود به زمانبندي حرکت قطارها در یک محور یکخطه با در نظر گرفتن محدودیتهاي سبقت و طلاقی و کمینهي سرفاصلهي زماني بین اعزام دو قطار میپردازند. در این مدل متغیرهاي تصمیم به صورت پیوسته در نظر گرفتهشدهاند. جهت حل مدل ارائهشده، یک روش شاخه و کران3 پیادهسازي شدهاست. کاپرارا و همکاران [2] در مدلی که ارائه میدهند، زمانبندي قطارها در یک محور یکخطه را مورد بررسی قرار میدهند. در این مدل علاوه بر در نظر گرفتن محدودیتهاي سبقت و طلاقی و کمینهي سرفاصلهي زمانی بین دو اعزام متوالی، محدودیتهاي قطارهاي از پیش برنامهریزي شده و همچنین محدودیت مسدودي خط به دلیل نگهداري و تعمیرات لحاظ گردیده است. زمانها در این مدل به صورت گسسته در نظر گرفته شدهاند و جهت حل مدل ارائهشده یک روش لاگرانژ طراحی و پیاده سازي شدهاست. ژو و ژانگ [4] زمانبندي حرکت قطارها را در فضاي زمانبندي پروژه با محدوديت منابع (RCPSP4) مدلسازي نمودهاند. محققان جهت حل مدل خود یک روش شاخه و کران ارائه دادهاند. یک مدل زمان بندي حرکت قطارها، با استفاده از فضاي مسأله زمانبندي کارگاهی5 توسط شفیعا و همکاران [5] ارائه شده است.
در هیچکدام از مدلهایی که تا کنون مورد بررسی گردید الگوي تقاضاي مسافري به عنوان یک عامل تأثیرگذار بر تصمیمگیري مورد بررسی قرار نگرفتهاست. در زیر به بررسی تعدادي از تحقیقات انجام شده که در آنها تقاضاي مسافري به عنوان یک عامل مهم تصمیمگیري مورد بحث قرار گرفتهاست آورده میشود. این مدلها اغلب به دلیل این که براي شبکههاي مترو طراحی گردیدهاند محدودیتهاي سبقت و طلاقی لحاظ نشده است.
کانکا و همکاران [6] در پژوهش خود یک مدل زمانبندي عددصحیح غیر خطی براي مسأله زمانبندي حرکت قطارها با تقاضاي مسافري متغیر ارائه میدهند. در این پژوهش تاثیر انتخاب توابع هدف بر برنامهي خروجی نیز مورد بررسی قرار گرفته است. بارنا و همکاران [7] یک مدل زمانبندي حرکت قطارها در شرایط تقاضاي مسافري پویا ارائه میدهند. هدف اصلی در این مدل کمینه کردن میانگین زمان انتظار مسافران میباشد. جهت حل مدل پیشنهادي، یک الگوریتم شاخهوبرش ارائه گردیدهاست. سان و همکاران [8] براي زمانبندي حرکت قطارهاي مترو با در نظر گرفتن تقاضاي مسافري یک مدل ریاضی ارائه دادهاند. در این پژوهش جهت به دست آوردن اطلاعات تقاضاي مسافري از دادههاي سیستمهاي اتوماتیک جمعآوري کرایه استفاده شدهاست.
-2 مدل ریاضی
مدل ارائهشده در این مقاله بر پایه مدل ارائه شده در [7] میباشد. هدف اصلی در این مدل کمینهسازي میانگین زمان انتظار مسافران است. با توجه به حجم بالاي تقاضاي مسافران در مترو و این موضوع که این حجم از پیش قابل تعیین نیست، استفاده از این مدل جهت کاهش زمان انتظار مسافران منطقی به نظر میرسد .
اغلب مدلهاي معمول در ادبیات موضوع، از متغیرهاي صفر و یک جهت نمایش زمان اعزام قطارها استفاده میکنند اما این امر در اغلب موارد به غیر خطی شدن مدل منجر میشود. در مدل ارائه شده توسط بارنا متغیرهاي جریان معرفی شدهاند که باعث میشوند مدل در حالت خطی باقی بماند.
در زیر به بررسی نمادهاي ریاضی بهکاررفته در مدل ارائه شده میپردازیم و سپس مدل ارائه میگردد. S 1,..., n مجموعه مرتبی از ایستگاه هاست که یک راه آهن دوخطه را نمایش میدهد. افق زمانی مورد مطالعه در مسأله به بازههاي زمانی با اندازه ي شکسته شدهاست. بنابر این لحظه ي زمانی به لحظه زمانی اشاره دارد که واحد زمانی از آغاز افق زمانی گذشته است.
ثابت گسسته سازي زمانی بیانگر طول کوتاهترین زمانی است که در مدل در نظر گرفته میشود.
مقدار تقاضاي مسافري بین ایستگاه هاي در فاصله ي زمانی میباشد.
مدلسازي با این فرض انجام میشود که مقادیر تقاضا در هر بازهي زمانی در دسترس میباشند. این فرمت از دادهها در راهآهنهاي پیشرفتهتر بسیار معمول است. این اطلاعات معمولا از طریق دستگاههایی که در ورودي و خروجی هر ایستگاه نصب میگردند قابل دسترسی هستند و با توجه به شناسهي یکتایی که به هر مسافر تخصیص داده میشود ماتریس مبدأ-مقصد٦ در هر بازهي زمانی قابل تشکیل است. همچنین در صورت عدم دسترسی به ماتریس تقاضاي مبدأ-مقصد میتوان از میزان نسبی تقاضاها در زمانهاي مختلف و ایستگاههاي مختلف نسبت به یکدیگر استفاده کرد.
به ترتیب کمینه و بیشینهي زمان سیر در سیرگاه بین ایستگاههاي i و j میباشد.
این زمانها میتوانند با پیشمحاسبه و در نظر گرفتن زمانهاي شتابگیري و ترمز لحاظ گردند.
کمترین سرفاصلهي زمانی بین حرکت دو قطار متوالی را نمایش میدهد. این مقدار کمترین زمانی است که پس از گذشت آن از اعزام قطاري، مجاز به اعزام قطار بعدي هستیم. w min و w max به ترتیب کمینه و بیشینه زمان توقف در ایستگاه هستند.
در مدل ارائه شده توسط بارنا هدف اصلی تعیین زمان اعزام قطارها از ایستگاهها و همچنین سرعت آنها در سیرگاههاست به نحوي که میانگین زمان انتظار مسافران به کمینهي مقدار خود برسد.
در مدل ارائهشده مجموعهي M 1,..., m قطارهایی را نشان میدهد که امکان اعزام آنها وجود دارد. ذکر این نکته الزامی است که این فرض یک فرض مطلق و قطعی نیست و میتوان مدل را با در نظر گرفتن تعداد اعزام بینهایت نیز حل نمود.
با استفاده از تعاریف فوق مدل ریاضی به صورت زیر تعریف میشود.
به نحوی که
در این مدل ، تابع هدف که در عبارت (1) آمده است، مجموع زمانهاي انتظار مسافران را کمینه میکند. محدودیت (2) مقدار متغیر f it را محاسبه میکند. نحوهي این محسابه به این صورت است که مقدار مسافري که در لحظهي زمانی قبلی در انتظار بودهاند را با تقاضاي جدید که در زمان t وارد میشوند جمع زده و تعداد مسافرانی را که به قطار سوار میشوند را از آن کم میکند. محدودیت (3) یک حد بالا براي مسافرانی که سوار قطار میشوند معین میکند. محدودیت (4) در واقع ترتیب اعزام قطارها را مدیریت میکند. رویهي کار به این صورت است که در صورتی که قطار -k-1ام اعزام شده باشد سمت راست نابرابري برابر یک خواهد شد و در واقع محدودیتی روي زمان اعزام اعمال نمیکند. اما اگر قطار -k-1ام اعزام نشده باشد سمت راست محدودیت برابر صفر خواهد شد و این بدان معناست که مادامی که قطار k-1 اعزام نشده است به مدل این اجازه داده نمیشود که قطار -kام را اعزام کند. بیشینهي تعداد سرویس قطار در دسترس از طریق محدودیت (5 ) در مدل اعمال میگردد. اعمال این محدودیت به صورت کوچکتر یا مساوي به این معناست که میتوان فرایند برنامهریزي را بدون این اجبار که تمامی قطارها استفاده شوند انجام داد. محدودیت (6) تضمین میکند که یک قطار از هر ایستگاه حد اکثر یک بار اعزام میشود. محدودیت هاي (7) و (8) کمینه و بیشینهي زمان رسیدن قطارها به ایستگاههاي انتهایی سیرگاهها را مشخص میکنند.
-3 روش حل پیشنهادي
روش حل استفادهشده در این مقاله روش شاخه زنی محلی7 است. این روش بدون در نظر گرفتن ماهیت دنیاي واقعی مسائل برنامهریزي عدد صحیح به حل آنها میپردازد. این روش براي اولین بار توسط فیسکتی و لودي [9] در سال 2003 مطرح گردید.
در این روش یک نرمافزار حل MIP به عنوان یک ابزار براي اکتشاف فضاي جواب در سطح تاکتیکال به کار میرود و از یک ساختار شاخهزنی در سطح استراتژیک براي کنترل الگوریتم استفاده میشود. در حقیقت این روش به محققان این امکان را میدهد تا تمرکز خود را بر روي گسترش موضوع تحقیقاتی خود قرار دهند و نیازي به صرف زمان بر روي طراحی الگوریتمهاي حل مدل نداشته باشند. با توجه به حجم بالاي مسائل برنامهریزي حرکت قطارها و قابلیت بالاي روش شاخهزنی محلی که توسط پدیدآورندگان آن در ابعاد مختلف مورد بررسی قرار گرفته است و همچنین توانایی بالاي شاخهزنی محلی در حل مسائلی که با متغیرهاي صفر و یک سرو کار دارند، در این مقاله از این روش براي حل مسائل برنامهریزي حرکت قطارهاي مترو استفاده شدهاست. در ادامه ساز و کار این روش بهطور خلاصه توضیح داده خواهد شد.
مدل برنامهریزي ریاضی به شکل زیر را در نظر بگیرید: (12) (13) (14)
که در آن مجموعه ي اندیسها است که به تقسیم میشود که در آن B مجموعه اندیسهاي متغیرهاي صفر و یک است و هیچگاه تهی نمیتواند تهی باشد. مجموعه اندیسهاي G و C میتوانند تهی باشند به ترتیب نشاندهندهي متغیرهاي عدد صحیح و پیوسته هستند.
با در اختیار داشتن یک جواب شدنی مرجع مانند x مسأله عدد صحیح، مجموعه S : j B : x j 1 تعریف می گردد. این مجموعه مشخص کنندهي متغیرهاي صفرویکی است که در جواب مقدار 1 اتخاذ نمودهاند. براي هر پارامتر صحیح مثبت k همسایگی N ( x, k) مربوط به x به صورت مجموعهاي از جوابهاي مسأله تعیین میگردد که محدودیت اضافهي زیر، که آن را محدودیت شاخهزنی محلی مینامیم را ارضا مینمایند:
