نشریه تخصصی مهندسی صنایع، دوره 45، شماره 1، فروردین ماه 1390، از صفحه 103 تا 116 یک مدل زما ن بندي حرکت قطارها با در نظر گرفتن
زمان هاي توقف براي نماز

مسعود یقینی*1 و علی محمدزاده 2
استادیار دانشکده مهندسی راه آهن – گروه حمل و نقل ریلی- دانشگاه علم و صنعت ایران
دانش آموخته کارشناسی ارشد حمل و نقل ریلی- دانشکده مهندسی راه آهن – دانشگاه علم و صنعت ایران
(تاریخ دریافت 24/7/89، تاریخ دریافت روایت اصلاح شده 2/11/89، تاریخ تصویب 23/1/90 )

چکیده
در ایران به دلیل نبود یک مدل جامع براي اعمال محدودیت توقف اجباري براي اداي فریضه نماز، زمان بندي حرکت قطارها به شکل دستی انجام می گیرد. در این مقاله، یک مدل ریاضی براي زمان بندي حرکت قطارهاي مسافري براي محورهاي دوخطه راه آهن با هدف حداقل کردن مجموع تأخیرات قطارها با در نظر گرفتن زمان هاي توقف اجباري براي اداي فریضه نماز ارائه شده است. نوآوري در مدل پیشنهادي، بررسی شرط لزوم توقف در ایستگاه هاي بین راهی داراي نمازخانه، براي قطارهاي مسافري براي اداي فریضه نماز و انتخاب بهترین ایستگاه براي توقف است که باعث ایجاد کمترین تأخیر در مجموع زمان سیر قطارها می شود. براي ارزیابی عملکرد مدل پیشنهادي موضوع نمونه با ابعاد مختلف حل شده است. با ایجاد یک سیستم پشتیبان تصمیم و استفاده مدل پیشنهادي در آن، می توان زمان بندي حرکت قطارهاي مسافري را به صورت مکانیزه انجام داد.

واژه هاي کلیدي: زمان بندي حرکت قطارها، قطارهاي مسافري، محدودیت نماز، بهینه سازي

مقدمه
Email: [email protected] ، 77491030 : نویسنده مسئول : تلفن : 77240117 , فاکس *

