Model and Solution Approach for Multi-Period and Multi-Depot Vehicle Routing Problem with Flexibility in Specifying the Last Depot of Each Route

ارايه و حل مدل مساله مسيريابي وسايل نقليه در حالت چند دوره اي و چند قرارگاهي به همراه انعطاف پذيري در تعيين قرارگاه پاياني هر مسير

امروزه با توجه به افزايش جمعيت و گسترش شهرها و در پي آن افزايش تقاضا براي دريافت كالا و خدمات، مسايل مربوط به حمل و نقل اهميت بسزايي پيدا كرده اند. يكي از مسايل مهم در بحث حمل و نقل كه توجه محققين بسياري را به خود معطوف ساخته است مساله مسيريابي وسيله نقليه مي باشد. در اين پژوهش، مدل جديدي از مساله مسيريابي چند قرارگاهي و براي چند دوره متوالي به صورت برنامه ريزي خطي عدد صحيح فرموله مي شود كه در آن الزامي به بازگشت وسايل نقليه به قرارگاه اوليه نبوده و قرارگاه ابتدايي و انتهايي براي هر مسير در هر دوره با توجه مشتريان ساير دوره ها مشخص مي گردد. هدف اصلي مدل ارايه شده نيز سرويس دهي به مجموعه اي از مشتريان در طي دوره هاي مختلف از طريق چندين قرارگاه مي باشد. سپس يك الگوريتم فرا ابتكاري(الگوريتم ژنتيك) به عنوان راه حل مدل ارايه شده مورد مطالعه و توسعه قرار خواهد گرفت. از نتايج مهم اين مقاله مي توان به كاهش مجموع هزينه هاي مسيريابي با لحاظ نمودن ويژگي انعطاف پذيري در تعيين قرارگاه پاياني هر مسير اشاره نمود. معتبر بودن و كارايي محاسباتي الگوريتم ارايه شده در بررسي تعدادي از مسايل نمونه توليد شده نشان داده شده است.

Nowadays transportation problems are drawing more attention with respect to increasing demand for receiving products and services due to population increase and expansion of cities. One of the most important issues of transportation problems which are drawing the attention of the most researchers is vehicle routing problem. In this research, a new linear integer programming for multi-depot vehicle routing problem with multiple consecutive periods is formulated such that there is no obligation for vehicle to return to the fist depot and the first and the last depot for each route, in each period are specified based on the customers of other periods. The main goal of the presented model is servicing the set of customers during different periods through via different depots. Then a met-heuristic algorithm (genetic algorithm) is analyzed as a solution approach of the problem. One of the main results of this research is the reduction of routing costs due to flexibility in determining the last depot of each route. Some of the generated benchmark instances are used to show the performance and validity of the algorithm.