به طور کلی انتخاب و طراحی بهینه در بسیاری از مسائل علمی و فنی باعث تولید بهترین محصول یا جواب ممکن در یک شرایط خاص می شود. برای مثال تولید محصولات مناسب در حوزه های مختلف فنی و مهندسی وابسته به طراحی دقیق و بهینه ی شکل، اندازه و قطعات آن محصول است. به موازات تولید محصولات در شرایط بهینه، استفاده بهینه از امکانات موجود نیز حائز اهمیت است که می بایست در مسائل مختلف مورد توجه قرار گیرد. یکی از این مسائل، توزیع محصولات از مراکز پخش به مشتریان می باشد. در سالهای اخیر شرکتهای توزیع کالا و خدمات، اهمیت طراحی استراتژیهای پخش کارآمد را برای بهبود سطح سرویس دهی مشتریان و کاهش هزینه های حمل و نقل مورد توجه قرار داده اند. توزیع محصولات از دپوها به مشتریان مسئله ای کاربردی و رقابتی در مدیریت حمل و نقل است چرا که اتخاذ تصمیمات مناسب در زمانبندی و مسیریابی، سطح بالاتری از رضایتمندی مشتریان را نتیجه می دهد. مسئله توزیع به طور کلی تحت عنوان مسأله مسیریابی وسایل نقلیه (VRP) فرموله می شود که اولین بار توسط دنتزیگ و رامسر در سال 1959 ارائه گردید[1]. مسأله مسیریابی وسایل نقلیه، یکی از مسائل بهینه سازی بسیار پیچیده است که شامل طراحی و بهینه کردن مجموعه ای از مسیرها برای جریانی از وسایل نقلیه است که می بایست به مجموعه ای از مشتریان معین خدمت دهند. در این مسأله، وسایل نقلیه که هر کدام دارای ظرفیت محدودی می باشند در یک یا چند دپو مستقر بوده و می بایست مجموعه ای از مشتریان را که هر کدام دارای تقاضای مشخص و معینی هستند سرویس دهی نمایند. بنابراین هدف مسأله، طراحی و بهینه نمودن مجموعه ای از مسیرها برای وسایل نقلیه جهت سرویس دهی مشتریان می باشد بگونه ای که کل مسافت یا زمان سفر مینیمم گردد. در ضمن هر کدام از این جریانات می بایست از دپو شروع شده و به آن نیز ختم گردد. این مسأله خود به مسائل متنوعی تقسیم می شود که هر کدام در زمینه های متفاوت کاربرد مهمی دارند. یکی از انواع بسیار مهم و پرکاربرد آن، مسأله مسیریابی وسایل نقلیه در شرایط وجود چند دپو (MDVRP) می باشد. در این مساله از چندین دپو برای سرویس دهی مشتریان استفاده می شود، تعداد و محل استقرار دپوها از قبل تعیین گردیده و تعدادی وسیله نقلیه با ظرفیت مشخص در دپوها برای سرویس دهی به مشتریان مستقر می باشند که هر وسیله نقلیه بعد از سرویس دهی مشتریان به همان دپویی باز می گردد که از آن شروع به حرکت نموده است. کاربرد مساله MDVRP در صنعت حمل و نقل یکی از اصلی ترین کاربردهای MDVRP در صنعت حمل و نقل، بهینه سازی شبکه های توزیع کالا است. شرکت های لجستیک و حمل و نقل معمولاً باید کالاها را از چندین انبار یا دپو به مشتریان در نقاط مختلف جغرافیایی ارسال کنند. با استفاده از مدل MDVRP، این شرکت ها می توانند بهترین مسیرها را برای وسایل نقلیه خود تعیین کنند، به طوری که هزینه های سوخت، زمان سفر، و هزینه های عملیاتی به حداقل برسد. با تخصیص بهینه وسایل نقلیه به مسیرهای مختلف و تعیین بهترین دپوها برای شروع و پایان هر سفر، شرکت ها می توانند از هر وسیله نقلیه به طور کامل و مؤثر استفاده کنند. این مدیریت بهینه منابع می تواند هزینه های نگهداری و بهره برداری از ناوگان را کاهش داده و در عین حال بهره وری را افزایش دهد. در صنعت حمل و نقل ریلی نیز کاربرد ویژه MDVRP در مسیریابی لکوموتیوها جهت تخصیص بهینه این وسایل نقلیه به مسیرهای مختلف در شبکه راه آهن انجام می گیرد. با توجه به این که لکوموتیوها به عنوان منابع محدود در سیستم های حمل و نقل ریلی عمل می کنند، تخصیص صحیح آن ها به مسیرها می تواند تأثیر قابل توجهی بر بهره وری کل سیستم داشته باشد. در تعریف مساله مسیریابی لکوموتیوها با استفاده از MDVRP فرض بر این است که چندین مرکز اعزام جهت تأمین لکوموتیوهای مورد نیاز نواحی اطراف وجود دارد. در هر یک از این نواحی یک قطار تشکیل شده و می-بایست به نقطه دیگری که مقصد قطار مفروض می باشد اعزام گردد. در این مساله به دلیل وجود چندین دپوی مرکزی در نگهداری لکوموتیو، در مرحله اول اتخاذ روش تخصیص مناسب مورد نیاز است تا تعیین گردد تقاضای لکوموتیو هر یک از مشتریان راه آهن توسط کدامیک از مراکز تامین گردد. در مرحله بعدی ترتیب سرویس دهی مشتریان مطرح می گردد و باید بگونه ای باشد که در مسیریابی نهایی صرفه جویی بیشتری در هزینه حاصل گردد. در راه آهن ایران، تخصیص و مسیریابی لکوموتیوها به صورت دستی و بدون برنامه ریزی قبلی انجام می شود. این روش نه تنها باعث افزایش هزینه ها و کاهش کارایی می شود، بلکه امکان بروز خطاهای انسانی را نیز بالا می برد. به کارگیری روش های علمی و سیستماتیک برای حل این مسئله از اهمیت ویژه ای برخوردار است، به ویژه در شرایطی که شبکه حمل ونقل ریلی باید به طور مستمر با افزایش تقاضا و پیچیدگی های عملیاتی مواجه شود. بنابراین تخصیص و مسیریابی لکوموتیوها می تواند در بهبود بهره وری و کاهش هزینه ها در راه آهن ایران منجر گردد. در این پژوهش مساله مسیریابی لکوموتیوها با استفاده از MDVRP را به دو روش حل خواهیم کرد. در روش اول مرحله تخصیص و مرحله مسیریابی بطور همزمان انجام می شود، در روش دیگر مساله در دو مرحله حل می شود، مرحله اول باید توسط یکی از روشهای تخصیص تعیین گردد که تقاضای هر یک از مشتریان توسط کدامیک از مراکز تامین گردد بگونه ای که در مسیریابی نهایی صرفه جویی بیشتری در هزینه سفر حاصل گردد و سپس در مرحله دوم برای هر دپو یک مساله مسیریابی مجزا حل گردد. برای حل مساله نیز از آنجایی که روش های دقیق برای حل مساله MDVRP تنها برای نمونه هایی با اندازه کوچک قابل استفاده است و حل نمونه های بزرگتر به دلیل Np-hard بودن مساله با روش های دقیق امکان پذیر نیست، به همین دلیل از الگوریتم های ابتکاری و فرا ابتکاری برای حل مساله استفاده خواهیم کرد[1]. در مقایسه این دو نوع الگوریتم می توان گفت الگوریتم های فرا ابتکاری در هر زمان روی مجموعه ای از نقاط به منظور یافتن جواب عمل می کنند در صورتیکه الگوریتم های ابتکاری بهینه سازی در هر لحظه تنها یک نقطه خاص را مورد بررسی قرار می-دهند. همین اصل قابلیت خارج شدن از نقاط بهینه محلی را برای الگوریتم های فرا ابتکاری رقم می زند. همچنین الگوریتم های فرا ابتکاری بسیار زمان برتر از الگوریتم های ابتکاری بوده در حالی که جواب های حاصل از آنها جواب-هایی با کیفیت بالاتر می باشند. بنابراین این نتیجه حاصل می شود که با ترکیب این دو نوع الگوریتم شاید بتوان جواب هایی با کیفیت خوب و در زمان پایین تولید نمود. به همین دلیل در این پژوهش از ترکیب این دو نوع الگوریتم برای حل مساله مسیریابی لکوموتیوها جهت تخصیص بهینه و حداقل کردن هزینه استفاده خواهیم کرد.
