نشریه تخصصی مهندسی صنایع، دوره 46، شماره 2، مهر ماه 1391، از صفحه 185 تا 194
ارائه یک مدل جدید ریاضی براي مسأله مسیریابی سرویس مدارس و حل
آن توسط الگوریتم پیشنهادي

جعفر رزمی*1 و ماریا یوسفی2
1استاد دانشکده مهندسی صنایع و سیستم ها-پردیس دانشکده هاي فنی-دانشگاه تهران
2دانش آموخته کارشناسی ارشد دانشکده مهندسی صنایع و سیستم ها-پردیس دانشکده هاي فنی-دانشگاه تهران
(تاریخ دریافت 6/12/90، تاریخ دریافت روایت اصلاح شده27/1/91 ،تاریخ تصویب 1/7/91)

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

واژه هاي کلیدي:مکانیابی -مسیریابی، مسیریابی سرویس مدارس، الگوریتم جستجوي پراکنده، الگوریتم بازپخت شبیه سازي شده، حمل و نقل چند منظوره،حمل و نقل تک منظوره

مقدمه
سرویس مدارس(SBRP) در تلاش براي ایجاد یک زمانبندي کارا براي سرویس اتوبوس مدارس است، به طوري که اتوبوس، دانش آموزان را در ایستگاهها سوار کرده و آنها را به مدارسشان میرساند. این در حالی است که باید محدودیتهاي مختلف نظیر حداکثر میزان ظرفیت اتوبوس، حداکثر زمان مجازي که دانش آموزان در اتوبوس سپري میکنند، پنجره زمانی مدرسه و غیره در نظر گرفته شده و لحاظ شوند. در این بخش تحقیقاتی را که روي SBRP انجام شده است مرور میکنیم. از زمانی که اولین مقاله در مورد SBRP توسط نیوتن و توماس[1] منتشر شد، این مسئله به طور پراکنده مورد مطالعه قرار گرفت، اما هنوز یک رویکرد کارا براي مسئله SBRP نیاز است. در اغلب تحقیقات ارائه شده در مورد فرضیات و محدودیت هایی که با کمک آنها میتوان دنیاي واقعی را بیشتر توسط این مسئله شبیهسازي کرد بحث شده است؛ از این رو لی و فو [2] به این نکته اشاره کردهاند که بیش از یک رویکرد براي مسئلهSBRP وجود دارد. به علاوه، مسائل مکانیابی و مسیریابی همواره از جمله مسائل پرکاربرد در بهینه سازي استفاده از منابع فیزیکی، انسانی و زمانی هستند که در موارد مختلف مورد استفاده عملی قرار گرفتهاند. در حال حاضر به دلیل افزایش نرخ بنزین از سویی و کمبود منابع فسیلی از سوي دیگر، مسائل مکان یابی – مسیریابی بیش از پیش میتواند به اقتصاد جامعه کمک کند. این در حالی است که با استفاده از این تحقیقات، میتوان از حجم مسافرتهاي روزانه کم کرد تا با این کار، بار ترافیک کمتر شده و به کاهش آلاینده هاي خطرناك هوا که در کشور ما و بخصوص در شهر تهران بیش از حد مجاز است، کمک کرد. بنا بر کاربرد، در موارد گوناگون، شکل مسئله با حفظ کلیت آن تغییر خواهد کرد. یکی از انواع کاربرد آن، در زمینه مسیریابی ناوگان حمل و نقل مدارس است که از این پس آن رابه اختصار ١SBRP مینامیم. این مسئله بسته به فرضیات مختلف در نظر گرفته شده، میتواند در چندین دسته قرار گیرد که در ادامه به آنها اشاره می کنیم. به این ترتیب مسیریابی
Email: [email protected] ، 88013102 : نویسنده مسئول : تلفن :88021067 , فاکس *

