An Improved Tabu Search for Open Vehicle Routing Problem

In the open vehicle routing problem (OVRP), a vehicle does not return to the depot after servicing the last customer on a route. Today, the OVRP is encountered in practice in the home delivery of packages and newspapers. Contractors who are not employees of the delivery company use their own vehicles and do not return to the depot. An improved tabu search for the open vehicle routing problem is considered in this paper. The purpose of the proposed approach is to decrease the number of used vehicles and the total travel cost. An extensive numerical experiment was performed on benchmark problem instances available in literature, the computational results are presented to show the high effectiveness and performance of the proposed approaches.