پایان نامه حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده از یک الگوریتم فرابتکاری کارآمد

پایان‌نامه جهت اخذ درجه کارشناسی ارشد مهندسی صنایع

پائیز 1392

چکیده

در طی سال‌های گذشته، تلاش‌های زیادی به جهت کاهش هزینه حمل و نقل با استفاده از مدل‌های متفاوت مسأله مسیریابی وسیله نقلیه صورت گرفت. در واقع افزایش در هزینه های حمل و نقل بسیاری را تشویق کرد که هزینه حمل و نقل مرتبط با حرفه خود را با بهره‌گیری از سیستم مسیریابی وسیله نقلیه کاهش دهند. در این تحقیق ما مسأله مسیریابی وسیله نقلیه چند انبار با پنجره زمانی را مورد بررسی قرار می‌دهیم.

مسأله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی شامل ناوگانی از وسایل نقلیه می‌باشد که از انبارها حرکت نموده، دسته‌ای از مشتریان را ملاقات کرده و به انبار بر می‌گردند. ما در این تحقیق حالتی را در نظر گرفته ایم که دیگر نیازی نمی‌باشد هر وسیله نقلیه بعد از ملاقات مشتریان به انبار شروع حرکت برگردد بلکه ممکن است انبار ابتدای مسیر با انبار انتهای مسیر متفاوت از یکدیگر باشند. هر وسیله نقلیه دارای یک ظرفیت ثابت است، و هر مشتری دارای تقاضای مشخص است که باید کاملا ارضا شود. مسأله شامل ترکیب انتخاب ملاقات برای هر مشتری و تعیین مسیرهای وسایل نقلیه براساس قوانین مسأله مسیریابی وسیله نقلیه است؛ بطوریکه کل مسافت طی شده توسط هر وسیله نقلیه و کل زمان‌های زودکرد و دیرکرد و در مجموع کل هزینه کمینه شود.

از آنجائیکه مسأله مسیریابی وسیله نقلیه یک مسأله متعلق به کلاس NP-Hard است مسأله مسیریابی وسیله نقلیه چند انباره با پنجره زمانی نیز به عنوان تعمیمی از VRP جزء مسائل پیچیده و متعلق به کلاس NP-Hard است و برای حل آن از رویکردهای فراابتکاری استفاده می‌شود. در این پایان‌نامه الگوریتم ژنتیک برای حل مسأله مسیریابی وسیله نقلیه چند انباره با پنجره زمانی پیشنهاد شده است. وسعی شده است با استفاده از روش خوشه بندی ژنتیک، مشتریان را دسته‌بندی کرده تا فضای جستجوی مسأله را کاهش داده و سپس با استفاده از الگوریتم ژنتیک مجموعه جواب و تابع هدف مسأله را بدست می‌آ‌وریم.

کلمات کلیدی: مسیریابی وسایل نقلیه، چند‌انبار، پنجره زمانی، خوشه‌بندی، الگوریتم ژنتیک

فصل اول

کلیات تحقیق

-1- مقدمه

توسعه روز‌افزون شهر نشینی، صنایع و بخصوص صنایع پشتیبانی، جابجایی انسان و کالا را به صورت مسأله‌ای در آورده است که پیچیدگی آن دائماً در حال افزایش می‌باشد. رشد شهری باعث افزایش تقاضا در صنعت حمل و نقل شده که به تبع آن شهرها و صنایع بزرگ را دست به گریبان مشکلات زیادی در زمینه‌های تراکم ترافیکی، آلودگی هوا، اتلاف وقت‌های طولانی در مسیر سفرهای روزانه افراد، افزایش مصرف سوخت و استهلاک وسایل نقلیه و غیره کرده است.

برای حل مشکلات ترافیکی و مسایل اقتصادی، اجتماعی و زیست محیطی ناشی از آن در شهرهای بزرگ، صنایع تولیدی و بخش خدمات نیاز به یک سیستم مجهز و کارآمد حمل و نقل می‌باشد. در نتیجه تقاضای رو به افزایش برای راه‌حل‌هایی که اجرایی باشند و بتوانند تمامی منافع پیش‌بینی شده از جمله صرفه‌جویی در هزینه‌ها را با در نظر گرفتن حداکثر سرویس و استفاده بهینه از سرمایه و تجهیزات را حاصل نمایند وجود دارد. حمل و نقل داخل سازمانی، مسیر حرکت اتوبوس‌ها، سرویس‌های مدارس، سیستم‌های توزیع و نگهداری پخش پول و سرویس‌های بانکی و جمع‌آوری ضایعات صنعتی و غیره از جمله مسایلی هستند که می‌توان به آنها اشاره کرد.

