A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem

The purpose of this paper is to present a new metaheuristic, termed the backtracking adaptive threshold accepting algorithm, for solving the heterogeneous fixed fleet vehicle routing problem (HFFVRP). The HFFVRP is a variant of the classical vehicle routing problem (VRP) and has attracted much less attention in the operational research (OR) literature than the classical VRP. It involves the design of a set of minimum cost routes, originating and terminating at a depot, for a fleet with fixed number of vehicles of each type, with various capacities, and variable costs to service a set of customers with known demands. The numerical results show that the proposed algorithm is robust and efficient. New best solutions are reported over a set of published benchmark problems. (C) 2002 Elsevier B.V. All rights reserved.