امروزه یکی از شاخص هاي توسعه یافتگی کشور ها، میزان رشد و پیشرفت صنعت حمل و نقل آن ها است. در این میان حمل و نقل ریلی با داشتن مزایایی چون امکان حمل و نقل انبوه و ارزان، آلودگی کمتر محیط زیست، مصرف سوخت بسیار کم تر و ایمنی بیشتر جایگاه ویژه اي دارد [1]. با توجه به سرمایه گذاري هاي سنگین براي توسعه حمل و نقل ریلی، استفاده بهینه از امکانات موجود در این صنعت اهمیت شایانی دارد. در این میان زما ن بندي حرکت قطارها1 نقش بسیار مهمی ایفا می کند که مورد توجه راه آهن هاي دنیا است. موضوع زمان بندي حرکت قطار ها با توجه به وجود یک سري محدودیت ها، بهترین برنامه زمانی براي ورود و خروج قطارها به ایستگاه ها را تعیین کند، به طوري که کمترین هزینه را براي مسافران و نیز براي شرکت هاي مسافري داشته باشد. در ایران به دلیل وجود محدودیت توقف اجباري براي اداي فریضه نماز و نبود یک مدل جامع براي برآورده کردن محدودیت ذکرشده، زمان بندي حرکت قطارها توسط کارشناسان به صورت غیر مکانیزه انجام می گیرد.
تا کنون پژوهش گران مدل ها و راه حل هاي متفاوتی را با توجه به شرایط خاص راه آهن ها براي زمان بندي حرکت قطارها ارائه کرده اند. هیگینز و همکاران [2 ] و [3] مدلی براي راه آهن استرالیا ارائه کرده اند. این مدل شامل بلاك هاي یک خطه و دو خطه بوده که با استفاده از الگوریتم ژنتیک2 حل شده است. براي بهینه سازي زمان بندي حرکت قطارهاي باري توسط کراي و هارکر [4] مدل دیگري ارائه شده است. رویکرد آن ها برقراري ارتباط بین برنامه ریزي تاکتیکی و عملیاتی زمان بندي حرکت قطارها است که زمان هاي هدف را براي استفاده در مدل هاي اعزام مستقیم فراهم می کند. مدل به زیر مسئله اي با متغیر پیوسته تبدیل می شود که با الگوریتمی ترکیبی از روش تجزیه و جریان شبکه ها حل می شود.
قصیري و همکاران [5] براي مسئله زمان بندي دو تابع هدف، یکی از دید مسافر (کاهش مجموع زمان سفر) و دیگري از دید شرکت راه آهن (کاهش هزینه مصرف سوخت) در نظر گرفته شده اند. پینگ و همکاران [6] نیز دو تابع هدف را براي مسئله زمان بندي حرکت قطارها در نظر گرفته اند. دو تابع هدف مسئله عبارتند از امید ریاضی زمان انتظار قطارهاي سریع و نیز کل زمان سفر قطارهاي سریع و قطارهاي سرعت متوسط. براي حل مسئله از روش فرا ابتکاري هوش جمعی استفاده شده است. در پژوهش دیگري قصیري و مرشد سلوك [7] مسئله زمان بندي حرکت قطارها را به صورت مسئله فروشنده دورهگرد3 مدل سازي کرده که در آن شهرها به مثابه قطارها هستند و فرض شده است که قطارها فقط از ایستگاه هاي ابتدایی و انتهایی اعزام می شوند. تابع هدف مسئله، حداقل کردن تأخیر قطارها در نظر گرفته شده است و الگوریتم مورچگان4 درصدد یافتن بهترین توالی اعزام قطارها است.
پور سید آقایی [8] مسیر تک خطه تهران – اهواز که شامل 51 بلاك می شود را بررسی کرده است و با کمک روش هاي ابتکاري براي کاهش حجم مسئله به میزانی قابل حل توسط روش هاي دقیق، زمان بندي بهینه این مسیر به دست آمده است. آریانو و همکاران [9] یک شبکه را ه آهن را با استفاده از شیوه زمان بندي کارگاهی مدلسازي کرده و با روش شاخه و حد حل کرده اند. کوزان و باردت [10] در مطالعه خود بار دیگر از روش زمان بندي کارگاهی5 استفاده کرده اند. لی و چن [11] با استفاده از یک الگوریتم فرا ابتکاري مسئله زمان بندي قطار ها و مسیر یابی قطار ها6 را به شکل ترکیبی حل کرده اند.
جو و جونگ [12] یک مدل ریاضی براي راه آهن هاي یک خطه براي کمینه کردن زمان کل سفر پیشنهاد کرده اند. در این مقاله یک مدل ریاضی مبتنی بر زمانبندي پروژه با منابع محدود و با اعمال محدودیت هاي ظرفیت ایستگاه و خط ارائه شده است.
در یکی از جدیدترین مقالات ارائه شده توسط کاستیلو و همکاران [13] یک مسئله زمانبندي حرکت قطارها براي شبکه هاي با خطوط یک خطه و خطوط یک خطه و دوخطه به صورت مخلوط مورد بررسی قرار گرفته است.
هدف مسئله مورد بررسی، کمین کردن زمان سیر قطارهایی بوده که طولانی ترین زمان هاي سفر را داشته اند.
یکی از تکنیک هاي پرکاربرد در زمینه زمانبندي حرکت قطارها، تکنیک شبیه سازي است که در ادامه به برخی از کارهاي مهم انجام شده در این زمینه می پردازیم.
در یکی از جدید ترین تحقیقات انجام شده توسط مورالی و همکاران [14] از روش شبیه سازي براي تخمین زمان تأخیر قطار ها استفاده شده است.
شلک [15] یک چارچوب جدید براي استفاده یکپارچه ازمدل هاي بهینه سازي و شبیه سازي براي زمانبندي حرکت قطارها ارائه کرده است. در روش ارائه شده، هدف، استفاده بهینه از ظرفیت خطوط شبکه راه آهن است. کو و همکاران [16] یک مدل مبتنی بر جریان شبکه چند کالایی براي زمانبندي قطارهاي باري ارائه کرده اند. هدف مدل، کمینه کردن هزینه هاي عملیاتی است. در این مقاله یک الگوریتم مبتنی بر تولید ستون براي حل مدل ارائه شده، پیشنهاد شده است. الگوریتم ارائه شده در یک چارچوب مبتنی بر شبیه سازي عمل می کند.
همچنین مقالات متعددي درباره استفاده از تکنیک شبیه سازي براي تعیین سبقت و تلاقی قطارها ارائه شده است که می توان به چنگ [17] اشاره کرد. در فعالیت هاي پترسن و تیلور [18] و دورفمن و مدانیک [19] از تکنیک شبیه سازي براي ارزیابی تاخیرات قطارها استفاده شده است.
استفاده از تکنیک شبیه سازي اغلب براي تحلیل و ارزیابی برنامههاي زمانبندي و مشخص کردن برخورد قطارها است. اما مدل ریاضی براي تصمیم گیري درباره رفع برخورد قطارها و تعیین بهترین حالت تلاقی و سبقت قطارها استفاده می شود.
موضوع زمانبندي حرکت قطارها به عنوان یک مسئله NP-Hard شناخته می شود که امکان به دست آوردن جواب بهینه براي مسائل پیچیده و با ابعاد بزرگ وجود ندارد. [20] و [21] .
تا کنون در زمینه مدلسازي ریاضی، مسئله زمان بندي حرکت قطارها با در نظر گرفتن محدودیت توقف بین راهی براي نماز پژوهش هاي بسیار محدودي انجام شده است. بر اساس بررسی هاي انجام شده توسط نویسندگان مقاله، تنها تحقیقی که به این موضوع پرداخته است، مطالعه خادم ثامنی [22] است. خادم ثامنی یک مدل ریاضی زمان بندي حرکت قطار ها ارائه کرده که در آن قطارها براي اداي فریضه نماز در اولین ایستگاه نمازخانه داري که می توانند براي نماز توقف داشته باشند، توقف خواهند کرد. در پژوهش خادم ثامنی فقط سعی شده است که
محدودیت توقف بین راهی براي نماز برقرار باشد، بنابراین قطارها در اولین ایستگاهی که ممکن باشد، براي اداي فریضه نماز توقف می کنند و نه در بهترین ایستگاه ممکن که زمان کل سفر ها را کمینه کند. اما در مدل ارائه شده در این مقاله، محدودیت توقف اجباري در بین مسیر براياداي نماز طوري طراحی شده است که ایستگاه انتخابیبراي توقف قطار براي نماز، باعث ایجاد کم ترین تأخیر درمجموع زمان سفر همه قطار ها شود. به تعبیر دیگر اینمدل، ایستگاه بهینه را براي توقف براي نماز انتخاب می کند.
زمانبندي حرکت قطارها یکی از مهم ترین فعالیت هاي برنامه ریزي در راه آهن محسوب می شود [1]. در صورت وجود یک مدل جامع در زمینه زمانبندي حرکت قطارها و ایجاد یک سیستم پشتیبان تصمیم، راه آهن جمهوري اسلامی ایران می تواند، زمانبندي حرکت قطارها را به صورت کامپیوتري و خودکار انجام دهد.
در ادامه، مطالب ارائه شده در مقاله به این صورت سازماندهی شده است: در بخش دوم، مسئله زمان بندي حرکت قطارها و فرضیه هاي در نظر گرفته شده در مطالعه حاضر بیان می شود. در این بخش به توضیح محدودیت توقف اجباري براي اداي فریضه نماز پرداخته شده است. سپس مدل ریاضی پیشنهادي مسئله زمان بندي حرکت قطارها با توجه به محدودیت نماز در بخش سوم مقاله بیان شده است. در بخش چهارم یک مثال با ابعاد کوچک به صورت مشروح و 11 مسئله نمونه ارائه و حل شده است. در انتهاي مقاله، بخش نتیجه گیري و ارائه پیشنهاد هایی براي مطالعات بعدي در نظر گرفته شده است.

