: ۱ اگر مشتری j به انبار i اختصاص داده شود.
: متغیر کمکی برای محدودیت حذف زیر تور در مسیر k
(۲-۱۸)
(۲-۱۹)
(۲-۲۰)
(۲-۲۱)
(۲-۲۲)
(۲-۲۳)
(۲-۲۴)
(۲-۲۵)
(۲-۲۶)
(۲-۲۷)
تابع هدف کل مسافت طی شده را مینیمم می‌کند. محدودیت (۲-۱۸) بیانگر این است که هر مشتری دقیقا به یک مسیر تعلق دارد و به هر مشتری تنها یک مسیر وارد می‌شود. محدودیت (۲-۱۹) در ارتباط با ظرفیت وسایل نقلیه می‌باشد و بیان می‌دارد که تقاضای مشتریان بر هر مسیر باید کوچکتر یا مساوی با ظرفیت وسیله نقلیه باشد. محدودیت (۲-۲۰) مربوط به حذف زیر‌تورها است که از ایجاد حلقه در مسیر جلوگیری می‌کند. محدودیت (۲-۲۱) تداوم و پیوستگی مسیر را تضمین می‌کنند و بیانگر این‌است که اگر وسیله نقلیه‌ای به گره‌ای وارد می‌شود باید از آن خارج شود. محدودیت (۲-۲۲) بیان می‌دارد پایان هر مسیر از انباری است که مسیر از آنجا شروع شده است. (شروع و پایان هر مسیر به یک انبار است). محدودیت (۲-۲۳) مربوط به ظرفیت انبارها می‌باشد. محدودیت (۲-۲۴) بیانگر این است که هر مشتری می‌تواند به یک انبار تخصیص یابد اگر فقط یک مسیر از آن انبار به مشتری مرتبط باشد محدودیت (۲-۲۵) و (۲-۲۶) متغیرهای صفر و یک که در مدل مورد استفاده قرار گرفته‌اند را مشخص می‌کنند. در محدویت (۲-۲۷) ها متغیر کمکی که یک ارزش مثبت را درمعادله اعلام می‌کنند.
تحقیقات اندکی بر روی مسأله MDVRP صورت گرفته است. سامیچراست در سال۱۹۹۵برای اولین بار مسأله مسیریابی با چند انبار فرمول‌بندی شده است. رئوناد و همکارانش در سال۱۹۹۶با استفاده از الگوریتم جستجوی ممنوعه به حل این مسأله پرداخته‌اند. آنها روش پیشنهادی خود را با آوردن نمونه‌های با روش‌های دیگر مقایسه شدند. هو و همکارانش (۲۰۰۸) الگوریتم ژنتیک ترکیبی برای حل این مسأله در نظر گرفته اند، در مقاله دو نوع الگوریتم ژنتیک معرفی کرده‌اند که در هر کدام از روشی متفاوتی برای بدست آوردن جواب اولیه استفاده کردند و در انتها عملکرد دو الگوریتم را مورد مقایسه قرار دادند. هادجیکونستنتینو و بالاداکی (۱۹۹۸) مسأله مسیریابی وسیله نقلیه چنددپویی دوره‌ای با ارائه روشی ابتکاری شامل چهار سطح حل کرده‌اند. در سطح اول مشخص می‌گردد که کدام دپو باید به کدام مشتری سرویس دهد، در سطح دوم یک مسأله مسیریابی وسایل نقلیه دوره‌ای PVRP برای هر دپو حل می‌شود، در سطح سوم نیز یک مسأله VRP کلاسیک برای هر دپو برای هر روز حل می‌گردد و نهایتا در آخرین سطح یک مسأله کلاسیک فروشنده دوره‌گرد برای هر مسیر حل می‌شود. میرابی و همکارانش (۲۰۱۰)، از سه تکنیک ابتکاری بهینه‌سازی با استفاده از روش شبیه‌سازی بازپخت به حل این مسأله پرداخته‌اند. (صالحی و ساری (۱۹۹۷)، یک روش ابتکاری سه مرحله‌ای برای حل MDVRP ارائه نمود که درمرحله اول یک جواب شدنی ساخته می‌شود و در مرحله دوم و سوم مسیرهای بدست آمده برای هر انبار بهبود داده می‌شود. کوئوردو و همکارانش،(۱۹۹۷) نیز از روش جستجوی ممنوعه برای حل مسأله مسیریابی دوره‌ای وسایل نقلیه با چند انبار استفاده شده است. کرویرت و همکارانش (۲۰۰۷)، مسأله MDVRP را در حالتی در نظر گرفتند که در آن وسایل نقلیه می‌توانند ظرفیت خود را در انبارهای میانی پر کنند. آنها از روش جستجوی ممنوع برای حل این مسأله پیشنهاد کرده‌اند.
۲-۸-۷- مسأله مسیریابی وسایل نقلیه با پنجره زمانی
مسأله مسیریابی وسایل نقلیه با پنجره زمانی[۵۰] (VRPTW) تعمیم یافته‌ای از مسأله CVRP است که در آن سرویس به هر مشتری باید در یک بازه زمانی معین صورت گیرد. این مسأله با توجه به صورت گرفتن سرویس در یک بازه زمانی خاص پیچیدگی‌های زیادی دارد که در صورت اضافه شدن محدودیت طول مسیر و هزینه پنجره زمانی در عین پیچیدگی بسیار بالا به یک مبحث کاربردی در عمل بسیار نزدیک می‌شود. از مثالهای مشخص VRPTW می تواند به تقسیم پول نقد به شعب بانک‌ها، جمع آوری زباله‌ها و ضایعات صنعتی، تقسیم سوخت به جایگاه‌های پخش و سرویس مدارس و… اشاره کرد.
درهر مسأله VRPTW با دو مرحله مواجه هستیم :
مسیریابی
برنامه‌ریزی وسایل نقلیه
مسیریابی مربوط به پیدا کردن یک مسیر ایده‌آلی است که اهداف مدل را تامین کرده و از مشتری تبعیت کند در حالی که برنامه‌ریزی وسایل نقلیه، زمانی را که باید به هر مشتری خدمت داده شود را معین می‌کند. سرویس‌دهی هر مشتری در پنجره زمانی متناسب آن آغاز گردد، و ماشین در موقعیت هر یک از مشتری‌ها به اندازه زمان سرویس‌دهی می‌بایست متوقف گردد(تاث و ویگو،۲۰۰۲).
۲-۸-۷-۱- تقسیم بندی مسأله VRPTW
در این مسأله سرویس به هر مشتری باید در یک بازه زمانی خاص صورت گیرد. هدف حضور به موقع وسایل نقلیه در ایستگاههای تعیین شده است که موجب کاهش قابل توجه زیان‌های از دست دادن مشتریان و افزایش سطح رضایت آنها می‌شود.
VRPTW به سه دسته کلی قابل تقسیم است:
مدل‌های سخت ۲- مدل‌های نرم ۳- مدل‌های مختلط
این مدل‌ها نیز بر اساس پارامترهایی از جمله موارد زیر قابل‌تقسیم هستند:
همسان‌بودن وسایل نقلیه
چندگانه بودن مراکز یا دپوهای مرکزی
سایز و تعداد وسایل نقلیه(ثابت یا متغیر)
محدودیت مسافت طی شده محدود و…
۲-۸-۷ -۱-۱ مدل‌های پنجره‌های زمانی سخت
در پنجره‌های زمانی سخت[۵۱]، وسایل نقلیه ملزم به انجام سرویس در بازه زمانی معین هستند. به عبارت دیگر هر ایستگاه i، یک بازه زمانی سرویس به صورت دارد که ز

نوشته ای دیگر :   برّرسی و تحلیل عوامل فروپاشی جوامع از منظر امام علی (علیه السلام) با ...

دانلود متن کامل این پایان نامه در سایت abisho.ir

مان سرویس‌دهی حتما باید در این بازه انجام شود. مشتری تنها در این بازه دارای مطلوبیت است.
سرویس دهی مجاز نیست زمان مجاز سرویس دهی سرویس دهی مجاز نیست
شکل ۲-۵ :سرویس‌دهی در حالت TW سخت
محدودیت ریاضی مدل TW سخت
:زمان شروع سرویس گره i با وسیله نقلیه v.
:حد پایین پنجره زمانی گره i.
: :حد بالایی پنجره زمانی گره i.
۲-۸-۷-۱-۲ مدل‌های پنجره‌های زمانی نرم
در حالت TWنرم[۵۲]، سرویس‌دهی تا حد معینی خارج از بازه تعیین شده نیز مجاز است به این صورت که برای هر گره یا مشتری علاوه بر یک پنجره زمانی معین یک بازه زمانی سرویس‌دهی دیگر نیز به نام تعریف می‌شودکه بازه در داخل آن قرار می‌گیرد و به سرویس‌هایی که خارج از بازه انجام می‌گیرد جریمه تعلق خواهد گرفت.
سرویس دهی مجاز نیست سرویس دهی با جریمه سرویس دهی بدون جریمه سرویس دهی با جریمه سرویس دهی مجاز نیست
شکل ۲-۶: سرویس دهی در حالت TW نرم
محدودیت‌های ریاضی مدل TW نرم