برنامه ریزی حمل و نقل، امروزه یکی از زمینه‌های اساسی و مطرح در شاخه‌های مختلف علوم همانند تحقیق در عملیات، مهندسی صنایع و مهندسی عمران می‌باشد. هدف عمده این رشته، کمینه‌سازی هزینه حمل و نقل کالا و مواد بین دو سطح تولیدکننده و مصرف کننده می‌باشد، به طوری که تقاضای هر مصرف‌کننده باید توسط تولیدکنندگان ارضاء گردد. در این حالت با توجه به نوع مسأله مورد نظر عواملی همانند طول مسیر، کیفیت مسیر از لحاظ ساختاری و محیطی، ترافیک مسیر، گنجایش وسایل نقلیه و غیره مد نظر قرار می‌گیرند. چنانچه علاوه بر دو سطح تولید کننده و مصرف کننده، سطوح میانی نیز وجود داشته باشند، به آن شبکه حمل و نقل گفته می‌شود. به عنوان نمونه مسیریابی اتوبوس‌های داخل شهری حالت خاصی از شبکه حمل و نقل می‌باشد.

1-2- ضرورت و اهمیت برنامه‌ریزی حمل‌ونقل

حمل و نقل یکی از بخش‌های عمده و مهم، از اقتصاد هر کشوری به شمار می‌رود و همچنین یکی از مهمترین بخش‌های تشکیل دهنده هزینه تمام شده محصولات نهایی است. توسعه روز افزون شهر‌نشینی، صنایع و بخصوص صنایع پشتیبانی، جابجایی انسان و کالا را بصورت مسأله‌ای در آورده‌است که پیچیدگی آن دائماً در حال افزایش است. رشد شهری باعث افزایش فزاینده تقاضا در صنعت حمل‌ونقل شده که به تبع آن شهرها و صنایع بزرگ را دست به گریبان مشکلات زیادی در زمینه‌های تراکم ترافیکی، آلودگی هوا، اتلاف وقت طولانی در مسیر سفرهای روزانه افراد، افزایش مصرف سوخت و استهلاک وسایل نقلیه و غیره کرده است. برای حل مشکلات ترافیکی و مسایل اقتصادی، اجتماعی و زیست محیطی ناشی از آن در شهرهای بزرگ، صنایع تولیدی و بخش خدمات نیاز به یک سیستم مجهز و کارآمد حمل‌ونقل دارند. در نتیجه تقاضای رو به افزایش برای راه‌حل‌هایی که اجرایی بوده و بتواند تمامی منافع پیش‌بینی‌شده از جمله صرفه‌جویی در هزینه‌ها را با در نظر گرفتن حداکثر سرویس و استفاده بهینه از سرمایه و تجهیزات حاصل نماید، وجود دارد. نظافت خیابان‌ها، حمل‌ونقل داخل سازمانی، مسیرحرکت اتوبوس ها، سرویس مدارس، سیستم‌های توزیع و نگهداری پخش پول و سرویسهای بانکی و جمع آوری ضایعات صنعتی و غیره ازجمله مسایلی است که می توان به آن اشاره کرد.

در دهه‌های اخیر نتایج سودمندی در پروژه‌های بهینه‌سازی، بر مبنای روش‌های تحقیق در عملیات و برنامه‌ریزی ریاضی، در مدیریت موثر تدارک کالا و خدمت‌رسانی سیستم‌های توزیع دیده شده است. تعداد زیادی از کاربردهای واقعی جهانی، هم در آمریکای شمالی و هم در اروپا، بطور وسیع نشان داده که استفاده از روال‌های کامپیوتری برای برنامه‌ریزی فرآیند توزیع، صرفه‌جویی قابل توجهی را (معمولاً بین 5% تا 25%) در هزینه‌های عمومی حمل‌ونقل موجب می‌شود. در واقع، فرآیند حمل‌ونقل شامل همه مراحل سیستم‌های تولید و توزیع است. موفقیت بهره‌برداری از تکنیک‌های تحقیق در عملیات مدیون پیشرفت سیستم‌های کامپیوتری هم از نظر سخت‌افزار و هم از نظر نرم‌افزار و افزایش یکپارچگی سیستم‌های اطلاعاتی فرآیندهای تولید و تجاری است. فاکتور دیگر موفقیت که دارای اهمیت فوق العاده‌ای است، پیشرفت ابزارهای مدل‌سازی در سال‌های اخیر است. در واقع، مدل‌های پیشنهاد شده همه مشخصه‌های مسایل توزیع در کاربردهای واقعی، و الگوریتم‌های متناظر و اجراهای کامپیوتری را به حساب آورده و جواب‌های خوبی را برای نمونه‌های واقعی‌ جهانی در مدت زمان معقول پیدا می کند. (تاث وهمکاران،2002).

(جداول و تصاویر در فایل اصلی قابل مشاهده میباشد)

1-3- حمل‌ونقل در ایران