آنها این نکته را خاطر نشان کردهاند که بسیاري ازرویکردهاي موجود به ماهیت مسئله و مفروضات در نظرگرفته شده بستگی دارد.
در برخی موارد از مقالات منتشر شده در زمینه SBRPدر مرور ادبیاتهاي مسائلی که بسیار به آن شباهت دارند،استفاده میشود که از آن جمله میتوان به مقالات نگاشته شده توسط بودین و همکاران[3]،اسپادا و همکاران[4] و جزف ویز و همکاران[5]اشاره کرد. این مقالات از جمله مقالاتی هستند که در بسیاري موارد به آنها استناد شده است.
مسایلSBRP شامل زیرمسئلههاي کوچک تري میشود.
با توجه به تفکیکی که توسط دزروسیرز و همکاران[6]انجام شد، میتوان این مسئله را به پنج زیرمسئله تفکیک کرد: جمعآوري دادهها ،مکانیابی ایستگاههاي اتوبوس یا تخصیص دانشآموزان به ایستگاه-ها، مسیریابی اتوبوسها، تعدیل زمان شروع به کار مدارس و زمانبندي مسیرها. در مرحله جمعآوري دادهها، شبکهاي شامل موقعیت مکانی خانهها، مدرسه، ایستگاههاي اتوبوس تشکیل میشود و یک ماتریس مبدأ-مقصد بین آنها مشخص میشود. ماتریس بین این نقاط، یک ماتریس خاص است. براي یک شبکه مشخص در مرحله بعدي که مرحله مکانیابی ایستگاههاي اتوبوس است، از میان همه نقاط بالقوه، فقط یک سري به عنوان ایستگاه انتخاب می شوند و هر دانش آموز به یک ایستگاه تخصیص داده می شود. مسئله مکانیابی در بسیاري از مقالات به صورت یک مدل ریاضی کامل آورده شده است(هدا دربل و همکاران[7]) رویکردهاي حل هیوریستیکی براي مکانیابی ایستگاههاي اتوبوس به دو دسته اصلی شامل استراتژي٢LAR و استراتژي٣ARL تقسیم می شوند (لاپورت[8] و باورمن و همکاران[9]). استراتژي LAR ابتدا مجموعهاي از ایستگاههاي اتوبوس براي یک مدرسه را مشخص میکند و بعد دانشآموزان را به این ایستگاهها تخصیص میدهد. مسیرها براي این ایستگاههاي انتخاب شده ایجاد میشود. در این روش، انتخاب مکان ایستگاههاي اتوبوس و تخصیص دانشآموزان به این ایستگاهها بدون توجه به اینکه این انتخابها تا چه حد میتواند بر مسیرهاي ایجادشده تأثیر بگذارد ،انجام می گیرد. این روش منجر به تولید تعداد بسیار زیادي از مسیرها میشود. افرادي چون بودین و برمن[10]و دولاكو همکاران[11] و دزروسیرز و همکاران[6] همگی روش-هاي هیوریستیکی بر اساس استراتژي LAR را پیشنهاد دادهاند. در استراتژي ARL، دانشآموزان به خوشههایی تقسیم میشوند، در حالی که محدودیت ظرفیت خودرو در شکل گیري این خوشهها لحاظ میشود. در پی آن، ایستگاههاي اتوبوس انتخاب میشوند و مسیري براي هر خوشه ایجاد میشود. در نهایت دانشآموزان هر خوشه (مسیر) به ایستگاه اتوبوسی که همه ملزومات داده شده در مسئله مانند حداکثر تعداد دانشآموزان مجاز که میتوانند به یک ایستگاه تخصیص یابند، حداکثر میزان پیاده روي مجاز از خانه تا ایستگاه و کمترین فاصله بین دو ایستگاه ،تخصیص مییابند. افرادي چون چاپلو و همکاران[12] و باورمن و همکاران[9] از الگوریتمی که بر اساس استراتژي ARL کار میکند، استفاده کردهاند.
اسچیتکات و همکاران[13] به تازگی یک مدل ساده ریاضی را براي مکانیابی ایستگاههاي اتوبوس و مسیریابی بین آنها، در حالت تک مدرسهاي ارائه کردهاند. البته این مدل محدود به یک مدرسه است و فقط براي سایزهاي کوچک تصادفی (10 ایستگاه اتوبوس و 50 دانش آموز) آزموده شده است. پس از این مرحله، در مرحله مسیریابی اتوبوسها، مسیر اتوبوس براي رسیدن به هر مدرسه معین میشود. در بخش مسیریابی، مسیرهاي بین ایستگاههاي مدارس ایجاد میشود. مقالات زیادي در مورد ارائه مدل هاي ریاضی شامل مکانیابی و مسیریابی به طور همزمان و حل آنها منتشر شده است(کریستف دوهامبل و همکاران[14]، اسماعیل کاروگلان و همکاران[15] و محمدحسین زرندي[16]). الگوریتمهاي مورد استفاده در قسمت مسیریابی را میتوان به دو دسته اصلی شامل روش »ابتدا مسیریابی- بعد خوشهبندي« و روش »ابتدا خوشه بندي – بعد مسیریابی« تقسیم بندي کرد (بودین و برمن[10]). در روش »ابتدا مسیریابی- بعد خوشه بندي« یک مسیر اصلی توسط الگوریتم مسئله فروشنده دوره گرد ایجاد میشود که در آن همه ایستگاهها لحاظ میشود. سپس مسیر اصلی انتخاب شده به مسیرهاي کوچک تري تقسیم میشود که در هر یک از آنها محدودیتهاي مورد نظر لحاظ میشود. افرادي چون نیوتن و توماس [1] و بودین و برمن[10] از مبتکران و تکمیل کنندگان این روش هستند و در حل مسئله خود از این ایده استفاده کردند.
916432901192

