پایان نامه مدل ها و روش های، مكان يابي و مسير يابي
چكيده
مسأله مكانيابي- مسيريابي يك زمينه تحقيقاتي در حوزه مطالعات موقعيتيابي ميباشد كه داراي ويژگيهاي بارزي است. اين ويژگيها توجّه خاصي به مسائل زيربنايي مربوط به مسيريابي وسايل نقليه دارند. با وجود آنكه مطالعات زيادي روي جنبههاي گوناگون تئوري مكانيابي صورت گرفته، اما مسأله مكانيابي- مسيريابي آنچنان كه بايد مورد توجّه قرار نگرفتهاست. هدف ما اين است كهاين تحقيق يك بازنگري كاملي از روشهاي مكانيابي- مسريابي و همچنين مقدمهاي باشد با دسترسي سريع و آسان براي افرادي كه روي زمينههاي ديگر از نظريه مكانيابي مطالعه ميكنند.
در ادامه يك مساله مسير يابي مكان يابي مركب را در نظر مي گيريم. يك شبكه كمكي تعريف مي كنيم و يك فرمول فشرده از مساله در عباراتي از يافتن مجموعه مسيرها در شبكه كمكي كه قيود اضافي را تكميل مي كند، ارائه مي كنيم. حل برنامه ريزي خطي براي مدل در نظر گرفته شده يك كران پايين آغازين ايجاد مي كند همچنين در روش گرد كردن كه حل آغازين براي هيورستيك جستجوي تابو ايجاد مي كند به كار برده مي شود. بعلاوه، يك كران پايين متفاوت روي ساختار مساله ارائه مي دهيم. نتايج آزمايش محاسباتي روي يك مجموعه از نمونه هاي تصادفي ايجاد شده، ارائه مي شود.
همچنين يك بسط طبيعي ازمساله هاي مكانيابي نقاط دستگاهها ارائه شده است كه در آن دستگاهها گسترده هستند،يعني آنها كه نمي تواتند بوسيله نقاط جدا نمايش داده شود اما بصورت برخي ازساختارهاي چند بعدي ،مانند خطوط مستقيم،پاره خط،منحني هاي يا دواير چند وجهي نمايش داده مي شود.در اين مقاله يك مرور از كار گسترده روي مكان يابي دستگاههاي بسط يافته در فضاي پيوسته ارائه شده است. فاصله در دانش شناخته شده و پيشنهادهايي براي تحقيقات بيشتر ارائه شده است.
در بخشي ديگر از اين پايان نامه مساله دوري ميانه هدف تعيين يك دور ساده از ميان يك زير مجموعه از رئوس يك گراف شامل دو هزينه: يك هزينه مسير يابي متناظر با خود دوري،و هزينه عدم تخصيص رئوس روي دوري براي رئوس ملاقات شده است، در نظر گرفته مي شود. هدف مينيمم كردن هزينه مسيريابي به شرط يك كران بالا براي هزينه تخصيصي كل است. اين مساله در مكانيابي شالوده هاي ارتباطي و حمل و نقل شكل دايره ايجاد مي شود. ما يك مدل خطي صحيح مخلوط ارائه كرديم ، و با معرفي كلاسهاي اضافي نامساويهاي معتبر مهم بسط داديم. روشهاي جداسازي بهبود داده شدند و يك الگوريتم شاخه و كران دقيق توصيف شده است. نتايج محاسباتي روي نمونه هايي از كتابخانه مساله فروشنده دوره گرد[1] كلاسيك ,و نمونه هاي تصادفي توليد شده كارايي الگوريتم ارائه شده را تاييد كرد. يك كاربرد در رابطه با شهر ميلان(ايتاليا) همراه با حل محاسباتي معقول حل شده است
1-1 مكانيابي، مسيريابي و مكانيابي- مسيريابي: 9
2.1. كاربردهاي مكانيابي-مسيريابي. 13
مروري بر كارهاي انجام شده در مكان يابي مسير يابي. 15
2-1- روشهاي جواب دقيق براي مسائل قطعي: 18
2-2 روشهاي جواب غيرقطعي براي مسائل قطعي. 23
2-2-1. طبقهبندي و يك بازنگري از روشهاي مساله مكان يابي مسيريابي: 23
2-2-2 روشهاي مبتني بر دستهبندي.. 25
2-2-4. روش سلسله مراتبي (مرتبهاي) 30
2-3-1- مسألههاي مكان يابي فروشنده دورهگرد: 34
2-3-2مكانيابي سفر تصادفي با چند ماشين: 37
2-3-3 مكانيابي-مسيريابي پويا: 39
2-4- مسائلي با ساختار مراتبي غيراستاندارد 41
2-4-1 مسأله مكان حمل و نقل: 42
2-4-2 مسأله مسيريابي-مكان-بسيار به بسيار. 42
2-4-3 مسألههاي تخصيص –مسيريابي ماشين. 45
يك مدل فشرده و كرانهاي نزديك براي مساله مسير يابي-مكان يابي مركب.. 50
مكان يابي پيوسته ساختار هاي بعدي.. 78
4-.1 مكان يابي خطوط در صفحه. 81
4-2-بسط مساله هاي مكان يابي خط مسطح. 87
4-2-1جايگذاري بيش از يك خط. 87
4-2-2 مساله مكانيابي خط محدود شده 89
4-2-3-تخمين خطي هدفهاي ساده 91
4-3-مكانيابي ديگر دستگاههاي خطي. 92
4-3-3 مكانيابي ابرصفحه در فضاي نرمال. 95
4-5- مكانيابي منحني هاي چندوجهي. 102
4-5-1 منحني هاي چند وجهي مقيد خميده(طول) 103
2-5-2-منحني هاي چندوجهي خميده 107
مكانيابي دورهاي ميانه در شبكه ها 112
5-1.مدل براي مساله فروشنده دوره گرد 113
5-2-2 نامساويهاي تخصيص (5-10) 119
5-2-3 نامساويهاي همبندي پوشش(5-14) 119
5-3 الگوريتم انشعاب و برش… 121
عبارت (مكانيابي- مسيريابي) نبايد ما را دچار اشتباه سازد. زيرا اين مسأله يك مسأله واحد خوشتعريف مانند مسأله فروشنده دورهگرد نميباشد و بايد بهصورت مجموعهاي از مسائل و تئوريها در حوزة مكانيابي عنوان شود.
به هر صورت ما ترجيح ميدهيم كه به مسأله مكانيابي –مسيريابي[2] بهصورت روندي براي مدلسازي و حل مسائل مسيريابي و حل مسائل مكانيابي فكر كنيم.
بنابراين براساس تعريف برونز[3] [1] مكانيابي- مسيريابي را بهصورت مكانيابي-مسيريابي با در نظرگرفتن جنبههاي طراحي تور[4] در نظر ميگيريم و كهاين مطالب همسو با نظر بالاك ريشنان[5] ([2]ص 56) است. كه مسائل مكانيابي- مسيريابي[6] را بهصورت توجّه به تصميمات اساساً استراتژيك مكانيابي امكانات در نظر ميگيرد.
تعاريف ما بهصورت سلسله مراتبي بدين ترتيب هستند كه حل مسأله مكانيابي (مسألهاصلي) هدف ما است اما طي حل اين مسائل، بهصورت همزمان به حل يك مسأله مسيريابي وسيله نقليه (مسأله فرعي) ميپردازيم كهاين موضوع بيانگر يك روند حل يكپارچهاست. به عبارت ديگر ما نميخواهيم روند حل مسألهمان را كه به مكانيابي و مسيريابي يك مسأله ميپردازد و در عين حال رابطة بينابيني آن دو را مورد توجّه قرار نميدهد را طبقهبندي كنيم ويژگي مهم ديگر تعريف ما نياز آن به وجود طراحي تور است به عبارت ديگر وجود توقفهاي متعدد در يك مسير است كهاين پديده موقعي روي ميدهد كه تقاضاهاي مشتري كمتر از ظرفيت يك كاميون پر است البته نويسندگان ديگر تعاريف ديگري را از مساله مكان يابي مسيريابي در نظر ميگيرند يعني بازة وسيعتري از مسائل را در نظر ميگيرند.
1-1 مكانيابي، مسيريابي و مكانيابي- مسيريابي:
خوب است بدانيم كه مكانيابي امكانات و مسيريابي وسايل نقليه با هم مرتبط هستند، موران زانا[7] ([3]-ص 261) نشان داد كه محل كارخانجات، انبارهاي كالا و عرضه محصولات، اغلب تحت تأثير هزينههاي انتقال هستند. (بعضيها معتقدند كه مطالب اين مقاله از اولين مقالات مساله مكان يابي مسيريابي است. و همچنين در موارد بسياري در يك مسأله اكيداً تأكيد ميشود كه پيدا كردن كوتاهترين مسير بجاي مسيريابي وسايل نقليه مورد نظر است. بعلاوه پيرو مطالب عنوان شده در بالا راند[8] ([4]ص 248) بيان كرد كه بسياري از فعالان (تاجران) در اين زمينه از خطرات بهينه سازي فرعي با مكانيابي انبارهاي جدا از هم و مسيريابي وسيله نقليه مطلع هستند به هرحال دانشمندان و تاجران، هردو از اين ارتباط معمولاً چشمپوشي ميكنند وسائل مكانيابي را معمولاً بدون توجّه به مسيريابيهاي زيربنايي حل ميكنند ما در پائين سه دليل ممكن را براي اين امر بيان ميكنيم.
- هنگامي كه مسائل مكانيابي ويژگيهاي مسيريابي را نداشته باشد حالتهاي عملي زيادي ايجاد ميشود كه در اين حالت بوضوح روند مكانيابي-مسيريابي يك مورد مناسب براي حل نميباشد.
- بعضي از اهداف تحقيقي در مورد مكانيابي- مسيريابي بر مبناي ناسازگاري است. يعني مكانيابي را يك استراتژي (تدبير كلي) ميدانند در حالي كه مسيريابي را يك مسأله تاكتيكي (تدبير ساده و كوتاه) ميدانند. مسيرها به كرات (حتي روزانه) ميتوانند محاسبه شوند اما مكانيابيهاي انبارها معمولاً براي يك دورة بسيار طولاني هستند. بنابراين ايدة آنها اين است كه تركيب مكانيابي و مسيريابي در چهارچوب برنامهريزي مشابه در مورد برنامههاي متفاوت غير مقتضي است. و اين منتقدان، نويسندگان را به بررسي اين موضوع كه: استفادهاز مكانيابي-مسيريابي[9] در مسيرهايي كه مجاز به تغيير هستند، ميتوانند هزينههاي اضافي يك طرح را كاهش دهد، هدايت كردند. (براي جزئيات بيشتر بحث در اين زمينه، صلحي و ناجي[10]-[4] را ببينيد.)
- از لحاظ مفهومي، مساله مكان يابي مسيريابي، بسيار مشكلتر از مسأله موقعيتيابي كلاسيك است. برمن[11] ([6]-ص 431) نشان داد كه در مساله مكان يابي مسيريابي مركزيت ارتباط گروههاي اجرايي نقاط تقاضا، امكانات هستند به اين ترتيب حركت از بين همة آنها هنوز ناشناخته است بهصورت متفاوت امكانات و….. در مسائل مكانيابي كلاسيك بايد با فاصلههاي مورد نظر از نقاط تقاضاي منحصر بفرد مكانيابي شوند كه اين امر باعث ميشود كه مسأله ما كنترلپذير بيشتري داشته باشد كه به پيشرفت هستة مساله مكان يابي مسيريابي كمك ميكند.
- بوضوح مسائل موقعيتيابي- مسيريابي با مسأله مكانيابي كلاسيك و مسيريابي وسيله نقليهارتباط دارند. كه هر دو مسألهاخير به عنوان موارد خاصي از مساله مكان يابي مسيريابي بيان ميشوند. و اگر لازم باشد كه همه مشتريان بهصورت مستقيم با يك انبار ارتباط داشته باشند آنگاه مساله مكان يابي مسيريابي به يك مسأله موقعيتيابي استاندارد تبديل ميشود و از طرف ديگر اگر موقعيتهاي انبارها را ثابت نگه داريم مساله مكان يابي مسيريابي ما به مسيريابي وسيله نقليه[12] ساده ميشود.
مسأله مكانيابي- مسيريابي هنگاهي كهاز ديدگاه رياضي بهصورت يك مسأله بهينهسازي تركيبي مدلسازي ميشود از ديدگاه تمريني قسمتي از مديريت پراكندگي (توزيع) را تشكيل ميدهد.
توجّه داريم كهاين يك مسأله NP-hard است كه به مسأله NP-hard ديگر را شامل ميشود (1- موقعيتيابي امكانات و 2- مسيريابي وسيله نقليه).
هنگامي كه تعدادي از انواع مختلف مسأله وجود دارد، ما نميتوانيم تمام فرمولبندي را مجدداً ايجاد كنيم.
به عنوان نمونهاول، براي يك بازنگري بسيار عالي از انواع فرمولبندي به لاپورت[13] [8] ارجاع داده ميشويد. جدول 1-1 مختصري از گوناگوني انواع مساله مكان يابي مسيريابي را كهاز زمان انتشار بازنگري بالا ارائه شدهاست نشان ميدهد.
نوع مساله | مقالات |
مسأله مكانيابي –مسيريابي احتمالي | لاپرته[14] و همكاران[9] |
مسأله مكانيابي –مسيريابي پويا | لاپرته و ديجاكس[15][10] |
ميانه P هميلتوني | برانكو [16]و كوهلهو [17][11] |
مسيريابي ريل ترن | سمت[18][12] |
تخصيص- مسيريابي خودرو [19] | بيزلي[20] و ناسكيمنتو[21][13] |
مسأله مكانيابي –مسيريابي بسيار به بسيار | نگي[22] و سلهي[23][14] |
مكان يابي اقليدسي | قياني[24] و لاپرته[15] |
مسأله مكانيابي –مسيريابي با گامهاي مخلوط | وو [25]و همكاران [16] |
سرمايه گذاري مكان يابي مسير يابي | ليو[26] و لي[27] [17] |
مكان يابي چرخشي دوري دستگاه | لابه[28] و همكاران [18] |
مسأله مكانيابي –مسيريابي بسيار به بسيار | واسنر[29] و زاپلر[30][19] |
سرمايه گذاري مكان يابي مسير يابي چند گانه | آمبروسينو[31] و اسكوتلا[32] [20] |
مسأله مكانيابي –مسيريابي قطعي | آلبردا-سامبلا[33] و همكاران [21] |
VRAP (مساله دوري ميانه) | لابه و همكاران[22] |
مسأله مكانيابي –مسيريابي با هزينه غير خطي | ملو چوسكي [34]و همكاران[23] |
مسأله مكانيابي –مسيريابي مسطح (تك انباره) | اسچوارت[35] و ددلوف[36][24] |
VRAP مقيد | جيونارسون[37][25] |
مسأله مكانيابي –مسيريابي مسطح (چند انباره) | نگي و سلهي[26] |
جدول 1-1 فرمولبندي يا مدلسازي برنامه ريزي خطي براي انواع مساله مكان يابي مسيريابي
در نهايت ميخواهيم خاطرنشان كنيم كه يك روند كلي براي حل مسائل مديريت توزيع (پراكندگي) تنها به مكانيابي-مسيريابي محدود نميشود. در اين زمينه روندهاي كليتر مورد استفاده قرار ميگيرند و مسائل مكانيابي و مسيريابي معطوف به مسائل منطقي ديگر بررسي ميشوند اگر چه مجالي براي پرداختن به جزئيات اين مسائل در اين پايان نامه نيست اما اين مختصر كه ذكر ميشود ممكن است براي خوانندگان علاقهمند به مسائل منطقي تركيبي مفيد واقع شود.
تعدادي از مسائل مكانيابي بهصورت زير ميباشند:
- مسأله صف بندي-مكانيابي (بازنگري شده توسط برمن[38] و كراس[39] [27])
- مسأله مكانيابي-علامت (مَز[40] و خسنبيث[41] در[28])
- مسأله مكانيابي- ظرفيت (ورتر[42] و دنير[43] در[29])
- مسأله مكانيابي- شبكه- طراحي (ملكتو[44] و داسكيني[45] در [30] و لي[46] و همكاران در[31])
- مسألهانبارداري (موجودي كالا)-مكانيابي(داسكيني در [32] و شن[47] در [33] و رزنر[48] در[34])
- مسأله مكانيابي –برنامه زمانبندي (هِنِس[49] و هومافر[50][35])
- مسألهانبارداري(موجودي كالا)- مسيريابي و بازنگري توسط بَيتا[51] در [36] و مين[52] و سهلي[53][37])
- مسأله مسيريابي- برنامه زمانبندي (متلر[54] در [38]-آورباخ[55] و برمن در[39])
- مسأله مسيريابي- بستهبندي(تاركي[56] و انيل[57] در [40]و فِرِر[58] در[41])
2.1. كاربردهاي مكانيابي-مسيريابي
تحقيقات عملي و كاربردي ترجيح ميدهند كه به ساختار نرم افزاري برسند پس مشخص شدن كاربردهاي عملي از مكانيابي- مسيريابي بسيار مهم است جدول 1-2 خلاصهاي از ويژگيهاي اساسي كاربردهاي عملي اين تحقيق است كه مرجعي براي بخشهايي است كه در جزئيات بحث شدهاست و همچنين اندازة بزرگترين حل است كه در اصطلاح تعداد امكانات بالقوه و تعداد مشتريان را نشان ميدهد.
مشتريان | امكانات | كشور/ناحيه | كاربردها | مقالات |
300 | 40 | ايالات پادشاهي | توزيع نوشابه و غذا | واتسون-گاندي[59] و دوهرن[60] (1973)[42] |
50 | 3 | استراليا | توزيع كالاهاي مشتريان | بدنر [61]و استروهمير[62](1973)[43] |
117 | 3 | ايالات متحده | مكانيابي بانك خون | ار [63]و پيرسكالا[64](1973)[44] |
4510 | 42 | دانمارك | توزيع روزنامه | ژاكوبسن[65] و مادسن[66](1980)[45] |
300 | 15 | مالزي | مكانيابي دستگاه لاستيك سازي | نامبير[67] و همكاران(1981)[46] |
318 | 4 | ايالات متحده | توزيع كالاها | پرل[68] و داسكين[69](1984و1985)[47،48] |
موجود نيست | موجود نيست | بلژيك | مكانيابي جعبه هاي پست | لابه[70] و لاپرته[71](1986)[49] |
47 | 10 | مالزي | مكانيابي دستگاه لاستيك سازي | نامبير و همكاران(1989)[50] |
90 | 9 | سويس | توزيع لوبيا | سمت[72] و تايلارد[73](1993)[51] |
260 | 13 | بلژيك | انتخاب ضايعات | كولكار[74](1996)[52] |
331 | 29 | ايالات متحده | مكانيابي تجهيزات نظامي | مورتي[75] و جانگ[76](1999)[53] |
3200 | 200 | سويس | تحويل بسته | برونس[77] و همكاران(2000)[54] |
52 | 9 | ايالات متحده | تخليه دارو | چان[78] و همكاران(2001)[55] |
27 | 4 | هنگ كنگ | تحويل صورتحساب | لين[79] و همكاران(2002)[56] |
50 | 50 | كره | طراحي شبكه هاي نوري | لي[80] و همكاران(2003)[31] |
2042 | 10 | استراليا | تحويل بسته | واسنر[81] و زاپفل[82](2004)[19] |
70 | 6 | فرانسه | طراحي شبكه هاي ارتباطي | بيليونت[83] و همكاران(2005)[57] |
300 | 24 | اروپا | صنعت حمل و نقل | جيونارسون[84]و همكاران [25] |
750 | 22 | لهستان | تحويل بسته | ليسچاك [85]و تريسچ[86][58] |
جدول 1-2: مختصري از كاربردهاي مساله مكان يابي مسيريابي:
ميتوانيم حل مسائلي را كه مكانيابي صدها انبار و هزاران مشتري را در پي داريم، شاهد باشيم اين پايان نامه تعداد زيادي از آنها را نشان ميدهد كه اگر چه بيشتر آنها روي پراكندگي (تجمع) لوازم يا كالاهاي مصرفكنندگان متمركز شدهاست اما كاربردهايي هم در پزشكي، علوم نظامي و ارتباطات دارد تحقيقات عملي اكثراً در كشورهاي زيادي از اروپاي غربي و آمريكاي شمالي ايجاد شدهاند پس خوب است كه بدانيم مساله مكان يابي مسيريابي دركشورهاي پيشرفته مورد استفاده قرار گرفتهاست و بايد توجّه داشته باشيم كه در حدود يك پنجم از مقالات مساله مكان يابي مسيريابي با ساختارهاي نرمافزاري هستند. اين موارد مبني اين واقعيت است كه مساله مكان يابي مسيريابي واقعاً در عمل كاربرد دارد و تنها براي موارد دانشگاهي ساده نميباشد.
[1] TSP(Traveling Salesman Problem)
[2] LRP)Location-Routing Problem)
[3] Bruns
[4] Tour planing
[5] Balakrishnan
[6] LR(Location-Routing)
[7]. Maran Zana
[8]. Rand
[9] Locating Rouring(LR)
[10]. Salhi and Naji
[11]. Berman
[12] Vehicle routing Problem(VRP)
[13]. Laport
[14] Laporte
[15] Dejax
[16] Branco
[17] Coelho
[18] Semet
[19] Vehicle routing-allocation(VRAP)
[20] Beasley
[21] Nascimento
[22] Nagy
[23] Salhi
[24] Ghiani
[25] Wu
[26] Liu
[27] Lee
[28] Labbe
[29] Wasner
[30] Zapfel
[31] Ambrosino
[32] Scutella
[33] Albareda-Sambola
[34] Melechovsky
[35] Schwardt
[36] Dethloff
[37] Gunnarsson
[38]. Berman
[39]. Krass
[40]. Maze
[41]. Khasnabis
[42]. Verter
[43]. Dincer
[44]. Melkote
[45] .Daskin
[46] Lee
[47] .Shen
[48]. Drezner
[49] .Hennes
[50] .Hamacher
[51].Baita
[52].Moin
[53] .Salhi
[54] .Metlers
[55] .Averbakh
[56]. Turkey
[57] .Emel
[58] .Ferer
[59] Watson-Gandy
[60] Dohrn
[61] Bednar
[62] Strohmeier
[63] Or
[64] Pierscalla
[65] Jacobsen
[66] Madsen
[67] Nambiar
[68] Perl
[69] Daskin
[70] Labbe
[71] Laporte
[72] Semet
[73] Taillard
[74] Kulcar
[75] Murty
[76] Djang
[77] Bruns
[78] Chan
[79] Lin
[80] Lee
[81] Wasner
[82] Zapfel
[83] Billinnet
[84] Gunnarsson
[85] Lischak
[86] Triesch
نقد و بررسیها
هنوز بررسیای ثبت نشده است.