بخش حمل‌ونقل نیز به عنوان یکی از زیر بخش‌های مهم اقتصادی کشور که تولید آن به قیمت‌های ثابت دارای نرخ رشد بالاتری نسبت به نرخ رشد اقتصاد ملی بوده است، نیاز به توجه بیشتری در نظام مدیریتی کشور دارد. بررسی داده‌های آماری حساب های ملی در بازه ی بین دو مقطع زمانی 1370 تا 1386 نشان می دهد که در این دوره زمانی سهم فعالیت‌های حمل و نقل از تولید ناخالص ملی افزایش یافته است. افزایش سهم نسبی بخش حمل و نقل، انبارداری و ارتباطات از این عملکرد در سطح ملی 8/2 درصد بوده است. جدول (1-1)، مقایسه ارزش حمل و نقل در تولید ناخالص ملی در کشور در سال‌های 1370 تا 1386 را نشان می‌دهد. (شریعت،2004).

 بدین ترتیب، در روند تحولات اقتصادی، بخش حمل‌و‌نقل در سال‌های پس از انقلاب، بخصوص حمل‌و‌نقل زمینی، برجستگی بیشتری یافته و تکیه‌گاه اصلی جابجایی بار و مسافر بوده است، لذا با توجه به حجم بالای ارزش افزوده این بخش، اهمیت بیش از پیش بررسی و برنامه‌ریزی حمل و نقل در ایران به منظور تقلیل بخشی از هزینه‌های مربوطه احساس شده و برخورد علمی و منطقی با این مبحث مهم، امری ضروری است.

1-4- هدف از انجام مطالعه

برنامه‌ریزی حمل‌و نقل، امروزه یکی از رشته‌های اساسی و مطرح در شاخه‌های مختلف علوم همانند حمل و نقل در سیستمهای اقتصادی، تولیدی و خدماتی از جایگاه مهمی برخوردار است و بخش قابل‌توجهی از تولید ناخالص ملی هر کشوری را به خود اختصاص میدهد. مسأله مسیریابی وسیله‌نقلیه یکی از مهمترین مسائل برنامه‌ریزی حمل‌ونقل است که امروزه بسیار مورد توجه محققان و دانشمندان قرار گرفته است. هدف در این مسأله برآورده ساختن همه تقاضاها با حداقل هزینه می‌باشد. اگرچه اهداف فرعی تری از جمله حداقل کردن مسافت طی  شده، متعادل ساختن مسیر از جهت زمان سفر و حجم بار وسیله نقلیه، حداقل کردن خسارت دیرکرد ارائه خدمت به مشتریان، حداقل کردن تعداد مسافرت‌های هر وسیله نقلیه وغیره می‌باشد. یکی از زیر‌مجموعه‌های برنامه‌ریزی حمل‌و‌نقل، مسأله مسیریابی خودرو[1] است،شکل (1-2)، که از مسایل مهم و شناخته‌شده بهینه‌سازی ترکیبی[2] است که به دلیل اهمیت و کاربرد زیاد آن، از سال‌ها قبل مورد توجه محققان و پژوهشگران قرار گرفته است.

در معمول‌ترین شکل این مسأله، هدف بهینه‌سازی نحوه سرویس‌دهی به مجموعه‌ای از مشتریان است که از نظر موقعیت جغرافیایی با هم متفاوت هستند. سرویس‌دهی توسط ناوگان حمل و نقلی که در یک مرکز مستقر هستند، انجام می‌پذیرد. با توجه با قابلیت مسأله مسیریابی خودرو در مدل‌کردن انواع مسایل مطرح در لجستیک سازمان‌ها و به طور اخص سیستم‌های توزیع و یا تأمین آنها توجه به بالا بردن قابلیت‌های مسأله در مدل‌کردن شرایط دنیای واقعی از اهمیت بالایی برخوردار است. به عنوان نمونه، مسیریابی اتوبوس‌های داخل شهری، جمع‌آوری ضایعات، مسیریابی فروشنده دوره‌گرد، و واحدهای تعمیر و نگهداری، حالات خاصی از شبکه حمل و نقل است که از آن می‌توان به عنوان مسأله مسیریابی وسایل نقلیه یاد کرد.

-5- تعریف مسأله

VRP یک موضوع چالش برانگیز برای بسیاری از محققان از ابتدای معرفی آن توسط دانتزیگ و رامسر برای حل مسأله توزیع کامیون‌ها[3] بوده است. انواع روش های بهینه سازی پیشنهاد و مطالعه شده است. همان طور که عنوان گردید، اهمیت و کاربرد زیاد مسأله VRP در دنیای واقعی موجب گردیده است که مطالعه زیادی روی چگونگی مدل کردن انواع مسأله، توسعه فرضیات مسأله برای تطبیق با شرایط کاربردی در دنیای واقعی و همچنین ایجاد یا توسعه روش های حل مسأله به منظور کسب نتایج بهتر انجام پذیرد. این مطالعه نیز با هدف توسعه و ایجاد مدلی برای مسأله VRP، به منظور افزایش قابلیت مسأله در کاربردهای واقعی انجام پذیرفته است.

