نشریه تخصصی مهندسی صنایع، دوره 46، شماره 2، مهر ماه 1391، از صفحه 219 تا 233
یک روش فراابتکاري ترکیبی براي مسئله مکان یابی-مسیریابی وسیله نقلیه
ظرفیتدار با پنجرههاي زمانی سخت

علیرضا محمدي شاد 1و پرویز فتاحی*2
دانش آموخته کارشناسی ارشد مهندسی صنایع- دانشگاه بوعلی سینا
دانشیار و مدیر گروه مهندسی صنایع- دانشگاه بوعلی سینا
(تاریخ دریافت 27/1/91، تاریخ دریافت روایت اصلاح شده 20/3/91، تاریخ تصویب 18/4/91 )

چکیده
مسئله مکانیابی – مسیریابی وسیله نقلیه ظرفیتدار1 (CLRP)، یکی از حوزههاي جدید تحقیقاتی در مدیریت پخش است. این موضوع، دو مسئله مشکل مکان یابی تسهیلات و مسیریابی وسایل نقلیه را با یکدیگر ترکیب میکند. هدف از CLRP گشودن مجموعهاي از دپوها ،تخصیص مشتريها به دپوهاي احداث شده و سپس طراحی تورهاي وسیله نقلیه براي کمینه کردن هزینه کل است. محدودیت پنجرههاي زمانی کاربردهاي زیادي در دنیاي واقعی دارد، با این وجود در CLRP اهمیت کمی به آن داده شده است. این مقاله، مسئله مکانیابی- مسیریابی وسیله نقلیه ظرفیتدار را با پنجره هاي زمانی سخت2 (CLRPHTW) در نظر میگیرد. در این مقاله ،ابتدا یک مدل برنامهریزي خطی عدد صحیح مختلط براي CLRPHTW ارائه شده و سپس روشی فراابتکاري بر مبناي الگوریتم جستجوي همسایگی متغیر براي حل این مسئله پیشنهاد میشود. براي ارزیابی عملکرد روش پیشنهادي، این چارچوب با استفاده از یک مجموعه مثال هاي آزمایش مورد بررسی قرار میگیرد.
آزمایش هاي محاسباتی کارآیی روش پیشنهادي را نشان میدهند.

واژه هاي کلیدي: مکانیابی، مسیریابی وسیله نقلیه، پنجره زمانی، روش فرا ابتکاري ،جستجوي همسایگی متغیر، بهینهسازي ترکیب

مقدمه
در دو دهه اخیر رقابت بین شرکتها در راستاي عرضه کالا و خدمات، تبدیل به واقعیتی بزرگ براي پیشرفت آن ها شده است. امروزه شرکتها و کارخانجات نیازمند یکپارچه سازي و منعطف کردن همه فعالیتهاي تولیدي از تهیه مواد اولیه تا تحویل کالاي نهایی به مصرفکننده، در فرایند عرضه و پخش محصولات خود هستند. سیستمهاي توزیع و پشتیبانی بخشی از فرآیند زنجیره عرضه اند، به طوري که جریان مؤثر و کاراي انبارش کالاها، خدمات و اطلاعات وابسته به آنها را از نقطه شروع تا نقطه مصرف به منظور برآورده کردن نیازمندي هاي مشتري برنامه ریزي، اجرا و کنترل می کنند. لجستیک جزئی مهم از مدیریت زنجیره تأمین است.
Email: [email protected] ، 0811-8257410 : نویسنده مسئول : تلفن : 8257411-0811 , فاکس *

