نوع مقاله : یادداشت فنی
نویسندگان
دانشکدهی مهندسی صنایع، دانشگاه صنعتی خواجه نصیرالدین طوسی
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسندگان [English]
In classical time dependent routing problems, it is assumed there is a unique edge between two nodes. In other words, these are designed based on a simple graph. However, for many urban areas, where there is complex urbanism and different traffic constraints, the traditional VRP viewpoint is not very suitable. In this article, a novel extension of the time dependent vehicle routing problem (TDVRP) is studied, where more than one edge between the depot and customers, and between customers, is possible. For this purpose, this paper proposes a model called the Time Dependent Vehicle Routing Problem in Multigraphs. The multigraph is a graph which is allowed to have multiple edges or parallel edges. Today, many of the transportation networks are defined in multiple graphs. Particularly, the model for studying vehicle routing problems in large cities can be useful. This model is designed, based on the Malandranki and Daskin (1992) proposed model for TDVRP. This formulation minimizes total travel time. The time dependent vehicle routing problem is an extension of vehicle routing problem and since VRP is a NP-hard problem, TDVRP is also NP-hard. For this reason, heuristics is used usually to solve these problems. In here, a tabu search (TS) algorithm is suggested for solving the proposed model. The main feature of the proposed heuristic is random selection between two switching strategies at every stage of neighborhood search. These two strategies are binary switching and reverse switching. This feature improves the algorithm performance. Finally, computational results of the proposed Tabu search algorithm, and the exact solution, using a CPLEX solver in GAMS V23.5 software, on 99 random instances, are compared. These instances cover a good range of different problems. This result presents the efficiency of the proposed algorithm in the computational time and quality of the solution.
کلیدواژهها [English]
)