An Ant Colony Algorithm Approach to the Vehicle Routing Problem and Variants

In the basic vehicle routing problem (VRP), a vehicle must deliver goods from one centralized warehouse to multiple customers efficiently. Several VRP variants and constraints exist, including different product types, specific delivery times, multiple warehouses, vehicle fuel constraints, and pick-up from one location and delivery to another. This work proposes and demonstrates a flexible algorithm for solving the VRP via ant colony optimization (ACO) that can address many of the variants discussed above. ACO algorithms mimic the behavior of ants, learning optimal paths to a food source and back to the nest based on stigmergic behavior. This work compares a proposed, more flexible ACO algorithm to a traditional optimization algorithm that is implemented in the Google VRP solver. Readily available data were used to test and demonstrate results. Several VRP variants were implemented in both the (proposed) flexible ACO algorithm and the Google VRP solver. The flexible ACO algorithm performed better in terms of distance traveled versus the Google VRP solver for two variants and worse for three other cases. However, the Google VRP solver was not able to solve some of the VRP variant combinations considered here and failed when solving some backhaul datasets. Because the flexible ACO algorithm was able to better handle many case variations, it may be an attractive alternative optimization tool.