مسئله مکانیابی- مسیریابی وسیله نقلیه3 (LRP)، یکی از مسائل مهم و کاربردي در مدیریت پخش و لجستیک است. LRP ترکیبی از دو مسئله مکان یابی تسهیلات و مسیریابی وسیله نقلیه است که به طور همزمان هر دو این مسائل را در نظر می گیرد. در نظر نگرفتن همزمان هر دو مسئله مکانیابی و مسیریابی، سبب افزایش هزینه هاي پشتیبانی زنجیره تأمین خواهد شد. هر دو مسئله مکانیابی تسهیلات و مسیریابی وسیله نقلیه پیچیدگی زمانی از نوع مسائل NP – hard دارند، بنابراین LRP نیز مسئلهاي با پیچیدگی زمانی از نوع مسائل NP – hard است. بنابراین، حل LRP در اندازه بزرگ با استفاده از روشهاي دقیق، سخت و تقریبا ناممکن است [1]. به همین دلیل در بیشتر تحقیقات انجام گرفته براي حل آن، به توسعه روشهاي ابتکاري و فراابتکاري پرداخته شده است.
در مسئله LRP محدودیت ظرفیت شامل دپو یا وسیله نقلیه (نه هر دو باهم) میشود. به تازگی تعدادي از محققان مسئله LRP را با محدودیت ظرفیت، هم در دپو و هم در وسیله نقلیه مورد مطالعه قرار داده اند [2]. این موضوع با عنوان مسئله مکانیابی- مسیریابی وسیله نقلیه ظرفیت دار (CLRP) نام گذاري شده است. پرینس4 و همکارن [2] در تحقیق خود، مدل ریاضی براي CLRP ارائه کرد. آنها CLRP را با استفاده از ترکیب رویکرد جستجوي توافقی تصادفی حریصانه5 (GRASP) و یک فرایند یادگیري و یک مکانیزم مرتبط کردن مسیرها پیشنهاد کردند. همچنین آنها در تحقیقی دیگر از یک الگوریتم ممتیک با مدیریت جمعیت استفاده کردند. در این الگوریتم بهبود جواب ها با استفاده از جستجوهاي محلی و جایگزینی عملگر سنتی جهش با یک تکنیک مدیریت جمعیت پویا بر مبناي فاصله تا جمعیت، انجام می گیرد[3].
بارتو6 و همکاران [4] از یک روش ابتکاري مبتنی بر دسته بندي مشتري ها براي حل CLRP استفاده کردند. آنها از چند روش سلسله مراتبی و غیر سلسله مراتبی براي دستهبندي استفاده کردند. پرینز و همکاران [5] از تکنیک سستسازي لاگرانژي و جستجوي ممنوعه دانه اي براي توسعه رویکردي دو فازي براي حل CLRP استفاده کردند. این الگوریتم به طور متناوب بین یک فاز مکانیابی و یک فاز مسیریابی، اطلاعات را جابه جا می کند. در فاز اول مسیرها و مشتري هاي آنها بهصورت یک ابرمشتري ترکیب می شوند تا مسئله به یک مسئله مکانیابی تسهیلات تبدیل شود. آزادسازي لاگرانژي در محدودیت هاي تخصیص براي حل مسئله مکانیابی تسهیلات به دست آمده مورد استفاده قرار میگیرد. در فاز دوم جستجوي ممنوعه دانهاي براي توسعه مسیریابی چند دپویی به دست آمده از فاز اول به کار می رود.
ماریناکیس و ماریناکی7 [6] از روشی ترکیبی مبتنی بر الگوریتم بهینه سازي گروه ذرات براي حل مسئله استفاده کردند. دوهامل8 [7] الگوریتم (GRASP+ELS)9 که ترکیبی از الگوریتم جستجوي تصادفی حریصانه توافقی با روش جستجوي محلی تکاملی براي حل مسئله CLRP استفاده کردند. یو10 و همکاران [8] از الگوریتم شبیه سازي تبرید ابتکاري براي حل CLRP استفاده کردهاند. آنها براي بهبود عملکرد الگوریتم شبیهسازي تبرید از سه ساختار همسایگی استفاده کردند. آنها ادعا کردند که استفاده از این ساختار سبب بهبود در الگوریتم شبیه سازي تبرید براي حل CLRP م یشود. آنها براي بهبود عملکرد الگوریتم شبیه-سازي تبرید از سه ساختار همسایگی با انتخاب احتمالی استفاده کردند. به تازگی نگیون11 و همکاران [9] در تحقیق خود از الگوریتم جستجوي تصادفی حریصانه توافقی با استفاده از فرایند یادگیري براي حل CLRP در دو سطح استفاده کردند. آنها همچنین در تحقیق دیگر خود، همین مسئله را با استفاده از روشی مبتنی بر الگوریتم جستجوي همسایگی تکرارشونده حل کردند و جواب هاي تحقیق پیشین خود را بهبود دادند[10].
با وجود کاربرد فراوان محدودیت پنجره زمانی در مسائل دنیاي واقعی ،در CLRP اهمیت کمی به آن داده شده است. جبل عاملی و غفاري نسب [11] مسئله مکان یابی -مسیریابی وسیله نقلیه را در هر دو حالت پنجره هاي زمانی نرم و سخت مدل سازي کردند و با ارائه مثالی کوچک اعتبار مدل خود را به نمایش گذاردند. نیک بخش و ذگردي مسئله مکانیابی-مسیریابی وسیله نقلیه دو سطحی با محدودیت پنجرههاي زمانی نرم را مورد مطالعه قرار دادند. نویسندگان این تحقیق براي مسئله مدل برنامهریزي ریاضی چهار – شاخصه و روشی ابتکاري براي حل ارائه کردند. همچنین آنها با استفاده از آزادسازي لاگرانژي کران پایینی براي مسئله به دست آوردند و جواب هاي حاصل از الگوریتم ابتکاري خود را با آن مقایسه کردند.
هدف اصلی در این تحقیق، افزودن محدودیت پنجره هاي زمانی به CLRP براي کاربردي تر کردن مسئله است. محدودیت پنجر ه هاي زمانی، از مسئله مسیریابی وسیله نقلیه با محدودیت پنجره هاي زمانی 12(VRPTW) گرفته شده است. این موضوع با عنوان مسئله مکان یابی -مسیریابی وسیله نقلیه ظرفیتدار با محدودیت پنجرههاي زمانی سخت (CLRPHTW) نام گذاري می شود. در این تحقیق ابتدا به مدلسازي ریاضی مسئله پرداخته میشود. سپس با توجه به پیچیدگی حل مسئله و ناتوانی روشهاي حل دقیق در حل مسئله با اندازههاي متوسط و بزرگ در زمانی معقول ،الگوریتمی فراابتکاري بر مبناي روش جستجوي همسایگی متغیر براي حل آن ارائه می شود. نوآوري تحقیق حاضر و تفاوت آن با سایر تحقیق ها، افزودن مدت زمان انتظار به مدل ریاضی ارائه شده توسط جبل عاملی و غفاري نسب [11] براي مسئله مکانیابی-مسیریابی وسیله نقلیه ظرفیت دار با محدودیت پنجرههاي زمانی سخت و طراحی الگوریتم فراابتکاري براي حل این مسئله است.
ادامه مقاله به صورت ذیل سازماندهی شده است: در بخش دوم، به بیان تعریفی از مسئله و ارائه مدل ریاضی آن پرداخته میشود. در بخش بعد، الگوریتم پیشنهادي به همراه جزئیات آن ارائه می شود. در بخش چهارم، نتایج آزمایشات محاسباتی آورده می شود و در نهایت در بخش آخر در مورد الگوریتم پیشنهادي و ارائه پیشنهاد براي آینده بحث می شود.