در روش »ابتدا خوشهبندي – بعد مسیریابی« گروههايدانشآموزان به خوشههایی تقسیم بندي میشوند، بهطوري که هر خوشه توسط مسیري که بتواندمحدودیت هاي مربوطه را ارضاء کند، قابل سرویسدهیباشد. افرادي که این روش را به طور کامل براي اولین باردر SBRP به کار بردند، دولاك و همکاران[11]، چاپلو و همکاران[12] و باورمن و همکاران[9] بودند. براي مشاهده جزئیات روش مورد نظر، میتوانید کارهاي انجام شده توسط دولاك و همکاران[11] و لاپورت و اسمت[8]در این باره را مشاهده کنید.
از دو مرحله آخر یعنی تعدیل و تنظیم زمان شروع به کار مدارس و زمانبندي مسیرها، براي اولویت بندي در حالت چند مدرسهاي استفاده میشود. ناوگان حمل و نقل اتوبوس مدارس اغلب براي مدارس واقع در یک منطقه مورد استفاده قرار میگیرد، نه براي یک مدرسه به تنهایی. به علاوه، اتوبوسها بین چند مدرسه به اشتراك گذاشته میشود و به همین دلیل تنظیم ساعات باز و بسته شدن مدارس به همان اندازه زمانبندي اتوبوسها میتواند مهم باشد. از جمله مقالات ارائه شده در این زمینه میتوان به کرتز و همکاران [22] اشاره کرد.
در اغلب رویکردهاي حاضر، این زیرمسئلهها به طور جداگانه و سلسله مراتبی در نظر گرفته شدهاند. اگرچه این زیرمسئلهها مستقل نیستند و بسیار به یکدیگر مرتبط هستند، اما به دلیل پیچیدگی و سایز مسئله، زیرمسئله هاي نامبرده را یکجا در نظر نمیگیرند. به علاوه اغلب فقط تعدادي از زیرمسئلههايSBRP در نظر گرفته میشود. بخصوص تعیین مکان ایستگاههاي اتوبوس و تنظیم ساعات باز و بسته شدن مدارس در اغلب موارد به سیاست مسئولان ناوگان حمل و نقل بستگی دارد. بسیاري از محققان، مدل هاي خود را با این فرض طراحی کردهاند که این اطلاعات باید از قبل در اختیار آنها قرار گیرد.
اگرچه SBRP خودش به تنهایی یک مسئله واحد و مستقل است، اما هر یک از زیرمسئلههاي آن، یا ترکیبی از آنها میتواند در دسته مسائل بهینهسازي موجود قرار گیرد.
در جدول (1) سعی در دسته بندي مسئلهSBRP بر اساس خصوصیات آن نوع خاص از مسئلهSBRP داریم.
اگرچه راههاي زیادي براي دسته بندي انواع این مسئلهوجود دارد، اما ما بر جنبههاي کاربردي این مسئله تمرکز می کنیم. جدول (1) دستهبندي مقالات منتشرشده در این زمینه را بر اساس تابع هدفها و محدودیتهاي در نظر گرفته شده نشان میدهد.

