An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows

The heterogeneous fixed fleet open vehicle routing problem with time windows is a very significant type of the vehicle routing problem (VRP) that aims to find the minimum fixed and vari-able cost of transportation for a heterogeneous fleet with a fixed number in which the capacity of every vehicle and usage of the vehicles should not be ignored. Also, in this problem, each customer has a special time window for servicing and each vehicle starts its route from the warehouse and ends up in one of the customers. We propose a mixed integer linear programming model of this problem. Since this problem, as well as open VRP and VRP with fixed heterogeneous fleet are hard NP problem, an improved tabu search algorithm is proposed to solve the problem. Our proposed algorithm uses a modified sweep algorithm to generate some initial solutions. Besides, a variable tabu list and some new mechanisms for intensification and diversification mechanisms are used. Numerical results are presented to show the correctness of our model and finally, the efficiency of the proposed algorithm is compared with an exact algorithm, classic tabu search and simulated annealing. The obtained results prove the efficiency of the proposed algorithm.(c) 2022 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Engineering, Alexandria University. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/ 4.0/).