The Vehicle Routing Problem with Time Windows Based on Agent Travel Time: An Exploration of Genetic Algorithm Reproduction Schemes

The Vehicle Routing Problem with Time Windows (VRPTW) is a critical combinatorial optimization problem in modern logistics, where finding optimal routes is essential for minimizing operational costs and enhancing service reliability. While Genetic Algorithms (GAs) are a powerful tool for solving VRPTW, their effectiveness is often undermined by premature convergence, a phenomenon in which the algorithm stagnates at suboptimal solutions, thus failing to achieve maximum efficiency. This study directly addresses this challenge by systematically evaluating how different reproduction schemes impact GA performance. The primary objective is to identify operator combinations that mitigate premature convergence to achieve superior solution quality, measured by total travel time, while also analyzing the trade-off with computational cost. We investigate combinations of conventional operators, such as Tournament Selection (TS) and Order Crossover (OX), against more advanced schemes, including Split Rank Selection (SRS) and Multi-Parent Order Crossover (MPOX), as well as different mutation methods, namely Scramble Mutation (SM) and Inversion Mutation (IM). Results demonstrate that advanced schemes, particularly the combination of SRS, MPOX, and IM, yield the most robust convergence and the lowest average total travel time of 48,422.8 minutes. However, this superior performance requires the longest computation time at 30.9 h. In contrast, conventional operator combinations are significantly faster, with execution times as low as 8.7 h, but they produce lower-quality solutions and exhibit unstable convergence. This study highlights the crucial role of the reproduction scheme in balancing the trade-off between solution quality and computational efficiency, confirming that a synergistic combination of advanced operators is essential for solving complex VRPTW instances effectively.