در این پایان‌نامه، مسأله VRP در حالت چند انباره و با در نظر گرفتن محدودیت پنجره زمانی به منظور در نظر گرفتن کاربردهای واقعی بیشتر مورد بررسی قرار گرفته است که در آن به کارگیری حالتی که انبار اول و آخر مسیر ممکن است متفاوت از هم باشند در نظر گرفته‌شده است و سپس با استفاده از روش خوشه‌بندی ژنتیک برای گروه‌بندی مشتریان و از الگوریتم ژنتیکی برای محاسبه تابع هدف، الگوریتم ترکیبی کارا برای حل ارائه می‌شود. جواب این مسأله شامل یافتن کوتاهترین مسیری که در آن هزینه هر مسیر کمینه شود. در انتها حل مسائل نمونه با استفاده از الگوریتم پیشنهادی ارائه شده است، که با استفاده از نرم افزار متلب کدنویسی و اجرا شده است.

1-6- جمع‌بندی و ساختار ارائه مطالب

فصول پایان‌نامه به شرح زیر تدوین شده‌اند: فصل اول تحقیق به معرفی اجمالی آن اختصاص یافته است. در این فصل مقدمه‌ای بر آشنایی با مسأله مسیریابی خودرو، اهمیت آن، هدف از انجام مطالعه و روش‌های بکار گرفته شده در این مطالعه آورده شده است. در فصل دوم به تعریف مسأله مسیریابی خودرو، تعاریف و نیز سوابق تحقیقات انجام شده پیرامون آن پرداخته شده است. در این فصل ضمن بیان مفاهیم اصلی و ادبیات موضوع مربوط به مسأله VRP که شامل تشریح اجزای مسأله، اهداف و محدودیت‌های آن می‌باشد، انواع حالت‌های خاص مسأله و انواع روش‌های آن و تحقیقات انجام شده پیرامون آنها ارایه شده است. در فصل سوم تحقیق، مدل پیشنهادی برای نوع خاصی از مسأله VRP تشریح شده است. سپس در همین فصل، الگوریتم فراابتکاری ژنتیک، برای حل مسأله مورد نظر ارائه می‌گردد. نتایج محاسباتی الگوریتم پیشنهادی با استفاده از نرم افزار مربوطه، در فصل چهارم مورد بررسی قرار می گیرد. سر انجام در فصل پنجم، با جمع‌‌بندی مطالب ارائه شده در تحقیق و نتیجه گیری کلی، پیشنهادها و توصیه‌هایی برای انجام مطالعات بعدی روی موضوع تحقیق آورده ارائه خواهد شد.

فصل دوم

ادبیات تحقیق

1-مقدمه

هدف از این بخش آشنایی با مدل‌های پایه‌ای مسیریابی، همچون فروشنده دوره‌گرد، مروری بر مدل‌های متنوع مسیریابی وسایل نقلیه، عوامل تاثیرگذاردر مدل‌ها و توابع هدف مختلف مطرح شده در این حوزه می‌باشد. در ادامه این بخش به طور خاص به بررسی کارهای انجام گرفته در مسیریابی وسایل نقلیه با چندین انبار و مسیریابی وسایل نقلیه با پنجره زمانی و ترکیب این دو پرداخته خواهد شد. شناخت کامل مسأله مسیریابی و مشتقات آن تاثیر به سزایی در افزایش توانایی و همچنین سهولت در رویه مدل‌سازی موارد واقعی دارد.

2-2- مسأله مسیریابی

هر مسأله که بدنبال تولید یک تور یا مجموعه‌ای از تورها بر روی یک شبکه یا زیر‌شبکه با هدف بهینه ساختن یک یا چند تابع هدف می‌باشد را مسأله مسیریابی گویند. تمامی این مسائل به نوعی یک حالت خاص از مسأله فروشنده دوره‌گرد به شمار می‌روند. در حقیقت با استفاده از این مسأله بدنبال مدل‌سازی موارد حقیقی هستیم (تاث و همکاران،2002). اجزای یک مسأله مسیریابی عبارتند از: شبکه[4]، هزینه[5]، تقاضا[6]، ناوگان[7] و اهداف[8]. 

2-3- مسأله فروشنده دوره‌گرد

مسأله فروشنده دروه‌گرد (TSP)[9] یکی از بنیادی‌ترین و مشهورترین مسائل در زمینه حمل و نقل و مسأله مسیریابی می‌باشد. در مسأله فروشنده دوره‌گرد هدف یافتن یک دور، مسیر کامل(تور) برای یک فروشنده دوره‌گرد است که در آن تمامی شهرها (مشتریان) با کمترین هزینه ممکن ملاقات شوند و فروشنده از هر کدام تنها و تنها یک بار عبور نماید، سپس این تور در همان شهر اولیه که سفر از آنجا آغاز شده بود پایان یابد (تاث و همکاران،2002). نمایی از مسأله فروشنده دوره­گرد در شکل 2-1 نشان داده شده است.

Abstract

During the past few years, there have tremendous efforts on improving the cost of transportation using varieties of Vehicle Routing Problem (VRP) models. In fact, the recent rise on transportation cost has motivated s many to reduce the cost of transportation associated with their business through an improved implementation of VRP systems. In this research we study the Multi-depot Vehicle Routing Problem with Time Window (MDVRPTW).

