A developed Tabu Search algorithm for heterogeneous fleet vehicle routing problem

摘要

This paper deals with the vehicle routing problems for urban good distribution. The mix fleet size problem is a variant of the vehicle routing problem called Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The objective is to design a set of routes in order to minimize the sum of the costs. The purpose of this study is to develop a Tabu search (TS) heuristic to solve the HFVRP. The initial solution is obtained by a modified Clarke & Wright saving algorithm than treated by some fundamental and others new concepts of the TS algorithm. Our Tabu search algorithm uses a new procedure called Fusion in parallel with the split procedure in order to explore new search spaces. In addition, a number of neighborhood structure are combined together in a process for intensifying the local search. Besides, the proposed algorithm is boosted with an adaptive memory algorithm, known as probabilistic diversification and intensification. On several benchmark instances, the TS produces high-quality solutions, including two new best solutions for small sized instances. The results obtained illustrate the effectiveness of the approach and its applicability to routing problems.