2. تعریف مسئله و بیان مدل ریاضی آن
در مسئله مکانیابی -مسیریابی وسیله نقلیه ظرفیت دار با محدودیت پنجرههاي زمانی سخت ،مجموعه اي از مشتري ها و مجموعه اي از نقاط کاندید احداث دپو براي عرضه محصول، در سطحی جغرافیایی با مختصات مکانی معلوم وجود دارند. تقاضاي مشتري ها و ظرفیت دپوها از ابتدا مشخص هستند. وسایل حمل و نقل کالا همجنس با ظرفیتی یکسان هستند. هر مشتري براي دریافت کالاي مورد تقاضاي خود فقط به یک دپو و یک وسیله نقلیه متعلق به آن دپو تخصیص داده می شود که در اینجا باید محدودیت هاي ظرفیت دپو و همچنین ظرفیت وسیله نقلیه مد نظر قرار گیرد. هر وسیله نقلیه نیز تور خود را از دپو آغاز و پس از سرویسدهی به مشتري هاي تخصیص یافته به خود، دوباره به همان دپو باز می شود. هر مشتري یک بازه زمانی از قبل مشخص شده [e , l ] دارد. در اینجا e زودترین زمان شروع دریافت سرویس و l نیز دیرترین زمان شروع دریافت سرویس از وسیله نقلیه است. در حالت پنجرههاي زمانی سخت مشتري سرویس را فقط در بازه زمانی تعریف شده توسط خود دریافت می کند و اگر وسیله نقلیه زودتر از شروع بازه به محل مشتري برسد، باید در آنجا صبر کند تا پنجره زمانی گشوده شود. هدف از این موضوع، کمینه کردن هزینههاي مربوطه و تعیین مکان هاي مناسب احداث دپو و تعیین و برنامهریزي تورهاي وسایل نقلیه هر دپو است؛ به طوري که تقاضاي همه مشتري ها پاسخ داده شود.
براي بیان مدلسازي برنامه ریزي عدد صحیح مختلط13 (MILP) مسئله مورد تحقیق، ابتدا نمادها و پارامترهاي به کار رفته در مدل ریاضی تشریح می شوند، سپس با افزودن ملاحظات مربوط به محدودیت پنجرههاي ظرفیت دار ارائه شده توسط پرینس و همکاران [5]، مسئله مورد تحقیق مدل سازي می شود.
مجموعه ها:
مجموعه نقاط کاندید احداث دپو مجموعه مشتري ها مجموعه کل نقاط (گره ها) که ∪= مجموعه وسایل نقلیه پارامترهاي مدل:
تقاضاي مشتري .
78944050548