The MDVRPTW includes a fleet (vehicle with identical capacities) that move from depot; visit a group of customers return to depot. We consider a case in this research that there is no need for each vehicle to return to its primary depot which they have started their movement after serving customers. Rather, the primary depot may be different from the end depot. Each vehicle has a fixed capacity. So, each customer has a predefined demand that must be satisfied in one visit, completely. The problem consist of selected a visit combination for each customer and establishing the vehicle routes according to the VRP rules, so that, the total travelled distance by each vehicles and total the latest  times and the earliest times and finally total cost would be minimized.

Due to the VRP is generalization of the MDVRPTW and the VRP has been shown to be NP-hard, the MDVRPTW should be solved by meta-heuristic methods.

In this thesis a Genetic Algorithm (GA) is proposed to solve the MDVRPTW. And try to grouping customers by using Genetic Algorithm clustering method to reduce research space of the problem and by Genetic Algorithm, we obtain the answer bundle and objective function.

Keyword: Vehicle Routing Problem, Multi-depot, Time Window, clustering, Genetic Algorithm.

منابع ومآخذ

قصیری کیوان، قنادپور سیدفرید؛ مسأله مسیریابی وسیله نقلیه همراه با پنجره زمانی مبانی، روش‌ها و پیشرفت‌ها، همراه با مطالعات موردی درصنعت حمل و نقل، مرکز انتشارات علمی دانشگاه آزاد قزوین،1386.

احمد صادقیه ؛تصمیم‌گیری براساس الگوریتم ژنتیک در بهینه‌سازی، ناشر انتشارات علم نوین، 1384.

Toth, P., and Vigo, D., “The vehicle routing problem”, University degli Studi di Bologna, Italy, 2002.

Shariat, M.A., “The solution to vehicles routing problem with soft time windows using an Efficient algorithm”, M.SC. Thesis, Department of Industrial Engineering,

Islamic Azad University, Tehran South Branch, 2004 (in Farsi).

Toth, P., and Vigo, D., “The vehicle routing problem”, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002.

Zohrevand,A.M ,” Designing and solving a multi-objective period vehicle routing problem by an efficient meta-heuristic algorithm” ,Thesis, Department of Industrial Engineering, University of Tehran Faculty of Engineering,2011.

Rafiee Darmian,K. “Designing and Solving a Rich Vehicle Routing Problem by an Efficint Meta-Heuristic Algorithm” Thesis, Department of Industrial Engineering, University of Tehran Faculty of Engineering,2011

Golden, B.L., and Assad, A.A., “Vehicle routing: methods and studies”, New York:North ,Holland, 1988.

Laporte, G., Mercure, H., and Nobert, Y., “An exact algorithm for the asymmetrical capacitated vehicle routing problem”, Networks, 16, 33-46, 1986.

Miller, D.L., “A matching based exact algorithm for capacitated vehicle routing problems”, ORSA Journal on Computing, 7, 1-9, 1995.

Christofides, N., Mingozzi, A., and Toth, P., “Exact algorithms for the vehicle routing problem based on the spanning tree and shortest path relaxations”, Mathematical Programming, 20, 255-282, 1981.

Laporte, G., Nobert, Y., and Desrochers, M., “Optimal routing under capacity and distance restrictions”, Operations Research, 33, 1050-1073, 1985.

Augerat, P., Belenguer, J.M., Benavent, E., Corberan, A., Naddef, D., and Rinaldi, G., “Computational results with a branch and cut code for the capacitated vehicle routing problem”, Technical Report RR 949-M, Universite Joseph Fourier, Grenoble, 1995.

Baldacci, R., Hadjiconstantinou, E., and Mingozzi, A., “An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation”, Operations Research, 52, 723-738, 2004.

Fukasawa, R., Longo, H., Lysgaard, J., Poggi de Aragao, M., Reis, M., Uchoa, E., and Werneck, R.F., “Robust branch-and-cut-and-price for the capacitated vehicle routing problem”, Mathematical Programming, 106, 491 511, 2006.

Golden, B.L., Wasil, E.A., Kelly, J.P., and Chao, I.M., “Metaheuristics in Vehicle Routing”, Fleet Management and Logistics, T.G. Crainic and G. Laporte (eds), 33-56, Kluwer, Boston, 1998.

Gillett, B.E., and Miller, L.R., “A heuristic algorithm for the vehicle-dispatch problem”, Operations Research, 21, 340-349, 1974.

Fisher, M.L., and Jaikumar, R., “A generalized assignment heuristic for the vehicle routing problem”, Networks, 11, 109-124, 1981.

Lin, S., “Computer solutions of the travelling salesman problem”, Bell System Technical Journal, 44, 2245-2269, 1965.

Van Breedam, A., “An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related, and time-related constraints”, PhD dissertation, University of Antwerp, Belgium, 1994.

Osman, I.H., “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem”, Annals of Operations Research, 41, 421-451, 1993.

