MultiPath Island-Based Genetic Algorithm for the K-Most Diverse Near-Shortest Paths

This is the authors' abstract. We don't add key points for this paper.

Modern routing applications, such as those used for vehicle navigation and emergency response routing, often require access to multiple optimal paths/routes rather than relying on a single optimal solution. However, existing methods typically struggle to balance optimality and diversity within the paths they generate. To address this challenge, we introduce the MultiPath Island-Based Genetic Algorithm (MIBGA) for solving the K-Most Diverse Near-Shortest Paths (KMDNSP) problem, with an emphasis on promoting both path diversity and computation of near-optimal paths. MIBGA is a Parallel Genetic Algorithm (PGA) based on the island model, and our approach incorporates novel migration and selection strategies that preserve diversity across subpopulations of path solutions. Experimental results on large, complex real-world road networks from Arizona, Washington, and Kansas demonstrate MIBGAs superior performance in terms of solution diversity, computational efficiency, and convergence speed compared to other well-established Genetic Algorithm (GA) based approaches. The results of our work further highlight the potential of GAs for addressing complex alternate routing problems in practical real-world settings. • MultiPath Island-Based Genetic Algorithm for diverse alternate routes. • K-Most Diverse Near-Shortest Paths, emphasising diversity and near-optimality. • Novel migration and selection strategies for Island-Based Genetic Algorithms. • Data repository with 3 real-world road networks in edge list format and code.