ارائه دو مدل ریاضی و چهار الگوریتم ابتکاری برای مسئله‌ی مسیریابی وسایل نقلیه با درنظر گرفتن مکان-زمان‌های پیشنهادی مشتریان

نوع مقاله : پژوهشی

نویسندگان

1 دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان

2 دانشگاه صنعتی اصفهان

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

Two mathematical models and four heuristic algorithms for vehicle routing problem with selecting location-time of customers

نویسنده [English]

  • ali aghadavoudi jolfaei 1
1 department of industrial and systems engineering
2 isfahan university of technology
چکیده [English]

One of the most challenging problems in transportation is the Vehicle Routing Problem (VRP). VRP is one of the most important classic optimization problems that has been studied and developed by many researchers since its introduction. One of the developed forms is the Generalized vehicle routing problem (GVRP). This problem is relatively new and is one of the pristine areas for research. In the generalized vehicle routing problem, the set of customers is partitioned into clusters and each cluster has a given demand. The objective is to construct a minimum cost set of delivery routes serving one of the customers in each cluster such that the total demand of the customers served by a single-vehicle does not exceed the vehicle capacity. In this article, we consider generalized vehicle routing problem with time windows and seek to minimize the total travel time of routes. This objective function is a comprehensive expression that includes both distances and waiting times. we propose two mathematical formulations for GVRPTW to minimize the total duration of routes. The first model is a three-dimensional model based on nodes and the second model is based on flow and is presented as two indices. We also designed a two-phase heuristic algorithm to solve the problem. In the first phase, an initial solution is created, and in the second phase, a heuristic algorithm is implemented to improve the constructed solutions. Three different approaches are considered to construct the initial solution and based on these three approaches, four heuristic algorithms are designed. The first category is based on savings which include two sequential saving algorithm and parallel saving algorithm. The second category is insertion-based heuristics which is analyzed with 25 strategies, and the last category is a time-oriented nearest neighbor heuristic algorithm. Finally, the performance of the proposed algorithms are compared with each other. The results show the good performance of the insertion-based algorithm compared to other algorithms.

کلیدواژه‌ها [English]

  • Vehicle Routing Problem
  • Selective Vehicle Routing Problem
  • location-times of customers
  • Time Windows
  • Heuristic algorithms