هزینه بازگشایی دپوي کاندید هزینه ثابت استفاده از یک وسیله نقلیه در دپوي کاندید
هزینه طی مسافت از گره به گره
مدت زمان طی مسیر از گره به گره ظرفیت دپوي کاندید ظرفیت هر وسیله نقلیه
حداکثر مدت زمانی طی یک تور زودترین زمان شروع سرویس به گره دیرترین زمان شروع سرویس به گره مدت زمان ارائه سرویس به مشتري
M عددي بزرگ متغیرهاي تصمیم:
زمان رسیدن وسیله نقلیه به گره میزان انتظار در گره
اگر دپوي کاندید گشوده شود، یک و در غیر این صورت، صفر
اگر تقاضاي مشتري j توسط دپوي تأمین شود، یک و در غیر این صورت، صفر
2417072296645

اگر وسیله نقلیه از گره به طور مستقیم به گره برود یک و در غیر این صورت، صفر

با توجه به موارد ذکر شده در بالا، مدل برنامه ریزي عدد صحیح مختلط CLRPHTW به صورت ذیل ارایه می شود:
زمانی به مدل مسئله مکان یابی-مسیریابی وسیله نقلیه

Minimize ∑ ∈ + ∑ ∈ ∑ ∈ ∑ ∈ + ∑ ∈ ∑ ∈ ∑ ∈Subject to:
∑ ∈ ∑ ∈ = 1 , ∀ ∈
-355590

∑ ∈ ∑ ∈ ≤ , ∀∈ ,∀ ∈ (4)
, ∀∈
, ∀⊆,∈
, ∀ ∈,∈
, ∀∈
, ∀ ∈,∈,∈
, ∀ ∈,∈,∈
, ∀ ∈,∈
× , ∀ ∈,∈,∈
,∀ ∈,∈
, ∀ ∈
, ∀ ∈
∈ {0,1} , ∀ ∈ ,∈ (17)
∈ {0,1} , ∀ ∈ (18)
∈ {0,1} , ∀ ∈ ,∈,∈ (19)
, ∀ ∈
در این مدل، تابع هدف (1) مجموع هزینههاي ثابت دپو و هزینههاي مسیریابی که شامل هزینه ثابت وسیله نقلیه و هزینه مسافت طی شده است را کمینه می کند.
عبارت محدودیت دوم تضمین می کند که هر مشتري فقط و فقط به یک مسیر متعلق است و در تور فقط یک گره پیش نیاز دارد.
محدودیت (3) و (4) بهترتیب محدودیت هاي ظرفیت مربوط به وسیله نقلیه و دپو هستند. محدودیت حداکثر زمان طی مسافت در یک تور توسط عبارت (5) نشان داده شده است. محدودیت (6) مربوط به حذف زیرتورها است.
محدودیت (7) تضمین کننده پیوستگی تورها است و محدودیت (8) تضمین می کند که هر وسیله نقلیه از هر دپویی که حرکت خود را آغاز می کند بار دیگر باید به همان دپو بازگردد. عبارت (9) بیان می دارد که یک مشتري به یک دپو تخصیص می یابد، اگر توري باشد که این دو را به هم مرتبط کند.
عبارت (10) رابطه میان زمان رسیدن یک مشتري و رسیدن به مشتري بعدي اش را نشان می دهد.
محدودیت هاي (11) و (12) تضمین میکنند که پنجره زمانی مشتريها و دپوها نقض نشود. محدودیتهاي (13) و (14) شرایط اولیه متغیرهاي زمان انتظار و زمان رسیدن را براي دپوها مشخص میکند. محدودیتهاي (15) و (16) بیانگر مثبت بودن متغیرهاي تصمیم زمان رسیدن و زمان انتظار است. سرانجام محدودیت هاي (17)، (18) و (19) بیانگر دودویی بودن متغیرهاي تصمیم دیگر است. پس از تعریف کامل مسئله و مدل سازي ریاضی آن، در ادامه به ارائه روشی فراابتکاري براي حل مسئله می پردازیم.