مدل پیشنهادي
پیشفرض اولیه ما به این ترتیب است که یک سري از مدارس وجود دارند که متعلق به تعداد مشخصی از دانش آموزان است. هر مدرسه تعدادي ایستگاه بالقوه دارد که باید از میان این ایستگاهها تعداد ایستگاه هاي مورد نیاز را که بتوانند همه دانش آموزان را سرویس دهی کنند انتخاب کرد. ممکن است براي یک دانشآموز مقدور باشد که به بیش از یک ایستگاه برود؛ در این صورت همه ایستگاههاي پیشفرض باید مشخص باشند و در نهایت هر دانشآموز میتواند فقط و فقط به یک ایستگاه تخصیص یابد. مجموعهاي از خودروها که در این تحقیق غیر همگن نیز هستند در نظر گرفته شده است. این خودروها بر حسب ظرفیت شان باید به مدارس مختلف تخصیص یابند، به طوري که مجموع ظرفیت خودروهاي تخصیص داده شده به آن مدرسه، کمتر یا مساوي با تعداد همه دانش آموزان مربوط به آن مدرسه باشد. نوع حمل و نقل دانش آموزان تک منظوره است؛ یعنی دانشآموزان مدارس مختلف نمیتوانند در یک خودرو با هم باشند. در نهایت باید معلوم کرد که از میان خودروهاي تخصیص یافته به هر مدرسه، چه خودرویی، کدام ایستگاهها را زیر پوشش قرار میدهد وکوتاه ترین مسیر براي هر خودرو از مدرسه تا ایستگاهها کدام است. لازم به ذکر است که این تور در نهایت با بازگشت خودرو به همان مدرسه مبدا کامل می شود.
مدل ریاضی پیشنهادشده در این تحقیق، در ادامه ارائه شده و در مورد محدودیتهاي آن نیز توضیحات لازم داده خواهد شد. این مدل بر اساس مدل٤ VRP ساده ایجاد شده است و اساس آن بر مبناي مدلی است که اسچیتکات و همکاران[13]ارائه داده اند. در مدل آنها فقط یک مدرسه در نظر گرفته شده بود که با مفروضات واقعی سنخیت ندارد؛ چرا که در عمل یک مسئلهSBRP براي فقط یک مدرسه، حالت نامعقولی به حساب میآید. در ضمن در مدل آنها خودروها به شکل همگن در نظر گرفته شده است که امکان ایجاد مسیرهایی را با تعداد کمی ازدانشآموزان، از نظر اقتصادي غیرمنطقی می کند. در اینمدل، ابتدا یک سري از ایستگاهها از میان همه ایستگاههاانتخاب میشوند، به صورتی که بتوانند همه دانش آموزان رازیر پوشش قرار دهند و سپس همه دانشآموزان بهایستگاههاي مربوطه تخصیص می یابد، به طوري که هردانش آموز فقط و فقط به یک ایستگاه تخصیص یابد و در نهایت، خودروهاي تخصیص یافته به هر مدرسه مشخص میشوند. سپس کوتاه ترین مسیر ممکن براي هر خودرو ایجاد میشود، به طوري که از مدرسهاي که از آن شروع به حرکت کرده است ،به ایستگاههاي مربوطه رفته و در نهایت به همان مدرسه مبدا بازگردد.

پارامترها و متغیرها I:مجموعه همه مدارس
J:مجموعه همه ایستگاههاي بالقوه
K:مجموعه همه خودروها
L:مجموعه همه دانشآموزان
N: تعداد مدارس Cij: فاصله بین نقطه i و نقطه ∪∈ ،j
Qk: ظرفیت خودروي k Sij:متغیر باینري نشان میدهد که دانش آموز l میتواند به ایستگاه j برود که در این صورت مقدار آن برابر با 1 خواهد بود.
QQij: متغیر باینري است که اگر ایستگاه j متعلق به مدرسه i باشد، مقدار آن برابر با 1 خواهد بود.
متغیرهاي تصمیم Xijk:متغیر باینري است که مقدار آن برابر با 1 خواهد بود، در صورتی که از نقطه i به نقطه jبا خودروي k (مسیرk)
برویم ∪ ∈ ،
Yjk: متغیر باینري است که مقدار آن برابر با 1 خواهد بود، در صورتی که خودروي k از ایستگاه j عبور کند و در غیر این صورت مقدارش صفر است.
Wjlk: متغیر باینري است که مقدار آن برابر با 1 خواهد بود، در صورتی که دانشآموز l توسط خودروي k در ایستگاه j سوار خودرو شود.
Zij: متغیر باینري است که مقدار آن برابر با 1 خواهد بود، در صورتی که ایستگاه jبراي مدرسهiبه صورت بالفعل درآید.
utk’: متغیر کمکی براي محدودیت حذف زیر تور.
مدل ریاضی
(1)
63000-192016

(2)
، ∈

(3)

(4)

(5)

− 1

،∈،∈
≥ ∀ ∈، ∈
≤ 1 ∀ ∈
≤ ∀ ∈ ، ∈
670634063

،
(10)
∈ ،∈
≤ ∀ ∈ ، ∈،∈ (11)

(12)
∈0،1 ∀ ∈ ،∈
∈0،1 ∀ ،∈∪ ، ≠
∈0،1 ∀ ∈، ∈،∈
≥ 0 ∀∈ ،∈
∈0،1 ∀ ∈ ،∈

