Hybrid Algorithms for Energy Minimizing Vehicle Routing Problem: Integrating Clusterization and Ant Colony Optimization

Abstract

In the field of engineering, complex problems often arise that require solutions. The implementation of these algorithms plays a crucial role in achieving favorable outcomes with the available resources. The Vehicle Routing Problem (VRP) has been a central topic in distribution and logistics for decades. New VRP models and tools are developed to address the challenges of modern logistics. The Energy Minimizing Vehicle Routing Problem (EMVRP) is a “green”-oriented variant of the VRP where the objective is to minimize the total amount of energy consumed by a fleet of vehicles. The VRP literature has focused on solving the problem using a variety of approaches and techniques, including exact methods, heuristics, metaheuristics, and hybrid algorithms. Hybrid algorithms combine different techniques to obtain more effective and better solutions. This work presents four innovative hybrid algorithms to address the EMVRP problem. These algorithms combine Machine Learning (ML) clustering techniques with metaheuristic approaches inspired by an Ant Colony Optimization (ACO). The proposed algorithms are: Free Ant + K-Means, Free Ant + K-Medoids, Restricted Ant + K-Means, and Restricted Ant + K-Medoids. Each of them combines the benefits of clustering with the optimization capacity of ACO. Proposed algorithms were subjected to testing using instances from CVRPLIB. Both Free Ant and Restricted Ant efficiently solved EMVRP problems. The results obtained were analyzed and compared with the proposals of other authors in the literature. Overall, the results are promising, but they also indicate a significant scope for experimentation and parameter tuning of the proposed algorithms.

Keywords

• Complex problems
• free ant
• green-vrp
• heuristics
• k-means
• k-medoids