3. روش حل پیشنهادي
رویکرد پیشنهادي براي حل CLRPHTW روشی بر مبناي الگوریتم فراابتکاري جستجوي همسایگی متغیر است. در الگوریتم پیشنهادي ابتدا با استفاده از الگوریتم تعمیم یافته14 PFIH جواب اولیه براي شروع الگوریتم پیشنهادي به دست می آید. جواب اولیه (S ) به عنوان جواب فعلی الگوریتم قرار می گیرد. حال الگوریتم اصلی که بر مبناي الگوریتم جستجوي همسایگی متغیر است، آغاز می شود. در چارچوب الگوریتم جستجوي همسایگی متغیر ،براي جستجوي بهتر فضاي جواب از الگوریتم شبیهسازي تبرید استفاده می شود. در ادامه، اجزاي روش جدید به تفصیل تشریح می شوند و در پایان، ساختار الگوریتم پیشنهادي ارائه می شود.

3,1. الگوریتم جستجوي همسایگی متغیر
الگوریتم جستجوي همسایگی متغیر15 (VNS) که شبه کد آن در شکل 1 آمده است، نخستین بار توسط ملادنوویک و هانسن16 [13] در سال 1997 مطرح شد. ایده اصلی این الگوریتم تعویض سیستماتیک ساختار همسایگی در طول جستجو براي جلوگیري از افتادن در بهینه محلی است. سادگی در پیادهسازي و کیفیت جوابهاي حاصل از الگوریتم VNS ،این الگوریتم را به سرعت تبدیل به روشی خوب براي حل مسائل بهینهسازي کرد. الگوریتم VNS با تولید جواب اولیه و تعریف ساختارهاي همسایگی و استفاده از روشی براي جستجوي همسایگی کار خود را آغاز می کند. ساختارهاي همسایگی الگوریتم { , … ,2,1} = , هستند، که ساختار همسایگی ام است. پس از تعیین ساختارهاي همسایگی ممکن ترتیب آنها تعیین می شود. دو نکته مهم در اینجا، انتخاب ساختارهاي همسایگی مناسب و تعیین ترتیبی مناسب (به عنوان مثال ترتیب بر مبناي بزرگ شدن ساختارهاي همسایگی) است. تولید جواب اولیه با کیفیت، تعریف ساختارهاي همسایگی و تعیین ترتیب آن-ها و استفاده از روش مناسب براي جستجوي محلی ،عوامل تعیینکننده در کیفیت جوابهاي حاصل از الگوریتم است. الگوریتم با استفاده از جواب اولیه تولید شده (S ) کار خود را آغاز می کند و تا زمانی که معیار خاتمه برقرار شود، حلقه اصلی الگوریتم تکرار می شود. حلقه اصلی الگوریتم VNS شامل دو فاز اصلی تکاندهنده و جستجوي محلی است.
در فاز تکاندهنده، الگوریتم از جواب فعلی با استفاده از امین ساختار همسایگی به جواب همسایه ( ) حرکت م یکند. در فاز جستجوي محلی نیز به روي جواب با استفاده از روش هاي جستجوي محلی، جستجو انجام م یگیرد تا به بهینه محلی ∗ برسد. حال در بخش حرکت یا عدم حرکت اگر بهینه محلی بهدست آمده از جواب فعلی بهتر بود، جایگزین آن می شود و جستجو به برمی گردد، در غیر این صورت از ساختار همسایگی بعد ( ) براي ادامه جستجو استفاده می شود. این جستجو تا زمانی که ≤ باشد، ادامه م ییابد. در شکل (1)، شبه کد الگوریتم جستجوي همسایگی متغیر به نمایش گذارده میشود [14].
Input: a set of neighborhood structures ,= 1,2, . . , ,
S=generate initial solution ( );
Repeat
= 1;
While ( ≤)
{
′=Shaking ( , ) ′∗=Local search ( ′)
if ( ′∗) <( )
←′∗
= 1 ; else
=+ 1;
}
Until stopping condition are met;
Output: The best solution;