در این قسمت مدل ارائه شده بیشتر تشریح میشود. تابع هدف مسئله (1) سعی در کمینه کردن مسافت پیموده شده توسط همه خودروها را دارد. میتوانcij را از نوع هزینه نیز در نظر گرفت. محدودیت (2) به ما این اطمینان را میدهد که اگر گره iتوسط خودرو kسرویس دهی می شود، پس باید یک مسیر دوجانبه وجود داشته باشد که خودروي k وارد گره i شود و از این گره نیز خارج شود.
محدودیت (3) به ما اجازه نمیدهد که بیش از ظرفیت خودرو به دانشآموزان در ایستگاههاي مختلف سرویسدهیم. محدودیت شماره (4) این نکته را خاطر نشانمی کند که هر ایستگاه، حداکثر از یک خودرو سرویسمی گیرد و ممکن است برخی از ایستگاهها جزو نقاط بهینهما نباشند و در اصل هیچ خودرویی به آنها خدمت رسانینکند. محدودیت (5) به این موضوع توجه دارد که هر مسیر حداکثر میتواند یک بار سرویس دهی شود. محدودیت شماره (6)، محدودیت حذف زیرتور است. از آنجا که این مسئله مشابه سایر مسائل مکان یابی- مسیر یابی نیست، پس محدودیت حذف زیرتور به این شکل نوشته شده است. در سایر مسائل، مشتریان یا همان نقاط سرویس گیرنده ثابت فرض شده اند و دپوها یا نقاط سرویس گیرنده مکان یابی میشوند؛ در حالی که در این مسئله، مدارس که همان دپوهاي سرویس دهنده ما هستند ثابت و مکان ایستگاهها که همان مشتریان سرویس گیرنده هستند، متغیر در نظر گرفته شدهاند. به عبارت دیگر، ایستگاهها باید مکان یابی شوند. پس به جاي استفاده ازN که تعداد ثابت نقاطی است که مسیریابی برایشان انجام میگیرد، یعنی تعداد ثابت ایستگاهها در این محدودیت از ∈ ∑ ∈ ∑ استفاده میکنیم، که نشان دهنده تعداد ایستگاههاي تحت سرویسدهی هستند.
این محدودیت اولین بار است که به این شکل مورد استفاده قرار گرفته شده است. محدودیت (7) ضامن تخصیص ایستگاه به مدرسهاي است که تخصیص این ایستگاه به مدرسه مربوطه بی اشکال تشخیص داده شده است. محدودیت (8) نشان میدهد که هر ایستگاه میتواند حداکثر از یک خودرو خدمت بگیرد. محدودیت شماره (9) نیز ضامن این نکته است که هر دانشآموز فقط باید یک بار از یک ایستگاه و توسط یک خودرو سرویس بگیرد.
محدودیت (10) نشان میدهد که ایستگاه j به مدرسه i تخصیص می یابد؛ اگر از ایستگاه j به مدرسهi مسیري وجود داشته باشد.
محدودیت (11) زمانی به یک خودرو اجازه میدهد به ایستگاهی تخصیص یابد که دانشآموزي به آن ایستگاه تخصیص داده شده باشد (در حالتی که دانشآموزان یک ایستگاه انتخاب یا انتخابهاي دیگري غیر از آن ایستگاه را نیز داشته باشند). محدودیت (12) نشان میدهد که همه دانشآموزان باید سرویسدهی شوند. در نهایت محدودیت هاي (13) و (14) و (15) و (16) و (17) نوع هر یک از متغیرها را نشان میدهند.

روش حل مسئله
به طور کلی دو دیدگاه در حل مسائل مکانیابی و مسیریابی وجود دارد. در دیدگاه اول، با استفاده از روش هاي دقیق مانند شاخه و کران، برنامه ریزي پویا ،برنامه ریزي عدد صحیح و برنامه ریزي غیرخطی ،مسئله به صورت بهینه حل میشود. روشهاي حل تقریبی که به یافتن جواب هاي خوب و نه لزوماً بهینه میانجامد، در دیدگاه دوم دستهبندي میشوند. روشهاي ابتکاري و فراابتکاري در این دسته قرار میگیرند. روشهاي ابتکاري بر اساس نحوه مدل سازي رابطه میان زیرمسئلههاي مکان یابی و مسیریابی، به چند دسته تقسیم میشوند.
یکی از پرکاربردترین روشها، رویکردهاي متوالی هستند. در این رویکرد، ابتدا مسئله مکانیابی- تخصیص بر اساس کمینه سازي فاصله مستقیم میان نقاط توزیع و مشتریان حل میشود و در ادامه، مسیرهاي بازدید مشتریان تخصیصی به هر دپو تعیین می شود. در این روشها ،بازخوردي از مرحله مسیریابی به مرحله مکانیابی انجام نمیگیرد. همان طور که در مرور ادبیات به آن اشاره شد، کمتر مقالهاي یافت میشود که از روشهاي متاهیوریستیکی در حل مسئله به شکل یکپارچه استفاده کرده باشد و بازخورد مسیریابی در بخش مکان یابی در نظر گرفته شده باشد. بر اساس تحقیقات انجام شده، از میان مقالاتی که توسط محقق مطالعه شدهاند، فقط اسچیتکات و همکاران[13] براي حل مسئله، به طور دقیق از خود مدل ریاضی مسئله، کمک گرفتهاند و در بیشتر مواقع، حل بر اساس روشهاي دو مرحلهايِ ابتدا خوشهبندي و بعد مسیریابی یا روش حلِ ابتدا مسیریابی و سپس خوشه بندي انجام می شود. مطابق تعریف نگی و سلهی[21] مکان یابی یک مسئلهNP-hard است. مطابق با مقاله لی و فو[2] با در نظر گرفتن مسیریابی با مسئله مکانیابی به طور همزمان، پیچیدگی مسئله بسیار بیشتر میشود، بنابراین می توان نتیجه گرفت که مسئله مکان یابی -مسیریابی یک مسئله NP-hard است. در این تحقیق سعی شده است از خود مدل ریاضی براي حل مسئله توسط دو الگوریتم متاهیوریستیکی قوي استفاده شود که یکی دیگر از نوآوريهاي این مقاله به حسابمی آید؛ چرا که مسئله به صورت یکجا و بر اساس مدلریاضی آن حل شده است.
الگوریتمهاي در نظرگرفته شده، یکی الگوریتم
جستجوي پراکنده یاSS) ScatterSearch)است که میتوانبه نوعی آن را شکل تکامل یافتهتري نسبت به الگوریتمژنتیک دانست که لازم به ذکر است که این الگوریتم در مسائل مربوط به مسیریابی، جواب هایی به مراتب بهتر نسبت به الگوریتم ژنتیک کسب کرده است. الگوریتم دیگر
بازپخت شبیهسازي شده یا SA)Simulated Annealing) است.

