A Two-Phase Distributed Ruin-and-Recreate Genetic Algorithm for Solving the Vehicle Routing Problem With Time Windows

Abstract

Developing an algorithm that can solve the vehicle routing problem with time windows (VRPTW) and create near-optimal solutions with the least difference in magnitude is a challenging task. This task is evident from the fact that when an algorithm runs multiple times based on a given instance, the generated solutions deviate from each other and may not near-optimal. For this reason, an algorithm that can solve these problems is effective and highly sought after. This paper proposes a novel systematic framework using a two-phase distributed ruin-and-recreate genetic algorithm (RRGA). The two-phase consists of the RRGA phase and ruin-and-recreate (RR) phase, which is designed to run in the distributed computing environment that leveraging these networked resources. This combination of algorithms harnesses the strength of the search diversification and intensification, thereby producing very high-quality solutions. Experiments with Solomon’s benchmark show the RRGA can produce results superior to the recently published hybrid algorithms, best-known solutions, and nine leading hybrid algorithms.