شکل 1: شبهکد الگوریتم جستجوي همسایگی متغیر

3,2. الگوریتم شبیهسازي تبرید
الگوریتم شبیهسازي تبرید17(SA) روشی ابتکاري بر مبناي جستجوي محلی است. این الگوریتم قادر است از گیر افتادن در بهینه محلی با قبول جواب هاي بدتر، با احتمالی کم، جلوگیري کند. کیفیت جوابهاي حاصل از الگوریتم شبیهسازي تبرید موجب شده تا در حل مسائل بهینهسازي ترکیبی پیچیده در حوزههاي مختلف مسائل دنیاي واقعی مورد استفاده قرار گیرد. شبیهسازي تبرید توسط کرك پاتریک18 و همکاران [15] عمومیت پیدا کرد. مفهوم اصلی شبیهسازي تبرید از فرایند تبرید فلزات در صنعت متالورژي گرفته شده است.
فرایند بهینهسازي در شبیه سازي تبرید، جستجو براي یک جواب (نزدیک به) کمینه سراسري است. الگوریتم از یک جواب تصادفی به عنوان جواب اولیه حرکت خود را آغاز میکند و دماي سیستم برابر دماي اولیه قرار می گیرد ( = ). در هر تکرار یک جواب همسایه جواب فعلی بهدست می آید. مقدار تابع هدف جواب جدید با جواب فعلی مقایسه می شود. اگر جواب بهتر بود، جایگزین جواب فعلی می شود و اگر جواب بدتر بود با یک احتمال که از تابع بالتزمن ( ⁄∆−) به دست می آید، جایگزین جواب فعلی می شود. این مکانیزم منجر به این می شود که الگوریتم در بهینه محلی گیر نیافتد. در این رابطه

برابر میزان اختلاف مقدار تابع هدف جواب فعلی با جواب جدید است ،K ضریب بالتزمن است که از قبل تعیین می شود و T نیز دماي فعلی است. فرایند جستجوي همسایگی ادامه می یابد تا زمانی که تعداد تکرارها به مقداري از پیش تعیینشده برسد. پس از اینکه تعداد تکرارها به اندازه مقداري معین و از پیش تعیین شده گشت، دماي سیستم کاهش می یابد. این فرایند تا زمانی ادامه پیدا می کند که الگوریتم به معیار خاتمه برسد. شبه کد این الگوریتم در شکل 2 نمایش داده شده است.

3,3. تولید جواب اولیه
براي شروع کار الگوریتم نیاز به جواب اولیه مناسب و با کیفیت است ،به همین دلیل براي تولید جواب اولیه براي الگوریتم پیشنهادي از ساختار تعمیمیافته الگوریتم PFIH براي VRPTW در تحقیق سولومون19 [16] استفاده می شود. الگوریتم PFIH از الگوریتمهاي ابتکاري و متداول کسب جواب اولیه مناسب و شدنی براي حل مسئله مسیریابی وسیله نقلیه با محدودیت پنجرههاي زمانی است. این الگوریتم با توجه به محدودیتهاي پنجره زمانی و محدودیت ظرفیت وسیله نقلیه جوابی شدنی و مناسب ارائه می کند. گام هاي تولید جواب اولیه براي مسئله مورد تحقیق به شرح ذیل است:

Initialize parameters;
S=generate initial solution ( );
=;
While (<)
{
Until (≤_)
{
Generate solution ′ in the neighborhood of if ( ′) < ( ) ← ′ else
∆= ( ′) − ( ) ; = ( ) ; if ( < exp (− ∆⁄ ∗ ))
←′
}
=× ;
}
Return the best solution found;
شکل 2: شبهکد الگوریتم شبیه سازي تبرید