Clarke, G., and Wright, J.V., “Scheduling of vehicles form a central depot to a number of delivery points”, Operations Research, 12, 315-338, 1964.

Dueck, G., “New optimization heuristics: The great deluge algorithm and the record-to record travel”, Journal of Computational Physics, 104, 86-92, 1993.

Willard, J.A.G., “Vehicle routing using r-optimal tabu search”, MSc dissertation, The Management School, Imperial College, London, 1989.

Taillard, E.D., “Parallel iterative search methods for vehicle routing problems”, Networks, 23, 661-673, 1993.

Rego, C., and Roucairol, C., “A parallel tabu search algorithm using ejection chains for the vehicle routing problem”, Osman, I.H., Kelly, J.P. (Eds.), Meta-Heuristics: Theory and Applications, 661-675, Kluwer Academic, Boston, 1996.

Xu, J., and Kelly, J.P., “A network flow-based tabu search heuristic for the vehicle routing problem”, Transportation Science, 30, 379-393, 1996.

Toth, P., and Vigo, D., “The granular tabu search and its application to the vehicle routing problem”, INFORMS Journal on Computing, 15, 333-346, 2003.

Holland, J.H., “Adaptation in Natural and Artificial Systems”, The University of Michigan Press, Ann Arbor, 1975.

Prins, C., “A simple and effective evolutionary algorithm for the vehicle routing problem”, Computers &Operations Research, 31, 1985-2002, 2004.

Baker, B.M., and Ayechew, M.A., “A genetic algorithm for the vehicle routing problem”, Computers &Operations Research, 30(5), 787-800, 2003.

Reimann, M., Stummer, M. and Doerner, K., “A Savings based Ant System for the Vehicle Routing Problem”, Langdon et al. (Eds.): Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), 1317-1325, Morgan Kaufmann, New York, 2002.

Reimann, M., Doerner, K., and Hartl, R.F., “D-ants: Savings based ants divide and conquer for the vehicle routing problem”, Computers &Operations Research, 31, 563-591, 2004.

Golden, B.L., Assad, A.A., Levy, L., and Gheysens, F.G., “The fleet size and mix vehicle routing problem”, Computers &Operations Research, 11, 49-66, 1984.

Renaud, J., and Boctor, F.F., “A sweep-based algorithm for the fleet size and mix vehicle routing problem”, European Journal of Operational Research, 140, 618-628, 2002.

Osman, I.H., and Salhi, S., “Local search strategies for the vehicle fleet mix problem”,

Rayward-Smith, V.J., Osman, I.H., Reeves, C.R., Smith, G.D. (Eds.), 131-153, Wiley, New York, 1996.

Gendreau, M., Laporte, G., Musaraganyi, C., and Taillard, E., “A tabu search heuristic for the heterogeneous fleet vehicle routing problem”, Computers & Operations Research, 26, 1153-1173, 1999.

Wassan, N.A., and Osman, I.H., “Tabu search variants for the mix fleet vehicle routing problem”, Journal of the Operational Research Society, 53, 768-782, 2002.

Salhi, S., and Rand, G.K., “Incorporating vehicle routing into the vehicle fleet composition problem”, European Journal of Operational Research, 66, 313-330, 1993.

Gendreau, M., Hertz, A., and Laporte, G., “New insertion and postoptimization procedures for the traveling salesman problem”, Operations Research, 40(6), 1086-1094, 1992.

Paraskevopoulos, D.C., Repoissis, P.P., Tarantilis, C.D., Ioannou, G., and Prastacos, G.P., “A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows”, Journal of Heuristics, 14, 425-455, 2008.

Imran, A., and Salhi, S., “A variable neighborhood search-based heuristic for the heterogeneous fleet vehicle routing problem”, European Journal of Operational Research, 197(2), 509-518, 2009.

Liu, S., Huang, W., and Ma, H., “An effective genetic algorithm for the fleet size and mix vehicle routing problems’, Transportation Research Part E, 45(3), 434-445, 2009.

Dror, M., and Trudeau, P., “Split delivery routing”, Naval Research Logistics, 37, 383-402, 1990.

Dror, M., Laporte, G., and Trudeau, P., “Vehicle routing with split deliveries”, Discrete Applied Mathematics, 50(3), 239-254, 1994.

Belenguer, J.M., Martinez, M.C., and Mota, E., “A lower bound for the split delivery vehicle routing problem”, Operations Research, 48, 801-810, 2000.

Lee, C.G., Epelman, M.A., White, C.C., and Bozer, Y., “A shortest path approach to the multiple-vehicle routing problem with split pick-ups”, Transportation Research Part B, 40(4), 265-284, 2006.

Dror, M., and Trudeau, P., “Savings by split delivery routing”, Transportation Science, 23(2), 141-145, 1989.

Ho, S.C., and Haugland, D., “A tabu search heuristic for the vehicle routing problem with time windows and split deliveries”, Computers & Operations Research, 31(12), 1947-1964, 2004.

