Comparison of NSGA-II and Ant Colony Optimization for Solving the Multiobjective Vehicle Routing Problem with Flexible Time Windows

Abstract

Vehicle routing problems are widely encountered in real-world applications. This paper addresses a specific variant known as the Vehicle Routing Problem with Flexible Time Windows (VRPFlexTW), where solutions must comply with constraints, including travel, service, and waiting times, along with time-window restrictions. We propose the Nondominated Sorting Genetic Algorithm II (NSGA-II) and detail its components. Additionally, we provide a computational comparison between NSGA-II and the Ant Colony Optimizer (ACO) for several instances of VRPFlexTW. This comparison aims to evaluate the efficiency and performance of these approaches in solving this complex problem. Finally, the experimental results demonstrate that NSGA-II significantly improves solution quality and reduces the optimal fleet size, establishing it as the most effective algorithm among those presented. The results reveal that the NSGA-II algorithm consistently outperforms ACO and ALNS across all tested client configurations. NSGA-II achieves the lowest cost function values, demonstrating superior cost optimization by significantly reducing the total routing costs compared to ACO and ALNS