نحوه عملکرد الگوریتم جستجوي پراکنده
الگوریتم جستجوي پراکنده، یکی از روش هاي تکاملی براي حل مسائلNP-hard است که اولین بار در سال1977 توسط گلوور براي حل مسائل برنامه ریزي عدد صحیح ارائه شد. الگوي کلی الگوریتم جستجوي پراکنده به عنوان یک روش فراگیر براي حل مسائل NP-hard در سال 1998 توسط گلوور، مبناي همه اجراهاي الگوریتم جستجوي پراکنده قرار گرفت. این الگوریتم از 5 فاز اصلی حل تشکیل شده است که در سال 2003 مارتی لاگورا این مراحل را به ترتیب مطرح کرد. این مراحل به این ترتیب هستند:

1-DiversificationMethod: براي تولید گردایه اي از جواب هاي آزمایشی مختلف و پراکنده به کار می رود.
2- ImprovementMethod:یک جواب آزمایشی را به یک یا چندین جواب آزمایشی بهتر(در همسایگی آن) در صورت وجود تبدیل می کند.
3-ReferenceSetUpdateMethod: روشی است براي ساختن و حفظ یک مجموعه مرجع شامل b تا از بهترین جواب هاي پیداشده(تعداد اعضاي این مجموعه اغلب کوچک و کمتر از 20 است). عضوهاي این مجموعه بر اساس دو صفت کیفیت و پراکندگی انتخاب می شوند.
SubsetGenerationMethod: روشی است که روي مجموعه مرجع عمل کرده و زیرمجموعه ايr عضوي از عناصر مجموعه مرجع براي عمل ترکیب می سازد.
SolutionCombinationMethod: روشی است که یک زیرمجموعه جواب را گرفته و از ترکیب عناصر آن، جواب یا جواب هاي جدیدي به وجود می آورد.
همان طور که در مدل ریاضی مشاهده میکنید، در این مدل چهار متغیر ، ، ، وجود دارند که یکی بر اساس دیگري به دست میآید که در قسمت بهبود جواب ها از یک بهبود چهار مرحلهاي استفاده شده است. چنانکه ابتدا به دست آمده را با opt-2 تغییر دهیم، بر اساس این تغییر سایر متغیرها نیز تغییر میکنند؛ چرا که سه متغیر دیگر بر اساسz به دست میآیند.
اگر تغییر حاصله سبب بهبود تابع هدف شود، این تغییر حفظ شده و در غیر این صورت به حالت اولیه در میآید. وارد مرحله دوم بهبود میشویم؛ در مرحله بعدz تغییري نمیکند، بلکه y بر مبناي opt-2 تغییر میکند. در نتیجهw و x که بر مبناي y و z به دست میآیند، بر حسب تغییر تغییر کرده و در صورت بهبود تابع هدف، بهبود آنها حفظ میشود. به این ترتیب، چرخه ذکرشده در مورد w و xاعمال میشود. به این ترتیب در هر بار استفاده از opt-2 یکبار z، دوبار y، سه بار w و چهار بار x بهبود مییابند.
براي به دست آوردن مجموعه مرجع از 20% کل جواب ها استفاده شد که نصف آنها بر اساس کیفیت جوابهاي حاصله و نصف دیگر آن نیز بر اساس پراکندگی جواب ها انتخاب میشوند. تابع پراکندگی که براي انتخاب نصف دوم مجموعه مرجع انتخاب شده است، به این صورت تعریف شده که بهترین جواب را به عنوان مرجع در نظر میگیریم و سپس آرایههاي هر جواب در هر یک از ماتریسهاي ، ، ، را با آرایههاي مرجع همان ماتریس ها به صورت متناظر مقایسه کرده و در نهایت 10 درصد از جواب هایی که حداکثر امتیاز را کسب کردهاند، به عنوان جواب هاي پراکنده در مجموعه مرجع قرار میدهیم.
در بخش ترکیب جوابها نیز از روشcrossoverیا همان ترکیب ماتریسها در چهار مرحله استفاده شده است که باعث به دست آمدن جوابهاي بهتري شده است. لازم به ذکر است در این روش حل، با هر تغییر ایجادشده، شدنی بودن جواب در همان مرحله سنجیده میشود؛ چرا که به دلیل دوبعدي بودن ماتریسهايw و x، با خارج شدن جواب ها از حالت شدنی، ادامه کار و شدنی کردن دوباره جواب ها بسیار زمان بر و مشکل است و سبب بالا رفتن زمان حل مسئله میشود.

