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.