گام 1: ابتدا همه مشتري ها در لیست مشتري هاي تخصیص داده نشده (UC) قرار می گیرند.
گام 2: هر مشتري داخل لیست UC به نزدیک ترین دپو تخصیص می یابد. حال دپویی که بیشترین مشتري هاي نزدیک به خود را دارد ،به عنوان دپوي کاندید احداث گشوده می شود.

گام 3: از لیست UC با توجه به ترتیب نزدیکی فاصله به دپوي گشوده شده مشتري ها به دپوي مورد نظر تخصیص می یابند تا زمانیکه محدودیت ظرفیت دپو نقض نگردد.
گام 4: پس از تخصیص، این مشتري ها از لیست UC حذف می شوند و دپو نیز از لیست دپوهاي کاندید حذف می شود.
گام 5: اگر هنوز مشتري اي در لیست مشتري هاي تخصیص نداده شده بود، به گام 2 باز می گردیم، در غیر این صورت به گام آخر می رویم.
گام 6: در این گام براي هر دپوي احداث شده با توجه به مشتري هاي تخصیصی به آن از الگوریتم PFIH براي حل مسئله مسیریابی وسیله نقلیه با پنجرههاي زمانی استفاده می شود.
در 5گام آغازین روش ذکرشده، از روش تولید جواب اولیه براي مسئله مکانیابی-مسیریابی وسیله نقلیه ارائه شده توسط یو و همکاران [8] استفاده میشود. جواب تولید شده از الگوریتم فوق به عنوان جواب اولیه براي شروع الگوریتم پیشنهادي به امید رسیدن به جواب هایی با کیفیت در زمانی معقول مورد استفاده قرار می گیرد.

3,4. نمایش جواب و محاسبه تابع هزینه
براي نوشتن برنامه کامپیوتري الگوریتم، ابتدا به نحوه ساختار نمایش جوابها براي مسئله نیاز است. ساختار نمایش جواب، مسئله را به صورتی قابل فهم براي کامپیوتر تبدیل می کند. این ساختار باید بهگونهاي باشد که همه اجزاي یک جواب به خوبی قابل مشاهده و بررسی باشد. طراحی ساختار مناسب نقش زیادي در عملکرد یک الگوریتم دارد. ساختار نمایش جواب مورد استفاده براي CLRPHTW همانند ساختار معمول LRP است. اگر تعداد n مشتري ،m مکان کاندید احداث دپو و k وسیله نقلیه داشته باشیم، آنگاه نمایش جواب شامل آرایه اي با ترتیبی از n مشتري که با اعداد , . … ,2,1 مشخص می شود، و m دپو که با اعداد +n + 1, n + 2, …, n m نمایش داده میشود و 2-k درایه صفر است. در شکل (3) مسئله کوچکی از CLRP با 10 مشتري و 3 مکان احداث کاندید دپو را نشان می دهد.

در این شکل دو دپوي 11 و 13 گشوده شده اند. در این نمایش جواب زمانی یک دپو باز است که بین این دپو تا دپوي دیگر در نمایش جواب حداقل یک مشتري باشد. همان طور که از این شکل بر می آید، مشتري هاي 3، 5، 7، 2 و 1 به دپوي 11 تخصیص داده شده اند و سایر مشتري ها از دپوي شماره 13 سرویس دریافت می کنند.
همچنین در این نمایش جواب هر دو دپو داراي دو تور وسیله نقلیه هستند. به طور مثال در تور اول از دپوي 11، حرکت از دپو 11 آغاز می شود و پس از سرویس دادن به مشتري هاي 3، 5 و 7 ، به ترتیب، دوباره به دپوي 11 باز می گردد.
نکته مهم، نقض محدودیت هاي ظرفیت دپو، ظرفیت وسیله نقلیه و پنجرههاي زمانی است که ممکن است در این نمایش جواب رخ دهد. بدین منظور، در این مقاله از استراتژي جریمه گذاري براي برخورد با جوابهاي نشدنی استفاده میشود. در این استراتژي میزان جریمه اي متناسب با میزان نقض محدودیتها به تابع هدف افزوده میشود. در این مقاله پارامترهاي P_vehicle، P_depot و P_tw به ترتیب برابر میزان جریمه به ازاي نقض هر واحد محدودیت ظرفیت وسیله نقلیه، ظرفیت دپو و پنجرههاي زمانی تعریف میشوند.