جدول 2: مقایسه جواب هاي به دست آمده از الگوریتم ارائه شده جستجوي پراکنده با جواب هاي دقیق

ردیف تعداد دانش آموزان تعداد
خودروها تعداد
ایستگاه هاي بالقوه تعداد
مدارس SA SS GAMS خطا (%)
تابع
هدف زمان (ثانبه) تابع
هدف زمان (ثانبه) تابع
هدف زمان (ثانبه) 1 16 2 5 4 330 0,00078 330 0,00045 330 0,03 0
25 3 6 4 480 0,0061 480 0,0047 480 0,09 0
33 4 8 4 660 0,0140 660 0,0150 660 1,32 0
45 6 11 6 1290 0,091 1290 0,047 1290 5,39 0
3751 1,26
65 10 17 9 8127 15,12 3565 0,9 3495 348 1,9
120 19 27 12 8065 12,50 7925 16720,15 1,7
175 26 36 15 11751 23,12 11525 23,076 11185 85324,57 2,01
8 215 31 42 18 20852 141,34 18750 120,908 – –
9 225 35 42 19 24765 156,402 20335 119,006 – –
10 240 37 49 21 29571 415,76 27480 334,221 – –

پس از کدکردن مدل ریاضی توسط نرم افزار GAMS نتایج حاصل را با نتایج به دست آمده توسط الگوریتم جستجوي پراکنده پیشنهادي و نیز الگوریتم بازپخت شبیهسازي شده مقایسه کردیم. نتیجه مقایسه جواب هاي به دست آمده از نرم افزار GAMS، با جواب هاي حاصل از الگوریتم جستجوي پراکنده پیشنهادي و الگوریتم بازپخت شبیهسازي شده را در جدول (2) مشاهده میکنید.
همان طور که مشاهده میکنید، در جدول (2) 10مسئله با اندازههاي متفاوت در نظر گرفته شده است. ابعاد این مسئله را می توان هم با تغییر تعداد دانشآموزان و هم با تغییر تعداد ایستگاهها و در نهایت با تغییر تعداد مدارس بزرگ، کوچک و یا متوسط در نظر گرفت. جواب هاي به دست آمده از روش الگوریتم جستجوي پراکنده تا مسئله شماره چهارم به طور دقیق برابر با جواب هاي دقیق حاصل از GAMS است و درصد خطا برابر با صفر شده است. از مسئله شماره پنج مثالها به شدت NP-hard میشوند. جواب هاي حاصله با داشتن خطاهایی در حدود 0,019، 0,017 و 0,021 در مقایسه با جواب دقیق ،جواب هاي بسیار خوبی هستند، چرا که باید به زمان حل جواب نیز دقت شود. الگوریتم جستجوي پراکنده در مثال شماره 6، جواب را در زمانی معادل 0,0003 زمان مورد نیاز نرم افزار GAMS به دست آورده است و براي مسائل شماره 8 تا 10 نرم افزار GAMS نتوانست جوابی را به دست بیاورد، اما الگوریتم جستجوي پراکنده تعدیل شده در زمان هاي بسیار معقول توانست جواب هاي دقیقی به دست آورد. همچنین متوسط خطا براي 7 نمونه مسئله اول که هر دو روش حل جواب داده اند، برابر با 0,0081 است. این میزان خطا با توجه به زمانهاي حل دو روش، بسیار ناچیز است. با توجه به موارد ذکرشده، کارایی الگوریتم جستجوي پراکنده تعدیل شده نسبت به روش هاي دقیق واضح است.
همچنین با توجه به جدول (2)، جواب هاي به دست آمده از الگوریتم جستجوي پراکنده پیشنهادي، هم از نظر زمان و هم از نظر کیفیت ،جواب هاي مناسبتري نسبت به الگوریتم بازپخت شبیهسازي شده هستند.

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

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

