صفحه 1:
Sa
TSP & VRP
ae مر
محمد مهدي پایدار
دانشگاه صنعتی نوشیروانی بابل
هب
42
صفحه 2:
Routing Problem
هر مسئله که بدنبال تولید یک تور پا مجموعه ای از تورها بر روی بک شبکه یا زبرشبکه با هدف
بپینه ساختن یک یا چند تابع هدف عی باشد را مسئله مسیر یابی گویند. (یوسفیتز و همکاران
۳4
یک مسئله مسیریابی را می توان بوسیله اجزای زیر تعریف نمود:
Network شبكه *
Demand تقاضا *
* جریان(ناوگان) 60۱
* هزینه 6060
Objectives last =
صفحه 3:
مسأله فروشنده دوره كرد
* مساله فروشنده دوره كرد يكي از بنيادي ترين
مسائل مسيريابي و برنامه ريزي حمل و نقل
ازع مایق یاهع از
( گره ها ) عبور کرده , بطوریکه هر
و بل اس بت ۱۲
اولیه که از آن حرکت را شروع کرده است ,
برگردد.
صفحه 4:
در محدوده ی جغرافیایی فروشنده ی دوره گرد تعدادی شهر وجود دارد
dled بین هر زوج از شهر ها مشخص وعذدی تابت است. قراز است
فروشنده از یکی از شهر ها شروع کند و کلیه ی شهر ها را هر یک را
فقط یکبار » ملاقات کند و در نهایت به نقطه ی شروع برگردد.
۰ مساله فروشنده ی دوره گرد کاربرد های متنوعی دارد. مانند تخلیه
ادواری صندوق های پستی به وسیله ی پستچی.
صفحه 5:
* این مستله اولین بار توسط دو دانشمند به نام های ۱-هامیلتون ایرلندی
و ۲- کیرکمن بریتانیایی مطرح شد.
؟ اولین نمونه شبیه به اين مساله درسال ۱۷۵۹ مطرح شد و به
این صورت بود که یک مهره اسب می بایست روی بردشطرنج
حرکت کند و از هر خانه دقيقا یک بار عبور کند .
مسئله فروشنده دوره گرد جزو مسائل رام نشدنی می باشد و
حل دقیق آن زمان زیادی می برد.
صفحه 6:
© در این مساله میخواهیم دوری همیلتنی با حداقل هزینه را
بیابیم .
در یک گراف جهت دار. یک تور. که به آن دور هامیلتونی
نیز گفته می شود عبارت است از مسیری از یک راس به
خودش که از تمام رئوس دیگر دقیقا یک بار عبور کند.
* نکته: ممکن است گرافی اصلا تور نداشته باشد.
صفحه 7:
* نكته: طول تور بهینه وابسته به انتخاب راس آغازین نیست.
* این مساله را می توان به صورت ریاضی هم شبیه سازی
کرد . به دوری فراگیر (©,6)7 اين ترتيب كه ما در یک
ALF وزن دار با مینیمم مجموع وزنهای یالهای گذرنده می
خواهیم بیابیم .
در حالت عادى بايد كليه ی روش های ممکن بررسی
شود. که در این حالت مرتبه ی زمانی ! 10 خواهد بود.
صفحه 8:
9 به روش ریاضی مساله با يافتن تعداد جایگشت ها وسپس
ارزيابى هر حالت بررسى مى شود .
* تعداد جایگشتها ۲0 است. براى يافتن مينيمم دورها نيز به
حداکثر10! محاسبه احتیاج داریم. ولی اگر 10 را زياد فرض
کنیم تعداد محاسبات بسیار بالا خواهد بود
صفحه 9:
فرض کنیم 7 شهر مفروض است. میخواهیم اژم‌شهو
دلخواه. شروع به حرکت نموده و به هر شهر دیگر فقط
يكبار وارد و فقط يكبار از آن خارج شويم و در انتها. به
شهر مبدء بازگردیم؛ با این شرط که مسافت طی شده.
کمتزین: فسافت باهد: این مسعله ترا تسسله فروچنده
دوزه‌کرد: می‌نامید و ابهجتیزی که بهاین‌شورت: چیه
وجودمی‌آید. "تور" گفته میشود. درصورتی که مسافت
شهرهه تا شهر ۴ با مسافت شهر ع تا شهر «« برای
تمام مقادیر 7,17 برابر باشند. مسئله فروشنده دوره‌گرد
pyle غير ایتضورت آي. را ys g “gga”
می‌نانند.
صفحه 10:
900009
زیر وا نارای کم
رد ۱ اگر یال (/) در مسیر استفاده شده باشد. * در غیر این
برای هرفروشنده 14 تعداد نقاطی است که فروشنده در مسیر خود از بدا تا نقله از آنها می‌گذرد (یعنی
تعداد شهرهای ملاقات شده توسط یک فروشنده از مبدا تا هر ©
] بیشترین تعداد شهرهایی است که یک فروشنده می تواند بازدید کند.
K حداقل تعداد گره هایی است که یک فروشنده باید ملاقات کند
(وع) < ) مائریس هزینه (فاصله) برای هر کمان (,) می باشد
صفحه 11:
cood
Minimize Z=% % CX,
Fl
Subject to :
صفحه 12:
multiple Traveling Salesman
Problem (mTSP)
بكي از شناخته شده ترين مسئلم فروشنده دوره كردء مسئله
تبتاندازدچندین فروشتدویجوره کرد اسیت
اين مسئله را مي توان به | كونه تعريف نهو د: تعيين مجموعع اي
sess مه رکه همکي از بت ,شور به وان
مبدا وه ان شور باز مي گردند و هر شهر فقط
توسط یک فروشنده بازدید مي گردد
* مساله8552: بطوركلي ری ی
مجموعه د تعداد770 شند:
0 شور ما قرار درد شب ره
ید توسط فروشند کات موب بان ترا ی
مياني نامیده مي شوند mST! نکیل دز يافتن
u gir: ۳ همه ان شهرمبدا Jel 9
آن برگردند. همچنین هر نقطه ( ار دیده شود
و هزینه کل دیدن همه شهرها عه شونا ما مازینس فزینه مي Bilas
روي فاصله زمان و غیره تعریف شود.
صفحه 13:
900009
زیر وا نارای کم
رد ۱ اگر یال (/) در مسیر استفاده شده باشد. * در غیر این
برای هرفروشنده 14 تعداد نقاطی است که فروشنده در مسیر خود از بدا تا نقله از آنها می‌گذرد (یعنی
تعداد شهرهای ملاقات شده توسط یک فروشنده از مبدا تا هر ©
] بیشترین تعداد شهرهایی است که یک فروشنده می تواند بازدید کند.
K حداقل تعداد گره هایی است که یک فروشنده باید ملاقات کند
(وع) < ) مائریس هزینه (فاصله) برای هر کمان (,) می باشد
صفحه 14:
۳۳۳۳
Minimize > cy;
اراس
2-1 > وا زا
ats
سرد 5
uj+(L-2)a
وه ووو و جو
حلط كور( -ية) + يط + رفت بلا
Vij
xytay Sl
xy 240.1۲
صفحه 15:
محدودیت هاي (1) 9 )2( تضمین مي کنند که دقیقا »7
فروشنده از مبدا خارج و به آن برگردند. محدودیت هاي (3)
و (4) محدودیت هاي درجه اي هستند. نامعادله هاي (5) و
(6) كران بالا و پایین شهرهايي که بوسیله هر فروشنده مي
تواند بازدید شوند را کنترل مي کنند. این دو نوع محدودیت
مرزي هستند و در ادبیات موضوع7۷15 کاملا جدید مي
باشتد. نامساوي(7) تضمین مي کند که اگر و فقط اگرّ
باشند. بنابراین این محدودیت از ایجاد زیر مسیر بین شهرها
جلوگيري مي کند. تامساوي (8) هر فروشنده را أز بازديد
کردن تنها یک شهر باز مي دارد. لذا مي باشد.
صفحه 16:
* اكز محدوديتي .براق كزان يازين تعداد شهرهاتي كه هر
فروشنده باید بازدید کند وجود نداشته باشد, فقط
کافیست در محدودیت (6) ضریب متغیر را برابر صفر
قرار دهیم. همچنین اگر فروشندگان مجاز به برگشت به
مبدا در صورت بازدید از فقط یک شهر باشند, کافیست
محدودیت(8) حذف شود.
صفحه 17:
multiple departures single
destination multiple traveling
salesman problem (MDmTSP)
مسئله چندین مبداء چندین فروشنده دوره گرد (0۷70/5۳) تعمیم
یافته مسئله یک مبداء چندین فروشنده دوره گرد می باشد به
طوری که بیش از یک مبداء و تعدادی فروشنده در هر مبداء وجود
مسئله چندیین مبداء یک مقصد چندین فروشنده دوره گرد
gt) MDmISP) بار توسط کارا و بکتاس(۲۰۰7) ارائه
گردید.
صفحه 18:
aA
گره ها را بد مجموعه "217 7 دسته بندی می کنیم که 6 گره اول. از مجمرعه 7 . مجموعد
D={L,
میداء می باشند 4
تعداد فروشنده رال در میلاء أ كار ابتدا وجرد دارد که کل تعداد فروشنده ها برابر 19 است
سچیین ]2:...0+ 1,0 +0) < 7 مجموعه گره های مشتری می باشد. ,3 را به عتران یک
متغیر تصمیم صفر-یک تعریف می کنیم که مقدار | می گیرد اگر کمان («ق) در جواب بهینه
باشد. در غیر این صورت صفر است.
براى هر مسائرء:4 تعداد كره هاى ملاقات شده در مسيير مسائر از مبداء كره #مى باشساد.
لحداکتر تعدادگره هایی است که یک فروشنده می
اند ملاقات کند. بنابراین برلى هر 2 < 3
1
داریم رل >
بعلاو». کّ حداقل تعداد گره هایی است که یک فروشنده باید ملاتات کند. اگر 21 ریا
آتگاه م > پلاک
مجموعه (رر6) < ")ماتریس هزینه(فاصلهبرای هر کمان GES) مى باشد
فرض می شود که هر فروشنده مسافرت خرد را از هر گرء ای از مجسرعه (1 شره
همه فروشنده ها مسافرتشان رابه گره مقصد که گره 0 از مجموعه 7 است: به اتمام می رسانند
صفحه 19:
مدل ریاضی 0۷۷۷5
non
Minimize & >, ودره
مزر دز
تعداد کمان های وارد شده به گره مقصد 0 2
me
هر مشتری یک خروجی دارد iev, ¥4=1 2
JeVu 0
هر مشتری یک ورودی دارد ,از بل زود
keV
تعداد فروشنده ها در هر نقطه مبدا =p icD, »
eV,
صفحه 20:
uj- uj + Ly + (L- 2) xj <L-1, i#j, ijeV,
محدودیت بالا یک محدودیت حذف زیر مسیر ها می باشد که از بوجود آمدن هرگونه
مسیرهای فرعی (زیر مسیر) ین نقاط میلنی جلوگیری می کند.مسیر های فرعی, مسیر های
بسته ای هستند که توسط نثاط میانی بدون وجود مبدا یا پایان بوجود می ایند.
Subtour Elimination Constraint (SEC)) (
ieV, با سک وود - ود 2 (2 سل) +زنا
ررعز
ieV, ,2< وود10 -2) + ويد لق y+
keD
و محدودیت بالابه ترتیب حدود بالایی و پایلنی تعداد گره های بازدید شده را عمال
می کند.
صفحه 21:
2 وود + وود >1 ۷۶ ۷,
ke D
محدودیت بالا از ایجاد مسیرهایی فقط با یک نقطه میانی جلوگیری می AS
> 0 > زود
صفحه 22:
مسير يابى وسائل نقليه
Vehicle Routing Problem (VRP)
- مدف عمده این حوزه. کمینه‌سازی هزینه حمل و نقل کالا و مواد بین دو سطح تولیدکننده و
است. به طوری که تقاضای هر مصرف‌کننده بایستی توسط تولیدکنندگان برآورده گردد.
مصرف کنند؛
این حالت با توجه به نوع مسأله مورد بررسی» عواملی همائند طول مسیرء کیفیت مسیر از لحاظ ساختاری
قرار ميكيرئد.
و محيطى؛ ترافيك مسيره ظرفیت وسایل نقیه
به عنوان نمونه. مسيريابى اتوبوسهاى داخل شهرى» جمع‌آوری ضایعات. مسیریابی فروشنه‌های دور‌گرد:
آله مسيريابي و
حالات خاصى از شبكه حم لونقل است كه از آن به عنوا
صفحه 23:
اجزاي مسأله ۷2۵را در شکل معمول و شناخته
شده آن مي توان به مجموعه مشتریان, مجموعه
خودروها (ناوگان حمل و نقل), و شبکه جاده اي
(مسیرها) تقسیم بندي کرد. هر يك از اين اجزا
داراي خصوصياتي هستند که بعنوان فرضیات
مسأله یا پارامترهاي ورودي آن بايستي مورد
توجه قرار گيرند.
صفحه 24:
خصوصیات مشتریان
موقعیت مكاني مشتري: با گره در گراف شبکه جاده اي
نشان داده مي شود. مختصات مان مشتري در
لزوم براي محاسبه فاصله زمان و یا هزینه سفر بین گره ها
اده ميشود .
مقدار تقاضا: معرف مقدار كالابي است که بايد يه مشتري
تخويل دادة نتلود. يا ان محل مشدري جمع أور
زمان سرويس: مدت زماني است كه خودرق 5 مشتري
براي ارائه سرويس به توقف مي کند. زمان سرویس را
مي توان بصورت ابه أنه توقف مي كند: زهان شرو
مجموعه خودروهاي قابل استفاده براي مشتري: زير
مجموعه اي از خودروهاست که امکآن سرویس دهي به
مشتري را دارتد .
بازة زهاني توویین: اوه زمانن كهسوويين دشي ينه
بايستي انجام يذيرت
صفحه 25:
auAW
خصوصیات خودروها
مركز استقرار خودروها : le ol است که خودروها از آنجا
مر ده و در انهابه آن باز مي كردند .اين
ل و
ه هاي مشتریان آست .
۳ خودرو: eee باري خودروها بعنوان يکي از
بارامترهاي ورودى مسا در محدوديت ها مشا مي
ظرفیت خودروها مي تواند ب يا متفاوت باشد .
gists باركيري و تخليه يار خودرو.
هزینه هاي مربوط به بكارگيري خودرو.
مسیرهایی که خودرو امکان پیمودن آنها را دارا است.
محدودیت ها ط به میزان استفاده | درو (حدا
زمان مسافت اسان مب ۱۳9
صفحه 26:
خصوصيات مسيرها (شبكه جاده اي)
1. گره هاي ابتدا و انتهاي مسیر.
2. هزينه (زمان - مسافت) مربوط به سفر در
طول مسير از ابتدا تا انتها.
3 يكسان بودن يا نبودن هزينه سفر رفت و
برگشت مسیرها.
صفحه 27:
هدف مسأله
> حال هدف مسأله 782 حداقل كردن
ودب Bees است. کاه أوفات | به جای حداقل “as
هزينه از معادل هاي آن یعنی کل مسا
Te يا مجموع مان آستفاده ازانها در تام sae
مي شود.
حداقل کردن هزینه (زمان - سفر) کل سیستم.
ایستفاده ار جداقل مداد خودروهای:معکنبزای بجرییین:دهي یب
مشتریان.
ماکزیمم کردن تعداد مشترياني که توسط خودروها به آنها
سرویس داده مي شود.
بالانس سیستم براي آمکان سرویس دهي به مشتریان در بازه
هات زهاني تعین شوه 7
حداقل كردن زيان هاي ناشي از عدم برآورده شدن بر.
هاي مشتريان.
حداقل كردن زيان هاي ناشي از عدم استفاده از كل ظرفيت
خودروها.
صفحه 28:
؟ دسته دیگر از انواع مسایل ۷2 عبارت است از
مساأله مسيريابي دوره اي وسایل نقلیه (۳۷).
* همانند ۷۶۵ کلاسیک, موقعیت تک تک مشتري ها به
همراه تایع تقاضاي قطعي آنها کاملاً مشخص است.
° مسأله 7۷2۵ داراي یک افق برنامه ريزي مشتمل
برروز است, و تواتر بازدید براي هر مشتري
مشخص مي کند که در اين دوره 7-روزه هر چند
وقت یکبار مي بایست بازدید شود.
صفحه 29:
2178 مسأله 1783 را با ترسعد دوره روزهای منفرد به دوره 24روزه تعمیم می‌دهد. آر زیرمجموعد
رئوس (....,..,1) - 1 مطلبق با مشتريان در نظر گرفته شود. در طول پربود؛ هر مشتری 1 > ۸6,۶ > ,۶ > 1
ار ملافات میشود (که تکرار ملاقات نامیده میشود). هر مشتری 21 با :۴ تکرار ملاقاتش مشخص میشود.
إين ملاقاتها بايد از #ركيبهاى روز ملاقات مجموعه مجازپیروی کند برای نمون. اگر یک مشثری باید سه بر
در یک دوره ۶-روزه ملاقات شود. و ترکیب‌های مجاز روزملاقات (۵,۲:۲) و (۶.۴۰۱) باشند بتابراین این
مشتری فقط می‌توند در روزهای مرتبط با یکی از این ترکیبات ملاقات شود.
صفحه 30:
۳ شامل یافتن همزمان مجموعه‌ای از "1 تور برای هر روز از پربود و تخصیص بهترین ترکیب روز - ملاقات
به هر مشتری است بطوریکه همه نیازها تامین شود و همه هزینه های سفر دوره 1-روزه حداقل شود. ۳۷1 همه
محدودیت‌های ۷151 را رعایت میکند. و برخی محدودیت‌های اضافی عبارتند از
© هر مشتری باید یک ترکیب مجاز روز - ملاقات اتتخاب نماید
ا« هو معنتری: ka
زهای مزبوط به ترکیب: روز -ملاقات: ملاقات میشود:
© هر وسیله نقلیه می‌تواند بین دو مشتری در یک روز تردد کند اگر و فقط اگر هر دو مشتری برای ملاقات در
*_ هر مشتری فقط می‌تواند حداکثر یکبار در روز خدمت‌رسانی شود.
صفحه 31:
پاراسترهای ورودی:
3 : مجموعد نقاط تقاضا. نقطه تفاضای شماره ۱ معرف انبار مرکزی" است.
إن ,عثرة| (و)] - 4 : مجموعه يالها يا اتصالات بين نقاط تقاضا. ۷ : تعدادنقاط تقاضاء
: تعداد خودروهاى در دسترس ذر طول دوره برنامه ريزى. © : ظرفيت خودرو د
: متوسط زمان لازم برای طی یال 4>). :۶ هزینه هر واحد مسافت طی شده برای هر خودروء
4 : مقدار تقاضاى مشترى ف : یک زیر مجموعه دلخواه از 0.
: تعداد دفعاتى كه بابد به مشترى 7 در طول دوره برنامه ریزی مراجعه شود. ۰۰ 16 : یک عدد به دلخواه بزرک <1/2.
(۲05 احداقل تعداد خودروهای موردنیاز برای سرویس‌دهی به مجموعه نفاط تقاضا 5
متنبرهای تصمیم گیری :
۱ . آگروسیله قلیه ۷ یال[ را بیماید
!=
+ درغیر اینصورت
صفحه 32:
ve;
ررغ 1,1 < زلا
لواحي
1< زو
ve;
زر
صفحه 33:
تور گنبه -دوکنبه - چهارکنبه
نت قوزا تهب دسگنیوه
©