zbMATH — the first resource for mathematics

A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. (English) Zbl 1088.90536
Summary: In real life situations most companies that deliver or collect goods own a heterogeneous fleet of vehicles. Their goal is to find a set of vehicle routes, each starting and ending at a depot, making the best possible use of the given vehicle fleet such that total cost is minimized. The specific problem can be formulated as the Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP), which is a variant of the classical Vehicle Routing Problem. This paper describes a variant of the threshold accepting heuristic for the HFFVRP. The proposed metaheuristic has a remarkably simple structure, it is lean and parsimonious and it produces high quality solutions over a set of published benchmark instances. Improvement over several of previous best solutions also demonstrates the capabilities of the method and is encouraging for further research.

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management
Full Text: DOI