Archetti, C., Hertz, A., and Speranza, M.G., “A tabu search algorithm for the split delivery vehicle routing problem”, Transportation Science, 40(1), 64-73, 2006.

Min, H., “The multiple vehicle routing problem with simultaneous delivery and pickup points”, Transportation Research Part A, 23(5), 377-386, 1989.

Halse, K., “Modeling and Solving Complex Vehicle Routing Problems”, PhD thesis, Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Lyngby, 1992.

Golden, B.L., Baker, E.K., Alfaro, J.L., and Schaffer, J.R., “The Vehicle Routing Problem with Backhauling: Two Approaches”, Working paper MS/S 85-017, University of Maryland, College Park, 1985.

Casco, D.O., Golden, B.L., and Wasil, E.A.,” Vehicle routing with backhauls: Models, algorithms, and case studies”, Golden, B.L., Assad, A.A. (Eds.), Vehicle Routing: Methods and Studies, 127-147, Elsevier, Amsterdam, 1988.

Salhi, S., and Nagy, G., “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling”, Journal of the Operational Research Society 50, 1034- 1042, 1999.

Mourgaya, M., and Vanderbeck, F., “Probleme de tournees de vehicules multiperiodiques: Classification et heuristique pour la planification tactique”, RAIRO Operations Research, 40, 169-194, 2006.

Russell, R., and Gribbin, D., “A multi-phase approach to the period routing problem”, Networks, 21, 747-765, 1991.

Chao, I.M., Golden, B.L., and Wasil, E., “An improved heuristic for the periodic vehicle routing problem”, Networks, 26, 25-44, 1995.

Bertazzi, L., Paletta, G., and Speranza, M.G., “An improved heuristic for the period traveling salesman problem”, Computers &Operations Research, 31, 1215-1222, 2004.

Cordeau, J., Gendreau, M., and Laporte, G., “A tabu search heuristic for periodic and multi-depot vehicle routing problem”, Networks, 30, 105-119, 1997.

Angelelli, E., and Speranza, M.G., “The periodic vehicle routing problem with intermediate facilities”, European Journal of Operational Research, 137, 233-247, 2002.

Alegre, J., Laguna, M., and Pacheco, J., “Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts”, European Journal of Operational Research, 179, 736-746, 2007.

Alonso, F., Alvarez, M.J., and Beasley, J.E., “A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions”, Journal of the Operational Research Society, 7(23), 963-976, 2008.

Hemmelmayr, V.C., Doener, K.F., and Hartl, R.F., “A variable neighborhood search for periodic routing problems”, European Journal of Operational Research, 195, 791-802, 2009.

Sumichrast, R.T., Markham, I.S., “A heuristic and lower bound for a multi- depot routing problem”, Computers & Operation Research, Vol. 22, 1995, pp. 1047- 1056.

Renaud J, Laporte G, Boctor FF. A tabu search heuristic for the multi-depot vehicle routing problem. Comput Oper Res 1996;23:229–35.

Ho W, Ho TS, Ji P, Lau CW. A hybrid genetic algorithm for the multi-depot vehicle routing problem. Eng Appl Artif Intell (2008);21:548–57.

