نشریه تخصصی مهندسی صنایع، دوره 50، شماره 2، پاییز و زمستان 1395، از صفحه 247 تا 259

ارائة مدلی برای مسئلة مسیریابی اتوبوس مدرسه با درنظرگرفتن تفکیک جنسیتی
علیرضا رشیدی کمیجان1* ، پیمان قاسم

دانشیار مهندسی صنایع، دانشکدة مهندسی صنایع، دانشگاه آزاد اسلامی واحد فیروزکوه
دانشجوی دکتری مهندسی صنایع، دانشکدة مهندسی صنایع، دانشگاه آزاد اسلامی واحد تهران جنوب

)تاریخ دریافت 15/09/94 ـ تاریخ دریافت روایت اصلاح شده 12/06/95 ـ تاریخ تصویب 06/09/95( چکیده
در کشور ما مسیر حرکت سروی های مدارس به صورت تجربی و بدون درنظرگرفتن مسیر و مکان بهینة علمی تعیین می شـو د. همـواره طـی شدن مسیرهای اضافی توس این سروی ها موجب افزایش جابه جایی و افزایش مصرک سوخت و صرک هزینه های اقتصادی هنگفت می شـود . از این رو، پژوهش حاضر حرکت سروی های مدارس را در تهران با درنظرگرفتن دانش آموزان خـاص بررسـی مـ ی کنـ د. درنهایـت، مـدلی ارائـه می شود که حرکات را تا حد ممکن به حداقش می رساند و از عبورهای تکراری از ایستگاه ها جلوگیری مـی کنـد. مـدل ارائـه شـده نیـز از طریـقنرم افزار گمز حش می شود. با توجه به NP-Hard بودن مدل، برای حش مسئله در ابعاد بزرگ از الگوریتم ژنتیک استفاده شده است.‌نوآوری عمدة تحلیق درنظرگرفتن تفکیک جنسیتی در اتوبوس ها و مدارس است. برای حش این مسئله یک مدل برنامه ریزی اعداد صحیح خطی توسـعه دادهشده است. نتایج پژوهش بیانگر کاهش زمان حمش ونلش دانش آموزان مدارس است.

واژه‌های‌کلیدی: برنامه ریزی عدد صحیح خطی، تفکیک جنسیتی، دانش آموزان خاص، مسـئلة مسـیریابی اتوبـوسمدرسه مقدمه
مسائش مسیریابی اتوبوس مدرسه معرفی می شوند [1].
برای این سیستم که شامش مجموعه ای سروی گیرنـده و مجموعه ای سروی دهنده می شـود ایـن پرسـش مطـرحاست که هـر سـرو ی دهنـده بـه کـدام عضـو از مجموعـةسروی گیرنده سروی دهد و عملیات سروی دهـ ی خـودرا چگونه انجـام دهـد. مسـئلة مسـیریابی وسـیلة نللیـه درساده ترین صورت خود در پی یافتن جواب این سـؤال اسـتکه درصورت در اختیار داشتن ناوگانی محدود برای بازدیـداز نلاطی محدود در شبکة شهری یا بین شهری، هـر وسـیلةنللیه به کدام گره ها سر بزنـد و خـدمات ارائـه دهـد و ایـنوسیلة نللیه از مجموعة تحت وهیفة خود بـه چـه ترتیبـیبازدید کند و ایستگاه های در ارتباط با این وسـیلة نللیـه درچه مکانی مستلر شوند. درواقع، مسـئلة مسـیریابی وسـیلةنللیه در حالـت سـادة آن، شـامش یـک دسـته بنـدی نلـاطسروی گیرنده و حش یک مسئلة فروشـندة دوره گـرد بـرای ازآنجا که عمدهترین قسمت سیستم حمش ونلش عمـومی در کشورهای درحال توسعه را شبکة اتوبوسرانی شهری تشکیش می دهد، طراحی بهینة شـبکة اتوبوسـرانی بـا هـدک بهبـود وضعیت حمش ونلش عمومی اهمیت فراوانی دارد .همچنـین،در اغل ب کش ورها مس یر حرک ت س روی ه ای م دارس به صورت تجربی و بدون درنظرگـرفتن مسـیر بهینـة علمـی تعیین میشود. همواره طی شدن مسیر اضافی از سوی ایـن سروی ها موجـب افـزایش جابـه جـایی و افـزایش مصـرک سوخت و صرک هزینـه هـای اقتصـادی هنگفـت مـی شـود.مسائش مسیریابی اتوبوس مدرسه شامش ترکیبـی از انتخـابایستگاه و تولید مسیر بـرای اتوبـوس هاسـت کـه هـم زمـانبه دنبال مجموعهای از ایستگاه ها می گردد تا دانش آموزان را در این مکانها سوار کند و همچنین بـه دنبـال مسـیرهاییبرای اتوبوس ها میگـردد تـا ایسـتگاه هـای انتخـاب شـده را ویزیت کنند و دانشآموزان را به مدارس خود برسانند. ایـن

Email: [email protected] 02176445994 : نویسندة مسئول: تلفن:02176444091 فک *
هر دسته نلاط انتخابی می شود. اما مسئله درعمش به سادگی مسئلة باا نیست و شرای دیگری نیز بر آن حاکم است که پیچیدگی مسئله را افزایش می دهـد؛ بـرای مثـال، هرفیـتوسایش نللیه نامحدود نیست و ممکن است زمان سفر آن هـاتحت تأثیر شرای شبکه باشد که محللان بـه ایـن شـرای ب ه دلی ش اهمی ت آن ه ا جداگان ه در مس ائش مس یریابی – مکان یابی وسیلة نللیه توجه کرده اند[2].
مسائش مسیریابی همواره از جملـه مسـائش پرکـاربرد در بهین ه س ازی اس تفاده از من ابع فیزیک ی، انس انی و زم انی هستند که در موارد مختلف به صورت عملی از آن ها استفاده شده است. در حال حاضر، به دلیـش افـزایش نـرخ بنـزین از س ویی و کمب ود من ابع فس یلی از س وی دیگ ر، مس ائش مسیریابی بیش از پیش به اقتصاد جامعه کمک می کند [3]، درحالی که با استفاده از ایـن تحلیلـات، مـی تـوان از حجـم مسافرت های روزانه کم کرد تـا بـار ترافیـک کمتـر شـود و به این ترتیب آاینده های خطرنا هوا- کـه در کشـور مـا و به ویژه در تهران بـیش از حـد مجـاز اسـت – کـاهش یابـد.
براساس کاربرد، در موارد گوناگون شـکش مسـئله بـا حفـظ کلیت آن تغییر می کند.
در این تحلیق، حرکت و عبور و مرور سـروی مـدارسبررسی می شود. سروی مدارس معمواً برنامه ریزی ویژه ای برای چگونگی حرکت و ایجاد نظم در طول مسـیر نـدارد و معمواً این حرکت هـا مبتنـی بـر تجربـة راننـدگان اسـت و چندان مبتنی بر اصول علمی نیست. از ایـ ن رو، در پـژوهشحاضر حرکت سروی های مدارس بررسی می شود و مـدلی ارائه می شود که حرکات را تا حد ممکن به حداقش می رساند و از عبورهای تکراری از ایسـتگاه هـا جلـوگیری مـی کنـد و کوتاه ترین مسیرها را معرفی می کند. همچنـین ، بـا معرفـی راهکاری برای سوق دادن چند دانش آموز بـه یـک ایسـتگاه ، سعی شده است تعداد ایستگاه ها کـاهش یابـد . درادامـه ، بـا توج ه ب ه ک اهش حرک ات وس ایش نللی ه، مل دار زم ان صرفه جویی شده و هزینه های اقتصادی آن تعیین مـ ی شـود .
نوآوری این پژوهش درنظرگرفتن حالت تفکیـک جنسـیتیدر ه ر س روی اس ت ک ه ت اکنون در مس ئلة مس یریابی سروی مدارس حالت تفکیک جنسیتی درنظر گرفته نشده است .درادامه ،ادبیات موضوع بیان می شود. سـس مسـئلهتعریف و مدل سازی می شود. درادامه، پـ از مطـرح کـردنمطالعة موردی، حش مدل از طریـق نـرم افـزار گمـز صـورتمی پذیرد. همچنین، حش مدل در ابعاد کوچـک، متوسـ وبزرگ از طریق الگـوریتم ژنتیـک انجـام مـی گیـرد. سـس تحلیــش حساســیت صــورت مــی گیــرد و درنهایــت نیــزنتیجه گیری ارائه می شود.
مرور ادبیات
مسئلة مسیریابی اتوبوس مدرسه در ملولة مسائش مسیریابی وسیلة نللیه قرار دارد که در آن یک ناوگان اتوبوس مدرسـهطوری برنامه ریزی می شود که هر اتوبوس دانش آموزان را در ایســتگاه هــا ســوار کنــد و در مدرســة مــورد نظــر پیــاده کند. نیوتون و توماس برای اولین بار ایـن مسـئله را بررسـیکردند [4].
مسئلة مسیریابی اتوبوس مدرسه در دو محی شهری یا روس تایی درنظ ر گرفت ه م ی ش ود. در مح ی روس تایی، دانش آموزان مجبور نیستند تا ایستگاه اتوبوس پیاده بروند و اتوبوس آن ها را مستلیم از در منزل سوار مـ ی کنـد ، امـا درمح ی ش هری دان ش آم وزان بای د ت ا ایس تگاه اتوب وسمشخص شده پیاده بروند و از آنجا سوار اتوبـوس شـوند [5].
جنبة دیگری که مسائش مسیریابی اتوبوس مدرسه را از هـممتمایز می کند امکان بارگذاری مختل اسـت. در بارگـذاریمختل ، ممکن است یک اتوبوس دانـش آمـوزان مربـوط بـهبیش از یک مدرسه را سوار کند، اما اگر بارگـذاری مخـتل مجاز نباشد هر اتوبوس باید دانـش آمـوزان یـک مدرسـه راسوار کند [6].
درنظرگرفتن دانش آمـوزان خـاص از جملـه موضـوعاتیاست که در ادبیات موضوع مسئلة مسـیریابی و مکـانیـ ابی اتوبوس مدرسه وجود دارد؛ یعنی این دانشآموزان بـه دلیـشناتوانی، توانایی راه رفتن تا ایستگاه تعیـی ن شـده را ندارنـد واتوبوس مورد نظر باید آن ها را از در منزل سوار کند [7].
پار و کیم مسئله ای را برای طراحـی مسـیر اتوبـوس مدرســه بــه صــورت تــک مدرســه درنظــر گرفتنــد و یــک برنامه ریزی عدد صحیح غیرخطی را برای آن تعریف کردنـد[8 ]. آنه ا ی ک ک ران ب اا ب رای مس ئله ایج اد کردن د وبه این منظور از حش مسائش تخصیص به صورت مکرر اسـتفاده کردند و جواب بهینه را بـا اسـتفاده از روش حـد و مشـتق مشخص کردند.
ناصری یـک الگـوریتم دومرحلـه ای بـرای حـش مسـئلة DARP1 ارائ ه داده اس ت. مس ئلة DARP در حال ت کل ی شامش طراحی مسیر و زمان بندی برای تعداد معینی کاربر و وسیلة نللیه با درنظرگرفتن حالت بارگذاری و تحویش است.
مرحلة اول این الگوریتم به پـذیرش یـا رد درخواسـتهـایجدید می انجامد و خروجی مرحلـ ة دوم، شـامش مسـیرهایبهبودیافته وسایش نللیه است. هدک اساسی در این پژوهش ،پذیرش حداکثر درخواستهای جدید است، بـه گونـه ا یکـهسطح نارضایتی مسافران به حداقش برسد .نتایج این پژوهش نش ان داد ب ا الگ وریتم پیش نهادی، ب یش از 90 درص د از درخواستهای جدید پذیرفته می شود و بـا افـزایش درجـة پویایی سطح نارضایتی مسافران افزایش می یابد [9].
داگـــلاس و همکـــاران مـــدلی DARP پویـــا را بـــادرنظرگرفتن زودترین زمان حرکت و دیرترین زمان رسیدن به ملصد ارائه دادند. در ایـن مسـئله، سـروی هـا براسـاسم اکزیمم زم ان ت أخیر مج از مس یرهای خ ود را انتخ اب می کنند. برای این کار رانندگان مکان و زمان شروع حرکت خود را به واحد کنترل گزارش م یدهند. از جمله متغیرهای تصمیم درنظرگرفته شده در این پژوهش هرفیت خودروها و متغیرهای مربوط به مسیریابی و مکان یابی ایستگاه هاست. با توج ه بــه پویــابودن مســئله در هــر دوره و درنظرگــرفتنماکزیمم زمان تأخیر، الگوریتم فرا ابتکاری در هر دوره برای حش پیشنهاد شده است [10].
لو با استفاده از مدل DARP به طور هم زمان حالت هـا ی زیر را درنظر گرفت: 1. وسـایش حمـش ونلـش غیـر همگن؛ 2.
برنامـ ه ریـ زی نیـ روی انسـ انی؛ 3. بارگـ ذاری مخـ تل .
به این منظور، وی دو مدل مختلف ارائه داده است. مـدل اولبرای سوارکردن کارمندان و مدل دوم به منظور پیاده کـردنآن ها بیان شده است. وی با مثـال هـا ی عـددی مختلـف درحجم های متفاوت از الگوریتم شاخه و برش برای حـش ایـنمسئله استفاده کرده است [11].
مولنبوا و همکاران بـا اسـتفاده از مـدل سـاز ی DARP مدلی برای حمش ونلش بیماران در بلژیک ارائـه دادنـد. بـرایحش مدل ارائه شده از جسـت وجـوی محلـی اسـتفاده شـدهاست. تابع هدک مد نظر در این پژوهش کاهش هزینـه هـا وکاهش زمان حمش ونلش بیماران است. مدل ارائه شده تـوازنخوبی را بین هزینة عملیاتی و کیفیت سروی دهـ ی ایجـادم ی کن د. همچن ین، ی ک الگ وریتم ابتک اری ب ه منظ ور زمان بندی مسیرها در این پژوهش ارائه شده است. الگوریتم مذکور به منظور رسیدن به یک جواب شدنی برای هر مسیر ارائه شده است. نتایج ایـن مطالعـة مـوردی عملکـرد قابـشقبولی را برای مدل نشان می دهد [12].
چن و همکاران یک مدل عدد صحیح مخـتل را بـرایزمان بندی و مسیریابی حرکت اتوبوس مدرسه ارائـه دادنـد.
برای حش این مسئله از الگوریتم فـرا ابتکـاری شـب یه سـاز ی بازبخت استفاده شده است. مسئلة مورد نظر در این پژوهش ب ه ص ورت ت ک مدرس ه ای و ناوگ ان حم ش ونل ش همگ ن و درنظرگرفتن پنجرة زمانی است [13].
کنگ مدلی را به منظور مسیریابی و مکان یابی سـروی مدارس ارائه داد. مـدل ارائـه شـده بـا اسـتفاده از الگـوریتمژنتیک حش شده است. مسئلة مورد بررسی شامش دو بخـشاست. بخش اول شامش زمان بندی و مسیریابی وسیلة نللیـهاست و در بخـش دوم مکـان یـ ابی بـرای ایسـتگاههـا انجـاممی گیرد. در این پژوهش ،30 اتوبوس در زمینة وسایش نللیه مد نظر قرار گرفته است که نتـایج تحلیـق بیـانگر عملکـردمناسب الگوریتم ژنتیک طراحی شده است [14].
ویلیام با استفاده از تلریب پیوسـته مـدلی را بـه منظـورمس یریابی س روی م دارس ارائ ه داده اس ت. بارگ ذاریمختل و پنجرة زمانی از جمله نکات شـاخص پـژوهش ویبوده است. مطالعة موردی وی شهر میسـوری اسـت . نتـایجتحلیق بیان می کند بارگذاری مختل برای کـلان شـهرها و همچنین درصورت نزدیک بودن مـدارس بـه یکـدیگر مفیـداست [15].
لیما مدلی را به منظور مسـیریابی سـروی مـدارس درحالت شهری در برزیش و با درنظرگرفتن بارگـذاری مخـتل ارائه داده است. پنج الگوریتم فرا ابتکاری نیز به منظور حـشاین مدل ارائه شده است. همچنین، سه مثال عددی و یـکمطالعة موردی برای صحت عملکرد مدل ارائـه شـده اسـت.نتایج بیان می کنـد رویکـرد بارگـذاری مخـتل نسـبت بـهحالتی که بارگذاری مختل درنظر گرفته نمی شـود ، هزینـةبسیار کمتری دارد [16].
در این پژوهش، مسیریابی سـروی مـدارس در حالـتچند مدرسه ای، شهری و بارگذاری مخـتل درنظـر گرفتـهمی شود. با توجه به مرور ادبیات ،نوآوری های مـد نظـر ایـنپژوهش به شرح زیر است:
درنظرگــرفتن تفکیــک جنســیتی در مــدارس وسروی ها؛
درنظرگرفتن بارگذاری مختل در سروی ها؛
درنظرگرفتن دانش آموزان خاص؛
به کارگیری مدل در مطالعة موردی؛
طراحی الگوریتم فرا ابتکاری برای مدل ارائه شده؛
درنظرگرفتن هم زمان پنجرة زمانی نـرم و سـختبرای ایستگاه ها.
بیان مسئله
تهران یکی از شهرهای درحال توسعه در ایران است. رشـد وتوسعة شهری همواره چالش برنامه ریزی حمش ونلـش و ارائـةخدمات شهری را در پی دارد. دانش آموزان به صـورت مکـرربر سیستم حمش ونلـش شـهری تـأث یر مـی گذارنـد. اسـتفادةدانش آموزان از سیستم حمـش ونلـش شـهری بـه دو صـورتاست. نـوع اول دانـش آمـوزانی کـه از سیسـتم حمـش ونلـش عمومی استفاده می کنند و نـوع دوم دانـش آمـوزان ی کـه ازسروی مدارس استفاده می کنند. اغلب دانش آموزانی که از سروی مدارس استفاده می کنند از زمان زیاد حمـش ونلـش ناراضی اند؛ بنابراین، ارائة مـدلی بـرای مسـیریابی سـروی مدارس که زمان حمش ونلـش را نیـز کـاهش دهـد، ضـروریبه نظر می رسد.
در این پژوهش، چهار مدرسه شامش دو مدرسة پسرانه و دو مدرس ة دختران ه درنظ ر گرفت ه ش ده اس ت. م دارس«ضـ حی» و «سـ ما» دخترانـ ه و مـ دارس «احسـ ان» و
«دانشمند» پسرانه هستند.
مدل مـورد بررسـی در ایـن تحلیـق شـامش مسـیریابیاتوب وس ه ای مدرس ه ب رای س وارکردن دان ش آم وزان از ایستگاه های اتوبوس و رساندن آن ها به مدارس خـود اسـت.در این مسئله، دانش آموزان خاص درنظر گرفته شـده انـد واتوبوس ها باید آن ها را از در منزل سوار کنند. همچنین، هر اتوبوس هرفیت ثابتی برای حمش دانش آموزان پسر، دختر و دانش آموزان خاص دارد و این موضوع همان مفهوم تفکیـکجنسیتی در اتوبوس است. با شرای ذکرشده، مسئلة مـوردنظر یک مسئلة مسیریابی اتوبوس شـهری چنـد مدرسـه ای همراه با بارگذاری مختل و تفکیک جنسیتی است.
مفهوم تفکیک جنسیتی در پژوهش حاضر به ایـن معنـیاست که دو نوع مدرسـه وجـود دارد: 1. مـدارس پسـرانه ؛ 2.
مدارس دخترانه. همچنین، درون سروی ها هرفیـت خاصـیبرای هر نوع دانش آموز )دختـر و پسـر( درنظـر گرفتـه شـدهاست؛ برای مثال، اگر هرفیت اتوبوس 20 نفر باشـد )10 نفـر برای دانش آموزان پسر و 10 نفر برای دانـش آمـوزان دختـر(،درصورتی که هرفیـت دانـش آمـوزان دختـر تکمیـش باشـد وهرفیت دانش آموزان پسر تکمیش نشـده باشـد- بـا اینکـه در اتوبوس فضـای خـالی وجـود دارد- دیگـر هـیچ دانـش آمـوز دختری نبایـد سـوار شـود. ایـن موضـوع ماننـد جابـه جـا یی مسافران در اتوبوس های شهری در تهران است. شـرای فـوقبه دلیش شرای خاص مطالعة موردی درنظر گرفته شده است.
همچن ین، در مس ئلة م ذکور س روی ه ا ملیدن د در ساعات مشخص و از پـیش تعریـ ف شـده ای بـه ایسـتگاه هـاسروی دهی کننـد کـه بـه ایـن امـر پنجـرة زمـانی گفتـهمی شـود. درواقـع هـدک، حضـور بـه موقـع سـروی هـا در ایستگاه های تعیین شده است.
مدل هـای پنجـرة زمـانی بـه دو صـورت کلـی تلسـیممی شود:
الف(‌مدل‌های‌سخت:‌در این نـوع مـدل هـا ی پنجـرةزمانی، وسایش نللیه باید به یک دانـش آمـوز در بـازة زمـانی سروی دهند، به عبارت دیگر، هر ایستگاه )ایستگاه J( یـک بازة زمانی سروی به صورت [HEt , HLt ] دارد که زمـان سروی حتماً باید در این بازه صورت گیرد.
ب(‌م ‌دله ای‌ن رم: در حال ت پنج رة زم انی ن رم ،سروی دهی تا حد معینی خارا از بازة تعیـی ن شـده مجـازاست؛ یعنی برای هر گره )دانش آموز( علاوه بـر یـک پنجـرةزمانی معین [HEt , HLt ] یک بازة زمانی دیگر بـه نـام ][SEt ,SLt تعریف می شود که بازة [HEt , HLt ] داخش آن قرار می گیرد و سروی هایی که خـارا از بـازة ,HEt ]
[HLt انجام می گیرد باید جریمة بسردازند.
در این پژوهش، حالت پنجرة زمانی سخت و نرم درنظر گرفته شده است کـه ترکیبـی از دو حالـت یادشـده اسـت .به این ترتیب، هر پنجرة زمانی شامش یک محدودة نرم و یکمحدودة سخت است، به طوری که محدودة نرم مشابه حالـت ب قابش نلض است، ولی محدودیت سخت نباید نلض شود. در بخش بعدی، یـک مـدل برنامـه ریـزی عـدد صـحیحخطی برای این مسئله مطرح می شود.
مدل سازی
در این بخش یک مدل برنامه ریزی عدد صـحیح بـرای حـشمسئلة توصیف شده توسعه داده می شود. علائـم بـه کاررفتـه برای مدل سازی مسئلة مورد نظر به شرح زیر است:
اندیس‌ها‌و‌مجموعه‌ها ‌
مجموعة دانش آموزان پسر )اعـم از معمـولی وd’ خاص(
مجموعة دانش آموزان دختر )اعم از معمـولی و
d” خاص(
D مجموعة تمام دانش آموزان D d ‘d ” d اندی دانش آموز S مجموعة همة مدارس
S اندی مدرسه
J مجموعة همة ایستگاه ها T مجموعة همة گره ها بهجز دپو T S J   t,t’ اندی همة گره ها به جز دپو
O اندی دپو
مجموعة دانش آموزانی که با گره t مـرتب انـد)اگر t مدرسه باشد ،Dt مجموعة دانش آمـوزانDt آن مدرسه و اگر t ایستگاه باشد ،Dt مجموعـة
دانش آموزانی را نشان می دهد که می توانند در آن ایستگاه سوار شوند(
مجموعة ایسـتگاه هـا یی کـه دانـش آمـوزانd
Jd می توانند در آنجا سوار شود K مجموعة همة اتوبوس ها k اندی اتوبوس
مجموعه ای از یک تا کش تعداد گره های ممکن
P
565837-1321

در مسئله P   S J J ‘  p شمارنده ای متعلق به مجموعة p

)1(
پارامترها
زمان جابه جایی بین گره t و دپوی مرکزی c0t
هرفیت اتوبوس k برای دانش آموزان پسر Q ‘k
هرفیت اتوبوس k برای دانش آموزان دختر Q ”k
زمان جابه جایی از گره t به گره t’ ctt ‘
زمان شروع سروی برای گره t ام بـا اتوبـوسk Ftk
ملدار زمان زودکرد شروع سروی اتوبـوسk ام به گره t ام MEtk
ملدار زمان دیرکرد شروع سروی اتوبـوسk ام به گره t ام MLtk
جریمة یک واحد زودکرد سروی PNE
جریمة یک واحد دیرکرد سروی PNL
حد پایین پنجرة زمانی سخت برای گره t ام HEt
حد باای پنجرة زمانی سخت برای گره t ام HLt
حد پایین پنجرة زمانی نرم برای گره t ام SEt
حد باای پنجرة زمانی نرم برای گره t ام SLt
متغیرها ‌
x tpk متغیر دودویی، برابـر یـک اسـت درصـورت ی کـه اتوبوس k از گره t در p امین نلطه از مسیر خود عبور کند. در غیر این صورت، برابر صفر است.
e اگر گره t’ بلافاصله پ از گره t توس اتوبـوسk t t k ویزیت شود برابر یک.
tdk متغیر دودویی، برابـر یـک اسـت درصـورت ی کـه دانش آموز d توسـ اتوبـوسk در گـرهt سـوارخودرو شود.
htk متغیر دودویی، برابر یک است اگر گره t آخـرینگرهی باشد که توس اتوبوس k ویزیت میشود.
ntdpk متغیر کمکی بهمنظور خطیکردن معادله

با استفاده از متغیرها و پارامترهـای توضـیح داده شـده،مسئلة مورد نظر به شکش زیر مدل می شود:
k K
minz 1 c ett ‘ c h0ttk c x0tt k1 PNE ME.tk PNL ML.tk
‘T t T k K tt k’ k K t S  k K t J  k K t J  t t ‘

tpk x t p’, 1,k htk
‘T
)2(
  tS k,K p,P
xtpk 1   pP k,K )3(
t T

wtdk M x tpk  tJ k,K )4(
d D tp P
wtdk Q ‘k  k K )5(

t J d d ‘dt
  wtdk Q”k  k K )6(
t J d d ”Dt
wtdk 1  d D )7(
t J k K d  xtpk xt p’, 1,k u 1  t t, T t: t k’, K p, P )8(
ttk

w xtdktpk   xt p k”  tS d,D p t,P k, K )9(
t J dp p 1 wtdk xtpk ntdpk 1 t d p, ,  P k, K )10(

wtdk xtpk  2ntdpk t d p, ,  P k,K )11(

xt p 1k xtpk   kK p,P )12(
t Tt T
 xtpk  wtdk  tJ k,K )13(
p P d D t Ftk M.(1xtpk ) Ft k’ ctt ‘  0  t t, T t: t k’, K p, P )14( Ftk SEt  t J k, K )15( Ftk SLt  t J k, K )16( MEtk HEt Ftk  t J k, K )17( MLtk Ftk HLt  t J k, K )18(
w x h e ntdk , tpk , tk , ttk , tdpk 0,1 )19(

تابع هدک بیانگر مینیمم کردن زمـان حمـش ونلـش اسـت . قسمت چهارم تابع هدک بـه زمـان حمـش ونلـش بـین دپـویقسمت اول تابع هدک مربوط به زمان حمش ونلش بـین هـر دومرکزی تا اولـین گـره ای مربـوط اسـت کـه اتوبـوس ویزیـتگره ممکن است. درواقع، این عبارت زمان حمش ونلش بین هـرمی کند. جزء سوم تابع هدک نیز که با توجه به شرای مسئلهدو ایستگاه یا هر دو مدرسه یا زمان بین یک ایسـتگاه و یـک)پنجرة زمانی نرم( به مدل اضافه شـده اسـت ، مـی کوشـد درمدرسه را محاسبه می کند. قسمت دوم و سوم تابع هـدک بـهپنجــرة زمــانی ســخت ســروی دهــد و بــه هزی نــههــایزمان حمش ونلش بـین گـره از دپـوی مرکـزی مربـوط اسـت . سروی ندادن به موقع )زودکرد یا دیرکرد( مربوط است.
محدودیت 2 بیان می کند اگر مدرسـه ای وجـود داشـتهباشد که بعد از آن هـیچ گـره ای اعـم از مدرسـه، ایسـتگاه،منزل دانش آمـوز خـاص وجـود نداشـته باشـد، آن مدرسـهآخرین گـره ای اسـت کـه یـک اتوبـوس ویزیـت مـی کنـد . محدودیت 3 نشـان مـی دهـد بـه هـر مکـانp از مسـ یر k حداکثر یک گره اختصاص داده مـ ی شـود . ایـن محـدودیتدرواقع رابطة بین دو متغیر t و p را بیان می کند. محدودیت 4 بیان می کند اگر اتوبوس k از ایستگاه t عبور نکنـد ،wtdkباید برابر صفر شود. محدودیت 5 درمورد هرفیـت اتوبـوسبرای دانـش آمـوزان پسـر اسـت . محـدودیت 6، محـدودیتهرفیت دانش آموزان دختری است که در هر اتوبوس حمـشمی شوند. محدودیت 7 اطمینان می دهد همة دانـش آمـوزانسوار اتوبوس شده اند و هیچ دانش آموزی در ایسـتگاه بـاقینمانده است .محدودیت 8 متغیر ‘utt k را محاسبه میکند و درصورتی که گره هـا ی t و ‘t پشـت سـر هـم از طریـق یـکاتوبوس ویزیت شوند، ‘ett k برابر یک می شود. محـدودیت 9 بیان میکند اگر اتوبوسی در p امین مسیر حرکـت خـود ازایستگاه t عبور کند و دانـش آمـوز l در آن ایسـتگاه حضـورداشته باشد، می تواند آن دانش آموز را سوار کند .محدودیت 10 و 11فل به منظور خطـی سـازی محـدودیت 9 بـه کـار می رود .محدودیت 12 بیان می کند مکـان هـای موجـود درمسیریابی هر اتوبوس باید به ترتیب صعودی پر شوند؛ یعنـیاتوبوس باید ابتدا حرکت اول و سس حرکـت دوم را انجـامدهد و به همین ترتیب مکان ها باید به شـکش صـعودی طـی شوند. محدودیت 13 بیان می کند تا یک دانشآموز به یـکایستگاه نرود ،نمی تواند سوار اتوبوس شود.
مجموعة محدودیت های 14 تا 16 جزء محدودیت هـای مدل های نرم در پنجـرة زمـانی هسـتند. بـد ین صـورت کـه محدودیت 14 زمان شروع سروی برای هر گره را مشخص می کند و محدودیت های 15 و 16 شرط پنجرة زمانی نرم را در مدل برآورده م یسـاز ند. محـدود یت هـای 17 و 18 نیـز تعداد واحد زمانی سروی نـدادن را در بـازة زمـانی سـخت تعیین می کنند. محدودیت 19 نیز باینری بـودن متغیرهـایتصمیم را بیان می کند.
مطالعة موردی
داده های مورد استفاده در این پژوهش برگرفتـه از مـدارسشهر تهران است. در این پژوهش ،چهـار مدرسـه شـامش دومدرسة پسرانه و دو مدرسة دخترانه در تهران درنظر گرفتـهشده است. مدارس «ضحی» و «سما» دخترانه )مدارس 1 و 2( و مدارس «احسان» و «دانشمند» پسرانه )مـدارس 3 و
4( هستند .13 دانش آموز از مدرسة ضحی )دانش آمـوزان 1 تا 13(، 17 دانش آموز از مدرسة سما) دانش آمـوزان 18 تـا30(، 15 دانش آموز از مدرسة احسان )دانش آمـوزان 31 تـا
45( و 15 دانش آموز از مدرسة دانشمند) دانـش آمـوزان 46 تا 60( درنظر گرفته شـده اسـت. در ایـن مسـئله ، ده گـرهوجود دارد. گره های 1 و 2 مدارس دخترانة ضـحی و سـما،گ رة 3 و 4 م دارس پس رانة احس ان و دانش مند هس تند .
گره های 5، 6، 7 و 8 ایستگاه ها و گره هـای 9 و 10 منـازلدان ش آم وزان خ اص اس ت. 4 ع دد اتوب وس ب رای حم ش دانش آموزان وجود دارد. هرفیت دانش آموزان دختـر و پسـربرای هر اتوبوس 10 نفر برای هر جن محسوب شده است .
در این مسئله، دانش آموزان خاص درنظر گرفته شـ ده انـد واتوبوس ها باید آن ها را از در منزل سوار کنند. همچنین، هر اتوبوس هرفیت ثابتی برای حمش دانش آموزان پسر، دختر و دانش آموزان خاص دارد و این موضوع همان مفهوم تفکیـکجنسیتی در اتوبوس است. براساس شرای یادشده، مسـئلةم ورد نظ ر ی ک مس ئلة مس یریابی اتوب وس ش هری چن د مدرسه ای همراه با بارگـذاری مخـتل و تفکیـک جنسـیتیاست. جدول 1 بیانگر زمـان حمـش ونلـش بـین هـر دو گـرهمتوالی است که ورودی مسئله محسوب می شـود. جـدول 2 نیز فاصلة زمانی دپو تا هر ایستگاه است. شایان ذکـر اسـتهر اتوبوس در اولین مسیر حرکت خود به ایستگاه یـا خانـةدانش آموز خاص می رود.
987196193266

گره

5

6

7

8

9

10

دپو

30

33

24

33

30

40

گره

5

6



قیمت: تومان


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