TWO MATHEMATICAL MODELS AND FOUR HEURISTIC ALGORITHMS FOR VEHICLE ROUTING PROBLEM WITH SELECTING LOCATION-TIME OF CUSTOMERS

Transportation is one of the most signi cant issues in the eld of logistics. The development and expansion of urban networks, the increase in population, and the consequent increase in the trac of road networks have led to an increase in the importance and sensitivity of transportation compared to the past. On the other hand, transportation accounts for a signi cant part of any country's Gross National Product (GNP), and a lot of research has been done to improve the transportation situation. 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 developed form of VRPs is the Generalized Vehicle Routing Problem (GVRP). This problem is relatively new and is one of the novel areas for research. In the generalized vehicle routing problem, the customers are partitioned into clusters, each with a given demand. The objective is to construct a minimum-cost set of delivery routes serving one of the customers in each cluster in a way that the total demand of the customers served by a single vehicle does not exceed the vehicle capacity. In this article, we have considered generalized vehicle routing problem with time windows and sought to minimize the total traveling time of routes. This objective function is a comprehensive expression that includes both distances and waiting times. We have proposed two mathematical formulations for GVRPTW to minimize the total duration of routes. The rst model is a three-dimensional model based on nodes, and the second model is based on ow and is presented by two indices. We have also designed a two-phase heuristic algorithm to solve the problem. In the rst phase, an initial solution is created, and in the second phase, a heuristic algorithm is implemented to improve the constructed solutions. Three dierent approaches are considered to construct the initial solution, and based on these three approaches, four heuristic algorithms are designed. The rst category is based on savings, including both sequential and parallel saving algorithms. The second category is insertionbased heuristics which is analyzed through 25 strategies, and the last category is a time-oriented nearest neighbor heuristic algorithm. Finally, the performances of the proposed algorithms are compared with each other. The results show the good performance of the insertion-based algorithm compared to other algorithms.