Modelling and Solving Time Dependent Vehicle Routing Problem with Semi Soft Time Windows in Multigraphs

In the traditional “Time dependent Vehicle Routing Problems”, it is assumed there is only one edge between two nodes. In other words, these are designed based on a simple graph. However, in many urban areas, where there is complex urbanism and different traffic constraints and conditions, traditional VRP viewpoint is not very suitable.
In this article, an 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. The multigraph is a graph which is permitted to have multiple edges or parallel edges. Today, many of the transportation networks are defined in multiple graphs. Given the importance of FIFO property, it must be ensured. In this article, This is done using a special process. We proposed a model that is called “TDVRPMSSTW”. In this model, Semi Soft Time Windows is defined for customers. This formulation minimizes the total travel time, Time Window penalties and vehicle fixed cost.
Time Dependent Vehicle Routing Problem is an extension of Vehicle Routing Problem and since VRP is a NP-hard problem, therefore TDVRP is NP-hard too. So heuristics is used usually to solving these problems. In here, a Tabu Search (TS) algorithm is suggested for solving proposed model. The main feature of the proposed heuristic is randomly selection between two switching strategies in every stage of neighborhood search. These two strategies are binary switching and reverse switching. This feature improves the algorithm performance.
Finally, computational results of proposed Tabu search algorithm and the exact solution using GAMS software on the 40 designed instances are compared. These instances cover a good range of different problems with small dimensions. This result presents the efficiency of the proposed algorithm in computational time and quality of the solution.