Newton، R.M. and Thomas، W.H. (1969). “Design of school bus routes by computer.”Socio-Economic Planning Science،s 3 (1)، 75-85.
Li، L. and Fu، Z. (2002). “The School Bus Routing Problem: a casestudy.”Journal of the Operational research Society، 58، 1642-1651.
Bodin، L.D. (1975). “A taxonomic structure for vehicle routing and scheduling problems.”Computers and Urban Society، 1، 11-29.
Spada، M.، Bierlaire، M. and Liebling، Th.M.(2005). “Decision-aiding methodology for theschool bus routing and scheduling problem.”Transportation Science، 39.
Jozefowiez، N.، Semet، F. and Talbi، E.G.(2008). “Multi-objective vehicle routing problems.”European Journal of Operational Research، 189 (2)، 293-309.
Desrosiers، J.، Soumis، F.، Desrochers، M.and Sauve، M.،1986b. “Methods for routing with time windows.”European Journal of Operational Research، )2( 32، 236-.542
Houda، D.، Bassem، J.، Saïd، H. and Habib، C.(2012). “Genetic algorithm with iterated local search for solving a location-routing problem.”Journal of Expert Systems with Applications، 39 (2012) 2865–2871.
Laporte، G.and Semet، F.(2002). Classical heuristics for the capacitated VRP.In:Toth، P.،Vigo، D.(Eds.)، The Vehicle Routing Problem. SIAM، Philadelphia، PA،PP.109-.821
Bowerman، R.، Hall، B. and Calamai، P.(2001). “A multi-objective optimization approach to urban school bus routing: formulation and soloution method.” Transportation ResearchPart A 29 (2)، 107-.321
Bodin، L.D.andBerman، L.(1979). “Routing and scheduling of school buses by computer.” Transportation Science، )2( 31، 113–.921
Dulac، G.، Ferland، J.A. and Forgues، P.A.(1980). “School bus routes generator in urban surroundings.”Computers and Operational Research، )3( 7، 199-.312
Chapleau، L.،Ferland، J.A. and Rousseau، J.M.(1985). “Clustering for routing in densely populated areas.”European Journal of Operational Research، 20 (1)، 48-57.
Schittekat، P.، Sevaux، M. and Sorensen، K.(2006). A mathematical formulation for a school bus routing problem. In: Proceedings of the IEEE 2006 International Conference on Service Systems and Service Management، Troyes، France.
Christophe،D.، Philippe، L.، Christian، P. and Caroline، P.(2010). “AGRASP×ELS approachforthecapacitatedlocation-routingproblem.”Journal of Computers & Operations Research، 37 (2010) 1912 – 1923.
Ismail، K.، Fulya، A.، Imdat، K. and Berna، D. (2011). “A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery.”Journal of European Journal of Operational Research، 211 (2011) 318–332.
Mohammad Hossein، F.، Ahmad، H.and Soheil، D. (2011). “The multi-depot capacitated location-routing problem with fuzzy travel times.”Journal ofExpert Systems with Applications، 38 (2011) 10075–10084.
Braca، J.، Bramel، J.، Posner، B. and Simchi-Levi، D.(1997). “A computerized approach to theNew York City school bus routing problem.”IIE Transactions، 29، 693–702.
Corberلn، A.، Fernلndez، E.، Laguna، M. and Mart،ی R.(2002). “Heuristic solutions to theproblem of routing school buses with multiple objectives.”Journal of Operational Research Society، 53، 427–435.
Bektas، T. and Elmastas، S. (2007). “Solving school bus routing problems through integerprogramming.”Journal of the Operational Research Society، 58 (12)، 1599–1604.
Fügenschuh، A. (2009). “Solving a school bus scheduling problem with integerprogramming.”European Journal of Operational Research، 193 (3)، 867–884.
Nagy، G. and Salhi، S. (2007).“Location-routing: Issues، models and methods (Invited Review).”European Journal of Operational Research، 177: 649-672.
Cortes، C.E.، Matamala، M. and Contardo، C.(2011). “The pickup and delivery problem with transfers: formulation and a branch-and-cut soloution method.”European Journal of Operational Research، 200، 711.427
واژه هاي انگلیسی به ترتیب استفاده در متن
School Bus Routing Problem
Location-Allocation-Routing
Allocation-Routing-Location
Vehicle Routing Problem



قیمت: تومان


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