Hadjiconstantinou, E., Baldacci, R., A multi-depot period vehicle routing problem arising in the utilities sector. Journal of the Operational Research Society 49(`1998), 1239–1248.

M. Mirabi, S. M. T. F. Ghomi, and F.Jolai, “Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem,” Robotics and computer integrated manufacturing, vol. 26, pp. 564-569, December 2010.

Salhi, S., Sari, M., A multi-level composite heuristic for the multidepot vehicle fleet mix problem. European Journal of Operational Research 103(1997), 95–112.

Cordeau JF, Gendreau M, Laporte G. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 1997;30:105–19.

Crevier B, Cordeau J, Laporte G. The multi-depot vehicle routing problem with inter-depot routes. Eur J Oper Res 2007;176:756–73.

Fisher, M.L., “Optimal solution of vehicle routing problems using minimum k-trees”, Operations Research, 42, 626-642, 1994.

Kallehauge, B., Larsen, J., and Madsen, O.B.G., “Lagrangian duality applied to the vehicle routing with time windows’, Computers &Operations Research, 33, 1464-1487, 2006.

Desrochers, M., Desrosiers, J., and Solomon, M.M., “A new optimization algorithm for the vehicle routing problem with time windows”, Operations Research, 40, 342-354, 1992.

Kohl, N., Desrosiers, J., Madsen, O.B.G., Solomon, M.M., and Soumis, F., “2-path cuts for the vehicle routing problem with time windows”, Operations Research, 35, 256-273, 1999.

Solomon, M.M., “Algorithms for the vehicle routing and scheduling problems with timewindow constraints”, Operations Research, 35(2), 254-265, 1985.

 Van Landeghem, H.R.G., “Bi-criteria heuristic for the vehicle routing problem with time windows”, European Journal of operational Research, 36, 217-226, 1988.

Potvin, J.Y., and Rousseau, J.M., “A parallel route building algorithm for the vehicle routing and scheduling problem with time windows”, European Journal of Operational Research, 66, 331-340, 1993.

Dullaert, W., and Bräsy, O., “Routing relatively few customers per route”, Sociedad de Estadistica e Investigacion Operativa, 11(2), 325-336, 2003.

Taillard, E.D., Badeau, P., Gendreau, M., Guertin, F., and Potvin, J.Y., “A tabu search heuristic for the vehicle routing problem with soft time windows”, Transportation Science, 31, 170-186, 1997.

Badeau, P., Guerin, F., Gendreau, M. Potvin, J., and Tailard, E., “A parallel tabu search heuristic for the vehicle routing problem with time windows”, Transportation Research, 5(2), 109-122, 1997.

Bräysy, O., and Dullaert, W., “A fast evolutionary metaheuristic for the vehicle routing problem with time windows”, International Journal of Artificial Intelligence Tools, 12(2), 153-172, 2003.

Le Bouthillier, A., and Crainic, T.G., “A cooperative parallel meta-heuristic for the vehicle routing problem with time windows”, Computers & Operations Research, 32(7), 1685- 1708, 2005.

Hoong Chuin Lau ,Melvyn Sim, Kwong Meng Teo, Vehicle routing problem with time windows and a limited number of vehicles, European Journal of Operational Research 148 (2003) 559–569

Chia-Ho CHEN, Ching-Jung TING, A hybrid ant colony system for vehicle routing problem with time windows, Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 2822 – 2836, 2005.

BEATRICE OMBUKI, BRIAN J. ROSS AND FRANKLIN HANSHAR, Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows, Applied Intelligence 24, 17–30, 2006.

G.B. Alvarenga, G.R. Mateus, G. de Tomi, A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research 34 (2007) 1561–1584.

Brian Kallehauge, Formulations and exact algorithms for the vehicle routing problem with time windows, Computers & Operations Research 35 (2008) 2307 – 2330.

Yaw Chang,  Lin Chen, Solve the vehicle routing problem with time windows via a genetic algorithm , DISCRETE AND  CONTINUOUS. DYNAMICAL  SYSTEMS  SUPPLEMENT  2007.

Bin Yu, Zhong Zhen Yang, An ant colony optimization model: The period vehicle routing problem with time windows, Transportation Research Part E 47 (2011) 166–181.

Raul Banos, Julio Ortega, Consolacion Gil, Antonio Fernandez, Francisco de Toro, A Simulated Annealing-based parallel multi-objective approach to vehicle routing problems with time windows, Expert Systems with Applications 40 (2013) 1696–1707

Manolis N.Kritikos, GeorgeIoannou The balanced cargo vehicle routing problem with time windows, Int. J. Production Economics 123 (2010) 42–51.

J.Holland. Adaptation Natural and Artificial Systems, university of Michigan, (1975)

D.E.Goldberg. Genetic Algorithms in search ,optimization and Machine learning Addison-Wesley, Wokingham,(1989).

M.Gen and R.Chen. Gentic Algorithm & engineering design, Awiley Inter science publication, (1997).

M.Gen, Genetic Algorithms & Engineering optimization, New York, John Wiley, (2000).

S.N.Sivanandam, S.N.Deepa; 2008; Introduction to Genetic Algorithms; Springer-Verlag Berlin Heidelberg 2008; Springer Berlin Heidelberg New York; chapter 2; ISBN 978-3-540- 73189-4; pp. 31-53.

Faezeh Hosseininezhad, Afshin Salajegheh, Study and Comparison of Partitioning Clustering Algorithms, Iranian Journal of Medical Informatics (2012) Vol 2, Issue 1.

Dondo R , Cerda J , A Hybrid Local Improvement Algorithm For Large Scale Multi-Depot Vehicle Routing Problems With Time Windows , Computers and Chemical Engineering 33 (2009) 513–530.

Dondo R , Cerda J , A Cluster-based Optimization Approach For the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem With Time Windows, European Journal of Operational Research 176 (2007):pp, 1478–1507.

Xu.Y, Wang.L, Yang.Y , A New Variable Neighborhood Search Algorithm For the Multi-Depot Heterogeneous Vehicle Routing Problem With Time Windows, Electronic Notes in Discrete Mathematics 39(2012) :pp,289-296.

Kek, A.G.H., Cheu, R.L., Meng, Q., “Distance- Constrained Capacitated Vehicle Routing Problems with Flexible Assignment of Start and End Depots”, Mathematical and Computer Modeling, (2008) ,Vol. 47, No 1-2, pp. 140- 152.

Eidi ,A.R. AbdulRahimi, H., Proposition and Solution Of the Multi-periodic and Multi-depot Routing Problem Model With Flexibility in Determining the finished depot of each route, International  Journal of production management and Industries Engineering , (2012); Vol,23.  N.3. pp, 334-349.

http://neo.lcc.uma.es/radiaeb/WebVRP/index.html.