بخشی از مقاله
چكيده
مسئله زمانبندي ناوگان چندپايانهاي - MDVSP - يكي از مسائل مهم در فرآيند مديريت سيستم حمل ونقل است كه هدف آن انجام سفرهاي برنامه ريزي شده با استفاده بهينه از منابع موجود ميباشد. در كاربردهاي واقعي مسئله MDVSP، محدوديتهاي ديگري مانند محدوديت متوازن سازي پايانهها مطرح ميشود. در اين مقاله، براي متوازن سازي تعداد ناوگان عزيمت شده از هر پايانه به نسبت ظرفيت پايانه محدوديت جديدي پيشنهاد شده است تا تعداد ناوگان عزيمت شده از هر پايانه و همچنين تعداد رانندگان تخصيص يافته به هر پايانه نرمال سازي شود.
برآورده كردن اين محدوديت براي جلوگيري از تجمع بيش از حد ناوگان در يك پايانه و ترافيك ناشي از آن و همچنين توازن نيروي كار بين پايانهها ضروري به نظر ميرسد. با در نظر گرفتن محدوديت متوازن سازي، در اين مقاله مدل جريان چندمحمولهاي مسئله MDVSP را گسترش دادهايم. همچنين، از آنجايي كه برآورده كردن محدوديت متوازن سازي به صورت دقيق، بسيار سخت و البته غيرضروري به نظر ميرسد، محدوديت متوازن سازي به صورت يك محدوديت نرم در نظر گرفته شده است.
در اين مقاله براي فراهم سازي اين محدوديت از رويكرد مزايده-محور به همراه ايده هاي تجزيه استفاده شده است. نتايج محاسباتي نشان مي دهد كه رويكرد پيشنهادي مي تواند در زمان مطلوب مسئله موردنظر را حل كرده و همزمان محدوديت مورد نظر را برآورده سازد.
.1 مقدمه
مسئله زمانبندي ناوگان چندپايانهاي١ - MDVSP - يكي از مسائل مهم بهينه سازي تركيبياتي است كه در مديريت سيستمهاي حمل ونقل مطرح ميشود. اين مسئله يكي از كاربردهاي بسيار مهم مسائل جريان چندمحمولهاي ميباشد كه در حالت كلي، -NPسخت است .[1] در اين مسئله يك مجموعه از سفرهاي زمانبندي شده موجود است و هدف مسئله شامل موارد زير است:
تخصيص ناوگان حمل ونقل عمومي موجود در پايانهها به سفرهاي زمان بندي شده.
ارائه يك برنامه زمانبندي براي هر ناوگان.
به اين ترتيب براي هر ناوگان يك برنامه زمانبندي به صورت دنبالهاي از سفرهايي كه بايد اين ناوگان به صورت متوالي انجام دهد ارائه ميشود به نحوي كه هزينه اجراي تمام سفرها كمينه شود.
فرض كنيد T يك مجموعه سفر زمان بندي شده است و تعداد K پايانه وجود دارد. در يك برنامه زمانبندي براي يك ناوگانهر سفر بايستي دقيقاً يكبار انجام شود. هر پايانه k - k 1,..., K - ، شامل v ناوگان ميباشد.
هر سفر i T از مكان si شروع شده و در مكان ei خاتمه مييابد. زمان شروع سفر i T، ai است و مدت زمان انتقال از مكان si به ei، i ميباشد. هر زمانبندي براي يك وسيله نقليه بايستي از يك پايانه شروع شود و در نهايت به همان پايانه ختم شود. اين زمانبندي شامل يك دنباله از سفرها است كه براي هر دو سفر متوالي i و j رابطه ai i t i , j aj برقرار ميباشد.
جفت سفرهاي - i , j - كه در شرط فوق الذكر صدق ميكنند سفرهاي سازگار٢ ناميده ميشود. در اين رابطه t i , j زمان لازم براي انتقال از انتهاي سفر i به ابتداي سفر j است. هزينه زمانبندي براي يك وسيله نقليه مجموع هزينه انتقال بين سفرهاي متوالي و هزينه انتظار براي انجام سفرهاي زمانبندي شده است. همچنين اين هزينه شامل يك هزينه ثابت ميباشد كه همان هزينه راه اندازي يك وسيله نقليه از پايانه ميباشد. مسئله MDVSP تخصيص بهينه سفرها به ناوگان است به نحوي كه:
- هر سفر فقط به يك وسيله نقليه تخصيص يابد.
- هر وسيله نقليه يك دنباله از سفرها را انجام ميدهد به نحوي كه هر دو سفر متوالي سازگار باشند.
- هر وسيله نقليه سفر خود را از يك پايانه شروع ميكند و در انتهاي سفر به همان پايانه برميگردد.
- تعداد ناوگان عزيمت شده از هر پايانه بيشتر از ظرفيت آن پايانه نباشد.
- مجموع هزينه زمانبندي و هزينه ناوگان كمينه شود - استفاده از هر وسيله نقليه يك هزينه ثابت به تابع هدف اضافه ميكند. - .
تعدادي از محققين مسئله MDVSP را به صورت يك مسئله جريان چندكالايي عدد صحيح مدل سازي كردهاند - [2] و . - [3] در اين مدل هر پايانه به عنوان يك محموله در نظر گرفته ميشود. مدل رياضي يك مسئله MDVSP بر اساس يك شبكه اتصال٣ بيان ميشود كه سفرها و پايانهها توسط گرههاي شبكه نمايش داده ميشوند و اتصالات ممكن بين سفرها توسط كمانهاي شبكه مدل سازي ميشود. در اين صورت مسير يك وسيله نقليه توسط يك واحد جريان كه از پايانه شروع ميشود و به همان پايانه برميگردد نشان داده ميشود.
فرض كنيد سفرهاي متعلق به T بر اساس زمان شروع سفر مرتب شدهاند. شبكه اتصال جهت دار بدون دور G - V , A - را در نظر بگيريد كه به صورت زير تعريف ميشود. مجموعه V شامل يك گره براي هر سفر i T است و همچنين شامل دو گره - o - k و d - k - براي هر پايانه - k - k 1, ..., K ميباشد.
مسئله MDVSP به صورت مسئله - 1 - بيان ميشود [4] كه در آن تابع هدف مجموع هزينه پيمايش تمام سفرها را كمينه ميكند. محدوديت - الف - محدوديت پوشش دهي سفرها ناميده ميشود و تضمين ميكند كه هر سفر دقيقاً يكبار پيمايش شود. محدوديت - ب - محدوديت ظرفيت انبار است كه در آن v k ظرفيت ناوگان پايانه k است. قيد - ج - قيد توازن جريان در گرههاي شبكه است. همچنين قيد - د - محدوديت صفر و يك بودن متغيرهاست. مدل سازي - 1 - براي مسئله MDVSP داراي A K متغير و 2T K محدوديت ميباشد.
الگوريتم مزايده يكي از الگوريتمهاي مشهور است كه در ابتدا براي محاسبات موازي ارائه شد .[5] همچنين اين الگوريتم در محاسبات متوالي بسيار سريع عمل ميكند. الگوريتم مزايده سه شكل اصلي پيشرو4، معكوس5 و تركيبي دارد. در اين مقاله از رويكرد الگوريتم مزايده براي حل مسئله MDVSP در حضور محدوديت بودجه استفاده شده است. با توجه به مزيت هايي كه الگوريتم مزايده دارد و با توجه به نتايج محاسباتي بدست آمده به نظر مي رسد كه رويكرد پيشنهادي قابليت حل مسئله را با شرايط واقعي در نظر گرفته شده دارد. در ادامه اين مقاله در بخش دوم تعريف مسئله زمانبندي ناوگان چندپايانه اي با محدوديت متوازن سازي تعداد ناوگان ارائه شده است. در بخش سوم رويكرد الگوريتم مزايده و ايده تجزيه براي حل مسئله ارائه شده است. در بخش چهارم نتايج محاسباتي مقاله ارائه شده است. فصل پنجم جمع بندي مقاله به همراه راهكارهاي آتي را ارائه كرده است.
.2 زمانبندي ناوگان چندپايانهاي با محدوديت متوازن سازي
مسئله زمانبندي ناوگان چندپايانهاي با محدوديت متوازن سازي ناوگان به صورت مسئله - 2 - تعريف ميشود. تفسير تابع هدف و محدوديتهاي مسئله - 2 - ، مشابه مسئله - 1 - است؛ به جز اينكه محدوديت چهارم، قيد توازن ناوگان را نشان ميدهد كه با توجه به كاربردهاي عملي به صورت يك محدوديت نرم مدل سازي شده است. محدوديت متوازن سازي، ناوگان حمل ونقلي را به نسبت ظرفيت پايانهها تقريباً به صورت يكنواخت بين پايانهها توزيع ميكند. در نظر گرفتن اين محدوديت، با توجه به ضرورت توازن بار ترافيكي پايانهها و توازن رانندگان و امكانات تعمير و نگهداري در بين پايانهها ضروري به نظر ميرسد.
