A heuristic algorithm based on tabu search for vehicle routing problems with backhauls

In this paper, a heuristic algorithm based on Tabu Search Approach for solving the Vehicle Routing Problem with Backhauls (VRPB) is proposed. The problem considers a set of customers divided in two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. In the proposed algorithm, each route consists of one sub-route in which only the delivery task is done, and one sub-route in which only the collection process is performed. The search process allows obtaining a correct order to visit all the customers on each sub-route. In addition, the proposed algorithm determines the best connections among the sub-routes in order to obtain a global solution with the minimum traveling cost. The efficiency of the algorithm is evaluated on a set of benchmark instances taken from the literature. The results show that the computing times are greatly reduced with a high quality of solutions. Finally, conclusions and suggestions for future works are presented.