نوع مقاله : پژوهشی
1 دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان
2 دانشگاه صنعتی اصفهان
عنوان مقاله [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.