الگوریتم ژنتیک و بهینه سازی


Widget not in any sidebars

2-2-1. تاریخچه VRP
برای اولین بار مسأله مسیریابی وسایل حمل و نقل توسط دانتزیگ و رامسر[7] بصورت فرمول ریاضی ارائه شد و برای حل آن از روش های دقیق سود جسته شد، در سال 1954 اولین مقاله در مورد موضوع VRP توسط دانتزیگ، فالکرسون [8] به ثبت رسید، این مقاله یک مسأله نسبتاٌ بزرگ TSP را مورد مطالعه قرار داده و برای مدل VRP ارایه شده یک روش حل صفر و یک پیشنهاد داد شد که توسط تعداد زیادی از مقالات پیرامون TSP مورد پیروی قرار گرفت.
در سال 1964 رایت و کلارک[9] مقالهای ارایه دادند که مسأله TSP را با بیش از یک وسیله نقلیه در فرمولبندی مسأله به کار گرفتند، در نتیجه این مطالعه را میتوان به عنوان اولین مقاله در ادبیات VRP آنگونه که شناخته میشود، به حساب آورد. اولین مقالهایی که در خود عبارت (مسیریابی وسایل نقلیه) را یدک می کشد منسوب به گلدن، مگناتی و انگاین [10] می باشد. نسخههای دیگر VRP در اوایل دهه ی 1970 پدیدار شدند که به عنوان نمونه میتوان به آثاری که در مقالات جندرئو و همکاران و اوسوالد و همکاران و غیره [13،11،12] آورده شده است اشاره کرد.
در طی سالهای دهی 1990 تحقیقات در مورد VRP شتاب گرفت. عواملی چون قابلیت و در دسترس بودن ریز محاسبه گره‌ها، این توانایی را در اختیار محققین قرار داد که الگوریتم‌های جستجوی بیشتری را ارایه و توسعه دهند. طی این دوره متدهای فرا ابتکاری جهت حل کردن اینگونه مسائل و همینطور مسائل بهینه سازی پیچیده ی دیگر، به عنوان الگوریتمهای جستجو معرفی شدند. جندرئو و همکاران [14]، کاربردهای الگوریتمهای فرا ابتکاری همچون شبیه سازی تبرید، الگوریتم ژنتیک، کلونی مورچگان و غیره را در حل مسائل مسیریابی وسایل نقلیه مورد مطالعه قرار دادند. از دیگر تحقیقات انجام شده در این زمینه می توان به آثار واسرمن، عثمان و کلی ، عثمان و لاپورته، دوریگو، مونیزو و کلونی، آرتس و لنسترا ، گلوور و لاگونا [15] وعثمان و واسمن [16] اشاره نمود.
2-2-2. مشخصات کلی مساله مسیریابی وسایل حمل و نقل
– مشخصات کلی مشتریان:
نقاط موجود در شبکه مسیر که مکان مشتری در آن قرار دارد.
مقدار کالا (تقاضا) ، که می تواند چند نوع باشد ، و باید به مشتری تحویل داده شود و یا از آن تحویل گرفته شود.
دورههای روز (پنجره های زمانی) که در آنها میتوان به مشتری خدمتدهی کرد( برای مثال، به علت محدودیتهای ترافیکی و یا به این علت که در زمانهای خاصی مکان مشتری باز است).
زمان مورد نیاز برای تحویل گرفتن و یا تحویل دادن کالا به مشتری(به ترتیب، زمانهای بارگیری یا باردهی) ، که میتواند به نوع وسیله حمل و نقل مربوط باشد؛
زیرمجموعهایی از وسایل ممکن که میتوانند برای خدمتدهی به هر مشتری استفاده شوند (برای مثال به علت محدودیتهای دستیابی یا ملزومات بارگیری و باردهی).
بعضی از مواقع، ممکن است که به طور کامل تقاضای هر مشتری برآورده نشود. در این مواقع، می‌توان مقداری که باید تحویل داده یا گرفته شود، را کاهش داد، و یا اینکه تقاضای زیرمجموعهایی از مشتریان را بی‌پاسخ گذاشت. برای رویارویی با این مسأله، اولویت‌ها و یا جریمه‌های متفاوتی به کمبود‌های کلی و جزئی هر مشتری، تخصیص می‌یابد.
شروع و پایان مسیرهای طی شده برای خدمتدهی به مشتریان می‌تواند در یک یا چند مرکز باشد. هر مرکز با تعداد انواع وسایلی که به آن تخصیص داده شده و مقدار کل کالایی که به آن مربوط است، شناخته می‌شود. در بعضی مسائل دنیای واقعی، مشتریان از قبل بین مراکز تقسیم می‌شوند، و وسایل حمل و نقل باید در انتهای مسیرهایشان به مرکز مربوط به خود باز گردند. در این موارد، مسأله مسیریابی وسایل حمل و نقل کلی را می‌توان به چند مسأله مستقل تقسیم نمود که هر کدام به یک مرکز متفاوت مربوط است.
حمل و نقل کالا‌ها با به کارگیری دستهایی از وسایل انجام می‌شودکه ترکیب و انداره اشان می‌تواند ثابت باشد و یا اینکه بر اساس نیاز مشتریان تعیین شود.
– مشخصات کلی وسایل حمل و نقل
مرکز آشیانه وسیله و امکان اینکه مسیر در مرکز دیگری غیر از مرکز آشیانه پایان پذیرد.
ظرفیت وسیله، که به صورت حداکثر وزن یا حجم یا تعداد دسته هایی که هر وسیله میتواند بارگیری نماید، بیان می شود.
امکان تقسیم کردن وسیله به چند بخش، با توجه به گنجایش و انواع کالاهایی که میتواند توسط آن حمل شوند.
ابزار مورد نیاز برای عملیات بارگیری و بارگذاری.
زیرمجموعه ایی از کمانهای گراف مسیر که وسیله میتواند آنها را طی کند.
هزینه مرتبط با استفاده از هر وسیله ( به ازای واحد مسیر، به ازای واحد زمان، به ازای مسیر و غیره).
– محدودیتهای کاربردی VRP