A filter-and-fan approach to the multi-trip vehicle routing problem

The multi-trip vehicle routing problem (MTVRP) is studied whose task is to determine both the multiple trips to satisfy all the customers´ demands and the assignment of the trips to vehicles with the objective of minimizing the travel cost of the trips. For this problem, an algorithm based on filter-and-fan approach is proposed. Tabu search is adopted to initialize the procedure and provide useful moves to filter-and-fan searching tree, so that tabu search is diversified by filter-and-fan searching for guiding it to a difference region of the solution space. Then the solution is improved by the filter-and-fan approach which can be viewed as a search strategy on abbreviated neighborhood tree. Computational results are carried out to illustrate the proposed algorithm is effective and efficient.