3,5. ساختارهاي همسایگی
در الگوریتم پیشنهادي از چهار ساختار همسایگی استفاده می شود. ساختارهاي استفاده شده در این تحقیق از ساختارهاي همسایگی متداول براي حل مسئله مسیریابی وسیله نقلیه با پنجرههاي زمانی هستند. این چهار ساختار همسایگی شامل عملگر حرکتی relocation، عملگر حرکتی Swap ، عملگر حرکتی Or-opt و عملگر حرکتی ∗opt − 2 هستند. ترتیب ساختارهاي همسایگی استفاده شده در الگوریتم پیشنهادي به ترتیب ذکرشده است.

11 3 5 7 0 2 1 12 13 4 8 6 0 10 9 0 0
شکل 3: نماش جواب استفاده شده براي الگوریتم پیشنهادي
در عملگر حرکتی relocation، ابتدا دو عنصر i و j در طول آرایه نمایش جواب به طور تصادفی انتخاب می-شوند، سپس عنصر i از جاي خود برداشته و در مکان پس از عنصر j در آرایه نمایش جواب قرار می گیرد. در عملگر حرکتی Swap پس از انتخاب دو عنصر جاي آن ها در نمایش جواب با یکدیگر عوض میشود. عملگر حرکتی Or-opt یک تور را برداشت سه مشتري متوالی و قرار دادن این زنجیره در مکانی دیگر از تور بهبود میدهد.
عملگر حرکتی ∗opt − 2 دو تور از نمایش جواب به طور تصادفی انتخاب میکند، سپس هر تور را از مکانی به طور تصادفی در طول آن به دو قسمت تقسیم میکند. حال جاي مشتري هاي قسمتهاي اول و دوم از تور اول را به -ترتیب با قسمتهاي دوم و اول از تور دوم عوض در نمایش جواب فعلی جابه جا میکند.

3,6. الگوریتم پیشنهادي براي حل CLRPHTW
پس از تشریح اجزاي اصلی، در این به بخش به معرفی کامل الگوریتم پیشنهاد شده در این تحقیق براي حل مسئله مکانیابی -مسیریابی وسیله نقلیه با محدودیت پنجرههاي زمانی سخت می پردازیم. در ابتدا الگوریتم کار خود را با به دست آوردن جواب اولیه آغاز می کند. جواب اولیه به عنوان جواب فعلی سیستم قرار می گیرد ( = ). براي حل مسئله از چهار ساختار همسایگی استفاده می شود. شروع الگوریتم با ساختار همسایگی اول ،یعنی 1 =، است. ابتدا در فاز تکاندهنده (Shaking) بر اساس ساختار همسایگی ام الگوریتم از جواب فعلی به جواب همسایه حرکت می کند. حال در فاز جستجوي همسایگی به روي جواب همسایگی جستجوي همسایگی صورت م یگیرد تا بهینه محلی ∗ به دست آید. جستجوي همسایگی در الگوریتم پیشنهادي با استفاده از روش شبیهسازي تبرید با استفاده از ساختار همسایگی ام به عنوان عملگر حرکتی براي حرکت به نقاط همسایه صورت می گیرد. در اینجا طول زنجیره مارکوف براي جستجوي همسایگی با یک ساختار همسایگی مشخص برابر تعداد تکرار متوالی بدون بهبود در تابع هدف در نظر گرفته میشود. در بخش حرکت یا عدم حرکت، اگر مقدار تابع هدف بهینه محلی ∗ بهتر از باشد ،∗ = و 1 = م یشود، در غیر این صورت
از ساختار همسایگی بعدي استفاده می شود+ = )(1. حلقه الگوریتم جستجوي همسایگی متغیر در یک دما تا زمانی که ≤ باشد ادامه می یابد، در اینجا 4 = است، و پس از آن دما با استفاده از قانون کاهش هندسی ( × = ) بهروزرسانی می شود. الگوریتم پیشنهادي تا رسیدن به دماي پایانی ادامه م ییابد. فلوچارت الگوریتم پیشنهادي



قیمت: تومان


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