بیان مسئله
یک محور دو خطه راه آهن را در نظر بگیرید، این محور شامل چندین ایستگاه است. در این محور یک مسیر اختصاص به قطار هاي رفت و یک مسیر اختصاص به قطار هاي برگشتی دارد، مانند یک بزرگراه که همه وسایل نقلیه فقط در یک مسیر اجازه حرکت دارند. در این مسئله همه قطار ها، ایستگاه هاي مبدا و مقصد مشخصی دارند.
براي همه قطارها زودترین و دیرترین زمان شروع به حرکت از مبدا، از پیش مشخص شده است. به این معنی که قطارها نمی توانند خارج از بازه زمانی مورد نظر، ایستگاه مبدا را ترك کنند. همچنین زمان طی بلاك ها توسط قطارها، با توجه به مشخصات ناوگان و مشخصات خط، از پیش تعیین شده است. این مسئله با فرض امکان متغیر بودن سرعت قطارها در بلاك ها در نظر گرفته شده است. همچنین مدت زمان توقف هاي اجباري و از پیشتعیین شده هر قطار، در ایستگاه هاي عبوري مسیر خود مشخص است. محدودیت دیگر، موضوع تلاقی قطارها است. طبق قوانین راه آهن ایران، هر بلاك، حداکثر توسط یک قطار می تواند اشغال شود و امکان وجود دو قطار در یک بلاك به طور هم زمان وجود ندارد. مهم ترین محدودیتی که در مدل پیشنهادي ارائه شده است، محدودیت توقف براي اداي فریضه نماز است، بدین معنی که قطار ها موظف اند، در بازه هاي مجاز هر وعده نماز، در صورتی که لزوم توقف براي نماز مشخص شود، حتماً در یک ایستگاه نمازخانه دار توقف داشته باشند. به عنوان مثال اگر قطاري قبل از شروع بازه نماز صبح (یعنی لحظه اذان صبح) از مبدا خارج شده باشد و طبق برنامه زمان بندي خود، مشخص باشد که تا انتهاي بازه نماز صبح (یعنی زمان طلوع آفتاب) به مقصد خود نخواهد رسید، حتماً باید فقط یک بار در یکی از ایستگاه هاي نمازخانه دار مسیر، در طول بازه مجاز براي اداي نماز صبح، توقف داشته باشد. قطار ها با توجه به مدت زمان سفر خود، باید براي هر وعده نمازي که لزوم توقف آن حتمی و روشن شده است، توقف کنند، یعنی ممکن است یک قطار هم براي وعده نماز صبح، هم براي وعده نماز ظهر و عصر و هم براي وعده نماز مغرب و عشاء توقف داشته باشد. نکته دیگر این است که اگر مسافران فرصت کافی داشته باشند تا در ایستگاه مبدا یا در ایستگاه مقصد، نماز خود را به جا بیاورند، دیگر قطار موظف به توقف بین راهی براي فریضه نماز آن وعده نماز نیستند. به عنوان مثال اگر شروع بازه وعده نماز ظهر و عصر، ساعت 12:00 باشد و شروع حرکت قطار ساعت 15:00 باشد، به این دلیل که مسافران زمان کافی براي اداي نماز وعده ظهر و عصر را داشته اند، دیگر این قطار ، موظف به توقف در یکی از ایستگاه هاي بین راه براي آن وعده نماز نیست. البته تعیین این زمان ها به عهده شرکت راه آهن است. به عنوان مثال اگر زمانی که قطار از مبدا خود خارج می شود، بیشتر از 60 دقیقه از اذان گذشته باشد، دیگر نیاز به توقف براي اداي نماز در بین راه نیست. به همین ترتیب اگر زمانی که قطار به مقصد خود می رسد، بیشتر از 60 دقیقه به قضا شدن نماز مانده باشد، باز هم نیاز به توقف براي اداي نماز در بین راه نبوده است. در نهایت هدف مدل ارائه شده، کاهش مجموع زمان سیر همه قطارها، از مبدا تا مقصد است. به طوري که همه محدودیت هاي مسئله برقرار شود.

