A Hybrid Ant Colony System for the Heterogeneous Fixed Fleet Vehicle Routing Problem

One of the most significant extension problems of the Vehicle Routing Problem (VRP) is the Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP), which aims to provide a service to a specific customer group using a limited number of vehicles. This is vital in ensuring a business can meet customer demand while simultaneously maximizing its profits. The HFFVRP is concerned with determinations of the minimum cost routes for a fleet of vehicles in order to satisfy the demand of the customer population. The fleet composition consists of various types of vehicles, which differ with respect to their maximum carrying load and variable cost per distance unit. This paper proposes a hybrid metaheuristic algorithm based on the Ant Colony System (ACS) for solving the HFFVRP, in which two local search algorithms are used as improvement methods. The proposed algorithm is tested on 13 standard instances involving from 50 to 360 customers from the literature. The computational result shows that the ACS results are competitive with other metaheuristic algorithms results for solving the HFFVRP. In addition, the proposed algorithm finds closely the best known solutions for most of the instances in which six best known solutions are also found.