مدل ریاضی پیشنهادي
در این بخش ابتدا به معرفی نماد ها، مجموعه ها، عوامل و متغیرها پرداخته شده، سپس تابع هدف و محدودیت هاي عمومی معرفی شده و در انتها به توضیح تفصیلی محدودیت نماز پرداخته شده است.
علائم و نماد ها اندیس ها:
i : شمارنده قطارها (i

T) k : شمارنده ایستگاه ها (k

S) b : شمارنده بلاك ها (b

B) n : شمارنده وعده هاي نماز (n

N) مجموعه ها:
I : مجموعه قطار ها، {I={1, …, m S : مجموعه ایستگاه ها، {B ،S={1,.., l مجموعه بلاك ها، N مجموعه نماز هاي روزانه، {3,2,1}=N، (صبح =1، ظهر و عصر =2، مغرب و عشا = 3) و SP مجموعه ایستگاه هاي نماز خانه دار، SPS را نشان
.
متغیرها Oi: مبدا قطار i Di: مقصد قطار i db: طول بلاك b V mini ,b: حداقل سرعت مجاز قطار i در بلاك b V maxi ,b: حداکثر سرعت مجاز قطار i در بلاك b
EToi: زودترین زمان مجاز براي خروج قطار i از مبدا
LToi: دیرترین زمان مجاز براي خروج قطار i از مبدا
می توان نماز نوبت n را در آن ایستگاه ادا کرد یا خیر؟
Gi: ضریب اولویت قطار i STi ,k: حداقل مدت زمان توقف پیش بینی شده قطار i در ایستگاه k H i , j ,b: حداقل مدت زمان هدوي قطار هاي i و j در بلاك b LLk ,n: زودترین زمان مجاز براي توقف قطارها براي نماز نوبت n در ایستگاه k
LU k ,n: دیرترین زمان مجاز براي توقف قطارها براينماز نوبت n در ایستگاه k TOn: مدت زمان بعد از شروع بازه نماز نوبت n که
مسافران امکان اداي فریضه نماز در ایستگاه مبدا را دارند.
TDn: مدت زمان قبل از پایان بازه نماز نوبت n که مسافران امکان اداي فریضه نماز در ایستگاه مقصد را دارند.
TI n: مدت زمان توقف در ایستگاه هاي بین راهی براي اداي فریضه نماز نوبت n M: یک عدد بسیار بزرگ می شود متغیرهاي تصمیم:
X ia,k: زمان ورود قطار i به ایستگاه k X id,k: زمان خروج قطار i از ایستگاه k Ai , j ,b: اگر قطار i زودتر از قطار j وارد بلاك b شود، متغیر Ai , j ,b مقدار یک می گیرد و در غیر این صورت مقدار صفر خواهد گرفت. متغیر تصمیم Ai , j ,b تعیین می کند که از بین قطار i و j کدام یک ابتدا از بلاك b عبور می کند.
Y Li ,k ,n: اگر زمان رسیدن قطار i به ایستگاه k مساوي و یا بعد ازLLk ,n باشد، متغیر Y Li ,k ,n مقدار یک می گیرد و در غیر این صورت مقدار صفر خواهد گرفت. متغیر تصمیم Y Li ,k ,n تعیین می کند که آیا زمانی که قطار i به ایستگاه k می رسد، اذان نوبت n گفته شده است یا خیر؟ و آیا قطارi می تواند براي اداي نماز n در ایستگاه k توقف داشته باشد یا خیر ؟ YU i ,k ,n: اگر زمان رسیدن قطار i به ایستگاه k مساوي و یا قبل ازLU k ,n باشد، متغیر YU i ,k ,n مقدار یک می گیرد و در غیر این صورت مقدار صفر خواهد گرفت. متغیر تصمیمYU i ,k ,n تعیین می کند که زمانی که قطار i به ایستگاه k می رسد، آیا زمان ادا شدن نماز n باقی مانده یا به اتمام رسیده است ؟ و قطارi می تواند براي اداي نماز n در ایستگاه k توقف داشته باشد یا خیر؟ Y i ,k ,n: اگر زمان رسیدن قطار i به ایستگاه k در بازه زمانی مجاز براي اداي نماز نوبت n باشد، متغیر Y i ,k ,n مقدار یک می گیرد و در غیر این صورت مقدار صفر خواهد گرفت. متغیر تصمیم Y i ,k ,n تعیین می کند که زمانی که قطار i به ایستگاه k می رسد، در بازه زمانی اي است که QLi ,n: اگر زمانی که قطار i از ایستگاه مبدا خودخارج می شود، مساوي یا بیشتر از TOn دقیقه ازLLk ,n گذشته باشد، متغیر QLi ,n مقدار صفر می گیردو در غیر این صورت مقدار یک خواهد گرفت. متغیرتصمیمQLi ,n تعیین می کند که آیا مسافران قطار i قبل از حرکت قطار از مبدا، فرصت کافی براي اداي نماز نوبت n در ایستگاه مبدا داشته اند یا خیر؟ QU i ,n: اگر زمانی که قطار i به مقصد خود وارد می شود، مساوي یا کمتر ازTDn دقیقه به LU k ,n مانده باشد، متغیر QU i ,n مقدار صفر می گیرد و در غیر این صورت مقدار یک خواهد گرفت. متغیر تصمیم QU i ,n تعیین می کند که آیا مسافران قطار i بعد از رسیدن قطار به مقصد، فرصت کافی براي اداي نماز نوبت n در ایستگاه مقصد را خواهند داشت یا خیر؟ Qk ,n: اگر با توجه به زمان هاي خروج از مبدا و ورود به مقصد، نیاز به توقف اجباري براي اداي نماز نوبت n در ایستگاه هاي بین راهی باشد، متغیر Qk ,n مقدار یک می گیرد و در غیر این صورت مقدار صفر خواهد گرفت.
متغیر تصمیم Qk ,n تعیین می کند که آیا مسافران قطار i، فرصت کافی براي اداي نماز نوبت n در ایستگاه هاي مبدا یا مقصد خود را دارند یا اینکه قطار لزوماً باید براي اداي نماز نوبت n دریک ایستگاه بین راهی توقف داشته باشد؟ V i ,k ,n: اگر ایستگاه بین راهی k براي توقف قطار i براي اداي نماز نوبت n انتخاب شود، متغیر V i ,k ,n مقدار یک می گیرد و در غیر این صورت مقدار صفر خواهد گرفت.
متغیر تصمیمV i ,k ,n تعیین می کند که آیا قطار i، در ایستگاه k براي اداي نماز نوبت n توقف داشته باشد یا خیر؟

تابع هدف
حداقل کردن زمان تأخیر قطارها به عنوان تابع هدف مدل ارائه شده در نظر گرفته شده است:
m
minz Gi X ia,Di X id,Oi  (1)
i 1
i I

محدودیت هاي کلی
محدودیت هاي مدل ارائه شده براي مسئله زمان بنديحرکت قطارها، سعی دارند تا شرایطی ایمن براي حرکت قطارها فراهم آورند و از طرف دیگر شرایط برنامه ریزي تاکتیکی راه آهن را براي پاسخگویی به تقاضا هاي سفر ایجاد کنند. محدودیت (2) پنجره زمانی حرکت از مبدا را براي قطار بیان می کند که بر اساس برنامه ریزي هاي تاکتیکی راه آهن و مطالعات تقاضاي سفر است، به طوري که اعزام قطارها بتواند به تقاضاهاي سفر به قطار پاسخ دهد. بدین ترتیب زمان حرکت هر قطار از مبدا باید بین زودترین و دیرترین زمان تعیین شده حرکت آن قطار باشد که این زمان ها به عنوان ورودي به مدل داده می شود.

ETOi X id,Oi LUOi (2)
i I
محدودیت (3) بیان می کند که با توجه به شرایط خط و ناوگان، قطار مورد نظر i ، در چه بازه زمانی مجاز است که فاصله بلاك b را طی کند. در این محدودیت مسافت بین دو ایستگاه و نیز حداکثر و حداقل سرعت مجاز براي قطارi در بین هر دو ایستگاه متوالی، به عنوان ورودي به مدل داده می شود.
 db ad db 
197358-8788

1872234-8788

V maxi ,b X i ,k 1 X i ,k V mini ,b  (3)
 iI,bB
با توجه به برنامه ریزي هاي راه آهن و برآوردهاي انجام شده از تقاضاي سفر، قطارها باید در ایستگاه هاي خاصی توقف کنند تا مسافران سوار و پیاده شوند. هر چقدر درجه قطار پایین تر باشد، تعداد توقفات در ایستگاه هاي بین راهی بیشتر است. ممکن است براي بازرسی فنی قطار، آبگیري قطار و … نیز در صورت لزوم توقف هایی اجباري در مسیر پیش بینی شود. حداقل زمان توقف در ایستگاه هاي مختلف براي همه قطارها به صورت ورودي به مدل داده می شود. این مسئله در محدودیت (4) لحاظ شده است.

X id,k X ia,k STi ,k (4)
k S ,k Oi ,Di ,i I
در راه آهن ایران، به دلیل نبود سیستم بلاك متحرك و نیز سیستم کنترل خودکار قطار، بلاك ها، حد فاصل بین دو ایستگاه متوالی در نظر گرفته می شوند. بنابراین به منظور تأمین شرایط ایمن، در هر بلاك حداکثر یک قطارمی تواند وجود داشته باشد. محدودیت هاي (5) و (6) تضمین می کند که هیچ تصادفی بین قطارها روي ندهد.

M Ai , j ,b X id,k X aj ,k 1 H i , j ,b
i, jI,bB
M1Ai , j ,b X dj ,k X ia,k 1 H i , j ,b
i, jI,bB
از آنجا که فرض مسئله و مدل، برنامه ریزي براي مسیرهاي دوخطه است، بنابراین در هر خط قطارها فقط در یک براي حرکت می کنند و فقط امکان تصادف بین قطارهاي هم براي وجود دارد. همان طور که پیش تر اشاره شد، براي ساده تر شدن مدل، بدون از دست رفتن کلیت آن، فقطمسیر رفت در نظر گرفته می شود. واضح است که براي تولید برنامه زمان بندي مسیر برگشت فقط باید اندیس هاي مدل را تغییر داد. دو دسته محدودیت براي عدم تلاقی قطارها پیش بینی شده است. دسته اول محدودیت ها تضمین می کند که فقط هنگامی قطار i می تواند وارد بلاك b شود که از زمان خروج قطار j از بلاك b حداقل زمانی برابر H i , j ,b گذشته باشد. (در این حالت متغیر Ai , j ,b مقدار صفر خواهد داشت) و دسته دوم محدودیت ها تضمین می کند که فقط هنگامی قطار j می تواند وارد بلاك b شود که از زمان خروج قطار i از بلاك b حداقل زمانی برابر H i , j ,bگذشته باشد. (در این حالت متغیرAi , j ,b مقدار یک خواهد داشت) این دو دسته محدودیت طوري طرح شده اند که همواره یکی و فقط یکی از آن ها برقرار خواهد بود، بنابراین این دو دسته تضمین خواهد کرد که هیچ گاه بین دو قطار عبوري از یک بلاك، برخوردي به وجود نیاید.
مدلسازي محدودیت نماز
براي مدلسازي محدودیت نماز، ابتدا به شرح دقیق مسئله می پردازیم. توقف قطارها براي نماز در سه بازه زمانی انجام می گیرد: (1) توقف براي نماز صبح، (2) توقف براي نماز ظهر و عصر، (3) توقف براي نماز مغرب و عشاء.
در صورتی که قطار i در بازه زمانی مربوط به هر یک از نمازها در حال حرکت باشد، باید در ایستگاهی که نمازخانه داشته باشد، به مدتTI n دقیقه (به عنوان مثال 20 دقیقه) توقف کند تا مسافران از قطار پیاده شده و پس از اداي فریضه نماز بار دیگر سوار قطار شده تا قطارحرکت کند. اگر سفر قطار (از لحظه خروج از مبدا تا ورود به مقصد) با بازه نماز نوبت n تلاقی داشته، اما حرکت قطار پس از TOn دقیقه (به عنوان مثال 60 دقیقه) بعد از آغاز وقت نماز نوبت n باشد، نیازي به توقف قطار براي نماز نوبت n نیست، زیرا مسافران فرصت کافی براي اداي نماز قبل از سفر با قطار را داشته اند. همچنین اگر قطاري زود تر از TDn دقیقه (به عنوان مثال 60 دقیقه) مانده به قضا شدن نماز وعده n به مقصد برسد، لازم نیست قطار براي اداي نماز وعده n در بین راه توقف داشته باشد، زیرا مسافران فرصت کافی دارند تا پس از پیاده شدن از قطار به اداي نماز بپردازند. البته زمان هايTOn ،TI n و TDn ، توسط راه آهن تعیین شده و به عنوان عوامل ورودي مدل محسوب می شوند.
براي هر یک از وعده هاي نماز، یک بازه زمانی وجود دارد. به عنوان مثال بازه نماز نوبت ظهر و عصر، از اذان ظهر است (مثلاً ساعت 12:00) تا نیم ساعت مانده به قضا شدن نماز ظهر (مثلاً ساعت 18:00). در واقع توقف براي هر نوبت نماز باید در بازه آن نوبت باشد. براي تعیین بازه ها براي هر نوبت نماز، از دو عامل ورودي LLk ,n (ابتداي بازه) و LU k ,n (انتهاي بازه) استفاده شده است.
مدلسازي محدودیت توقف نماز در 3 بخش انجام شده است. بخش اول، تشخیص برقرار شدن شرط نماز در بین مسیر، بخش دوم، تشخیص لزوم توقف بین راهی براي اداي نماز و بخش سوم، توقف براي نماز است.
مشکل و دشواري اصلی مدلسازي این محدودیت و تفاوت ذاتی آن با سایر محدودیت هاي مسئله زمان بندي حرکت قطارها، شرط ضمنی بودن آن است. بدین معنی که از ابتدا مشخص نیست که یک قطار حتماً باید براي نماز توقف داشته باشد یا خیر. به عبارت دیگر، تا قبل از حل مسئله زمان بندي حرکت قطارها و تعیین زمان ورود قطار ها به ایستگاه ها و خروج آن ها از ایستگاه ها، مشخص نیست که آیا قطار لازم است در بین راه براي نماز توقف داشته باشد یا خیر؟ از طرف دیگر، توقف براي نماز روي زمان ورود قطارها به ایستگاه ها و خروج قطارها از ایستگاه ها تأثیرگذار است. بنابراین این ارتباط به طور کامل دو طرفه است. براي رفع این مشکل باید محدودیتی قرار داده شود که در صورت برقراري شرایط نماز، فعال شده و توقفTI n دقیقه اي را ایجاد کند و در غیر این صورت عمل نکند. در واقع مدل طوري طراحی شده استکه تعیین می کند، قطار i هنگامی که به ایستگاه kمی رسد، آیا در بازه زمانی اي است که می تواند براي نمازنوبت n توقف داشته باشد، یا خارج از آن بازه است. اینموضوع توسط متغیر صفر و یک Y i , j ,k تعیین می شود، اگر زمان رسیدن قطار i به ایستگاه X ia,k ) k) در بازه زمانی اي است که می تواند براي نماز نوبت n توقف داشته باشد، این متغیر مقدار یک و در غیر این صورت مقدار صفر می گیرد (به صورت رابطه (7)).

IF LLk ,n X ia,k LU k ,n (7)
THEN Y i ,k ,n = 1 ELSE Y i ,k ,n = 0
نکته قابل تأمل در طراحی رابطه (7) این است که به طور مستقیم نمی توان مدل خطی اي براي شرط ذکرشده ایجاد کرد، یعنی نمی توان مدلی نوشت که در آن یک متغیر، هم بتواند شرط X ia,k LLk ,n و هم شرطX ia,k LU k ,n را بررسی کند. بنابراین دو متغیر جدید تعریف شده است که هر یک، یکی از شرط ها را به تنهایی بررسی می کند و سپس با استفاده از دو متغیر جدید، می توانیم به مقصود خود برسیم. یکی از این متغیر ها Y Li ,k ,n است که بررسی می کند که شرط X ia,k LLk ,n برقرار است یا خیر؟ به عبارت ساده تر مقدار متغیر Y Li ,k ,n نشان می دهد که زمان رسیدن قطار i به ایستگاه k، آیا بعد از ابتداي بازه نماز نوبت n بوده است یا خیر؟
این شرط بیان می کند که اگر قطار i بعد از ابتداي بازه نماز نوبت n به ایستگاه k رسیده باشد، متغیر Y Li ,k ,n مقدار یک و در غیر این صورت مقدار صفر می گیرد. این شرط به صورت محدودیت (8) و (9) تبدیل شده است.

X ia,k LLk ,n M YLi ,k ,n  (8)
i I ,n N ,k S p ,k  Di ,D j

X ia,k LLk ,n M1YLi ,k ,n  (9)
i I ,n N ,k S p ,k  Di ,D j
در صورتی کهX ia,k از LLk ,n کوچک تر باشد، در محدودیت (8)، متغیرYLi ,k ,n می تواند صفر یا یک باشد، ولی در محدودیت (9) متغیرYLi ,k ,n باید صفر باشد. درصورتی کهX ia,k ازLLk ,n بزرگ تر یا مساوي باشد، در محدودیت (9) متغیرYLi ,k ,n می تواند صفر یا یک باشد، ولی در محدودیت (8)، متغیرYLi ,k ,n باید یک باشد.
متغیر دیگري که در مدل تعریف شدهYUi ,k ,n است که بررسی می کند آیا شرطX ia,k LU k ,n برقرار است یا خیر؟ به عبارت ساد هتر، مقدار متغیر YUi ,k ,n نشان میدهد که آیا زمان رسیدن قطار i به ایستگاه k، قبل از انتهاي بازه نماز نوبت n بوده است یا خیر؟ این شرط بیان می کند که اگر قطار i قبل از انتهاي بازه نماز نوبت n به ایستگاه k رسیده باشد، متغیر YUi ,k ,n مقدار یک می گیرد و در غیر این صورت مقدار صفر. این شرط به صورت محدودیت هاي (10) و (11) به مدل ریاضی اضافه شده است.

X ia,k LU k ,n M1YU i ,k ,n  (10)
i I ,n N ,k S p ,k  Di ,D j

X ia,k LU k ,n M YU i ,k ,n  (11)
i I ,n N ,k S p ,k  Di ,D j

نحوه عملکرد محدودیتهاي (10) و (11) مانند محدودیت مربوط به متغیر YLi ,k ,n است. با اعمال محدودیت هاي (8)، (9)، (10) و (11) می توانیم دریابیم که زمان رسیدن قطار i به ایستگاه k، چه نسبتی با ابتداي بازه نماز و چه نسبتی با انتهاي بازه نماز دارد. با یک مثال این مطلب تشریح می شود. فرض کنید زمان ورود قطاري به ایستگاه هاي مختلف به شرح زیر و ابتداي بازه نماز نوبت ظهر (LLk ,n ) ساعت 12:00 و انتهاي بازه نماز ظهر (LUk ,n ) ساعت 18:00 باشد. با اعمال محدودیت (8) و (9) سطر سوم جدول حاصل می شود و با اعمال محدودیت هاي (10) و (11) سطر چهارم جدول حاصل می شود.

با توجه به جدول (1) می توان دریافت که ایستگاه هایی که هم YLi ,k ,n و هم YUi ,k ,n مقادیر یک را گرفته اند، همان ایستگاه هایی هستند که قطار i وقتی به این ایستگاه ها می رسد، در بازه نماز نوبت n قرار گرفته و می تواند براي نماز توقف کند، اما هنوز متغیري که بتواند به طور مستقیم تعیین کند که قطار i هنگامی که به ایستگاه k می رسد، آیا در بازه زمانی اي است که می تواند براي نماز نوبت n توقف داشته باشد یا خیر به دست نیامده است. به این منظور متغیر صفر و یک Y i ,k ,n تعریف میشود که با توجه به مقادیر YLi ,k ,n و YUi ,k ,n به نحوي که در جدول (2) آمده است عمل می کند.
YUi ,k ,n YLi ,k ,n Y i ,k ,n
جدول2: رابطه مقادیر ، و
YLi ,k ,n 0 0 1 1
YUi ,k ,n 0 1 0 1
Y i ,k ,n 0 0 0 1
در واقع می خواهیم متغیر Y i ,k ,n مقدار حاصل ضرب دو متغیر YLi ,k ,n و YUi ,k ,n را نشان دهد (به صورت رابطه 12).
YU i ,k ,n YLi ,k ,n Y i ,k ,n
به این دلیل که رابطه (12) مدل را از حالت خطی خارج می کند، از محدودیت هاي (13) و (14) براي رفع این مشکل استفاده می شود.

YLi ,k ,n YU i ,k ,n 1M1Y i ,k ,n 
i I ,n N ,k S p ,k  Di ,D j

YLi ,k ,n YU i ,k ,n 1M Y i ,k ,n 
i I ,n N ,k S p ,k  Di ,D j

جدول1: یک مثال عددي از عملکرد محدودیت توقف براي نماز
Stations … 4 5 6 7 … 20 21 22 23 24 …
X ia,k … 10:30 11:15 12:00 12:30 … 16:00 17:00 18:00 18:45 19:10 …
YLi ,k ,n … 0 0 1 1 … 1 1 1 1 1 …
YUi ,k ,n … 1 1 1 1 … 1 1 1 0 0 …
تا این مرحله با اعمال محدودیت هاي (8)، (9)، (10)، (11)، (13) و (14)، همه ایستگاه هایی که قطار i میتواند براي نماز در آنها توقف داشته باشد، مشخص می شود. در واقع این محدودیت ها به این سؤال پاسخ می دهند که آیا قطار i در طول مدت سفر خود به بازه نماز بر می خورد یا خیر؟ در مرحله بعد به دنبال آن هستیم که دریابیم آیا قطار i حتماً باید در بین راه براي نماز توقف داشته باشد یا خیر؟ براي پاسخ به این سؤال باید 2 سؤال را بررسی کنیم. سؤال اول این است که آیا قطار i قبل از حرکت از ایستگاه مبدا، فرصت کافی براي اداي نماز وعده n را دارد یا خیر؟ با اعمال محدودیت هاي (15) و (16) متغیرQLi ,n مقدار صفر یا یک خواهد گرفت که هر یک از این مقادیر پاسخی براي سؤال اول خواهد بود.

X Odi LLk ,n TOn M1QLi ,n  (15)
i I ,n N

X Odi LLk ,n TOn M QLi ,n  (16)
i I ,n N
در محدودیت هاي (15) و (16) متغیر صفر و یک QLi ,n طوري عمل می کند که اگر زمان خروج قطار i از مبدا خود به گونه اي باشد که مسافران فرصت کافی براي اداي نماز نوبت n نداشته باشند، این متغیر مقدار یک خواهد گرفت و در غیر این صورت مقدار صفر خواهد گرفت. سؤال دوم که باید پاسخ داده شود، این است که آیا قطار i بعد از رسیدن به ایستگاه مقصد، فرصت کافی براي اداي نماز وعده n را دارد یا خیر؟ با اعمال محدودیت هاي (17) و (18) متغیرQU i ,n مقدار صفر یا یک خواهد گرفت که هر یک از این مقادیر پاسخی براي سؤال دوم خواهد بود.

X Dd i LU k ,n TDn M QU i .k  (17)
i I ,n N

XDdi LUk,n TDn M1QUi,n  (18)
i I ,n N
در محدودیت هاي (17) و (18) متغیر صفر و یک QU i ,n طوري عمل می کند که اگر زمان ورود قطار i به مقصد خود به گونه اي باشد که مسافران فرصت کافی براي اداي نماز نوبت n را نداشته باشند، این متغیر مقدار یک خواهد گرفت و در غیر این صورت مقدار صفر خواهد گرفت. با اعمال محدودیت هاي (15)، (16)، (17) و (18) متغیر هاي QLi ,n و QU i ,n مقدار گرفته اند، اما نیاز به یک متغیر صفر و یک هست که تعیین کند، آیا قطار i باید براي اداي نماز n، در بین راه توقف داشته باشد یا خیر ؟ به این دلیل متغیرQi ,n در مدل تعریف شده است. متغیر Qi ,n زمانی مقدار یک م یگیرد که هر دو متغیر QLi ,n و QU i ,n مقدار یک گرفته باشند و در غیر این صورت مقدار صفر خواهد گرفت. جدول (3) روابط بین 3 متغیر
.را نشان می دهد QU i ,n و QLi ,n ،Qi ,n

جدول 3: رابطه ي مقادیر QLi ,n ، Qi ,n و QU i ,n
QLi ,n 0 0 1 1
QU i ,n 0 1 0 1
Qi ,n 0 0 0 1

طبق جدول (3) هنگامی که هر دو متغیر QLi ,n و QU i ,n مقدار یک گرفته باشند، بدان معنی است که قطار i نه در مبدا خود و نه در مقصد خود، فرصت کافی براي توقف براي اداي نماز را نداشته است، بنابراین در این حالت، متغیر QLi ,n باید مقدار یک بگیرد که نشان دهد قطار i باید براي اداي نماز نوبت n حتماً توقف بین راهی داشته باشد. اگر حتی یکی از دو متغیر QLi ,n یا QU i ,n مقدار صفر بگیرد، بدان معنی است که قطار i در مبدا یا در مقصد خود، فرصت توقف براي اداي نماز وعده n را داشته است، بنابراین باید متغیر Qi ,n مقدار صفر بگیرد؛ بدان معنی که قطار i نیاز توقف بین راهی براي نماز نوبت n را ندارد. محدودیت هاي (19) و (20) با توجه به مقادیر QLi ,n و QU i ,n طوري عمل می کنند که متغیر Qi ,n طبق جدول 3 مقدار بگیرد.

QFi ,n QLi ,n 1M1Qi ,n 
i I ,n N

QFi ,n QLi ,n 1M Qi ,n 
i I ,n N
اکنون باید بر اساس تابع هدف مسئله، از بین ایستگاه هایی که قطار i براي نماز نوبت n باید انتخاب کند، یکی و فقط یکی از ایستگاه ها انتخاب شود. براي این منظور متغیر صفر و یک V i ,k ,n در نظر گرفته می شود. این متغیر در واقع امکان انتخاب شدن یا انتخاب نشدن ایستگاه k را تعیین می کند.
اگر متغیر V i ,k ,n مقدار یک گرفت، به این معنی است که قطار i براي نماز وعده n، باید در ایستگاه k توقف کند و اگر V i ,k ,n مقدار صفر گرفت، قطار i براي نماز وعده n، نباید در ایستگاه k توقف کند. براي این منظور محدودیت (21) طراحی شده است که تضمین می کند که ایستگاهی که توقف در آن انجام خواهد شد، به طور حتم جزو ایستگاه هایی باشد که قطار i در بازه نماز وعده n به آن می رسد.

V i ,k ,n Y i ,k ,n (21)
i I ,n N ,k S p ,k  Di ,D j
طبق توضیحات قبل اگر قطار i براي نماز نوبت n در ایستگاه k بتواند توقف داشته باشد، متغیر Y i ,k ,n مقدار یک خواهد گرفت، بنابراین متغیرV i ,k ,n ، بر اساس رابطه (21) فقط براي ایستگاه هایی می تواند مقدار یک بگیرد که متغیر متناظر Y i ,k ,n آن، مقدار یک گرفته باشد. این محدودیت تضمین می کند که ایستگاهی براي توقف انتخاب شود که قطار در بازه زمانی نماز به آن ایستگاه رسیده باشد. اکنون باید از بین ایستگاه هایی که می توانند براي توقف قطار i براي نماز نوبت n انتخاب شوند، یک ایستگاه را انتخاب کنیم. براي این منظور محدودیت (22) ارائه شده است.
kS p V i ,k ,n Qi ,n (22) i I ,n N ,k S p ,k  Di ,D j
اگر مقدار متغیر Qi ,n صفر شود، بدان معنی است که قطار i نیاز به توقف بین راهی براي نماز نوبت n را ندارد. محدودیت (22) طوري طراحی شده است که در حالتی که متغیر Qi ,n صفر است، هیچ ایستگاهی براي توقف براي نماز انتخاب نشود و اگر متغیر Qi ,n مقدار یک گرفته باشد، به این معنی است که قطار i براي نماز نوبت n نیاز به توقف بین راهی دارد. بنابراین محدودیت (22) طوري طراحی شده که در حالتی که متغیر Qi ,n یک است، یک و فقط یک ایستگاه از بین ایستگاه هایی که قطار i مجاز است براي نماز نوبت n در آن ها توقف داشته باشد، انتخاب شود. بدین ترتیب با اعمال محدودیت (22) ایستگاهی که قطار i براي نماز وعده n، باید در آن توقف داشته باشد، تا بهترین مقدار تابع هدف به دست آید، انتخاب می شود. اکنون که ایستگاه مورد نظر انتخاب شده است، باید محدودیتی طراحی کنیم که قطار i براي نماز وعده n، زمان TI n دقیقه که همان زمان مورد نیاز براي اداي نماز است را در ایستگاه انتخاب شده توقف کند.
محدودیت (23) این موضوع را تضمین می کند.

X id,k X ia,k TI n V i ,k ,n (23)
i I ,n N ,k S p ,k  Di ,D
j
لازم به یاد آوري است که مدل ارائه شده، مدت زمان توقف در یک ایستگاه را بر اساس دو محدودیت (4) و (23) تعیین می کند. به عنوان مثال اگر قطار i لازم باشد که در ایستگاه k، 15 دقیقه براي پیاده و سوار شدن مسافران بین راهی توقف داشته باشد و نیز لازم باشد که همان قطار براي اداي نماز ظهر مدت 20 دقیقه در همان ایستگاه توقف داشته باشد، در این حالت مدل طوري عمل می کند که قطار تنها مدت 20 دقیقه در آن ایستگاه توقف کند. در این مدت، هم فرصت کافی براي اداي نماز و هم براي پیاده و سوار شدن مسافران وجود خواهد داشت.

ارزیابی مدل پیشنهادي
براي ارزیابی مدل ارائه شده، ابتدا یک مثـــال کوچک به طور تفضیلی ارائه شده و سپس مسائل با ابعاد بزرگ تر حل می شود.
براي تشریح بهتر مدل، یک مثال ساده در این بخش ارائه می شود. این مثال شامل 4 قطار و 7 ایستگاه می شود.
مبدا همه قطارها ایستگاه 1 و مقصدشان ایستگاه 7 است.
اولویت همه قطار ها یکسان فرض شده است. واحد زمانی بر اساس دقیقه بوده و دوره زمان بندي در این مثال 360 دقیقه در نظر گرفته شده است. بنابراین فقط یک وعده نماز مورد بررسی قرار گرفته است. بازه زمانی مجاز در این مثال از دقیقه 630 تا 980 مفروض است. قطار 1 در ایستگاه 4، قطار 2 در ایستگاه 3، قطار 3 در ایستگاه 5 و قطار 4 در ایستگاه 2 و 6، به مدت 15 دقیقه، توقف از پیش تعیین شده براي پیاده و سوار کردن مسافران دارند. همچنین بازه مجاز براي خروج قطار 1 از مبدا خود از دقیقه 600 تا 620، براي قطار 2 از 630 تا 660، براي قطار 3 از 680 تا 790 و براي قطار 4 از 680 تا 800 مفروض است. زمان هاي TOn ،TI n و TDn به ترتیب برابر 40 دقیقه، 60 دقیقه و 60 دقیقه در نظر گرفته شده است. فرض می کنیم، تنها ایستگاه 3 نمازخانه داشته باشد.
شکل (1) شبکه فرضی مثال ارائه شده را نشان می دهد.

1

6

5
4
3
2
7



قیمت: تومان


دیدگاهتان را بنویسید