A parallel genetic algorithm for multi-criteria path routing on complex real-world road networks

A Parallel Genetic Algorithm (PGA) specifically designed for multi-criteria vehicle routing is described in this work. The algorithm aims to enhance the existing routing methods by offering users the ability to choose their preferred path from a set of optimal paths optimised on multiple objectives. The objectives are optimised using a novel fitness metric that prioritises minimising path length while also maximising access to specific amenities such as pubs, hotels, and charging stations. The developed approach, called Parallel Optimal-route Search (POS), follows a hybrid model using both global parallelisation and island-based approaches. A Loop-Free Path-Composer (LFPC) is described and this genetic operator generates new paths for evaluation and is shown to yield a more diverse set of solutions in contrast to other commonly used approaches, such as Node Based Crossover and Path Mutation (NBCPM). Our approach is validated on highly complex, large-scale real-world road networks, with sizes ranging from 3,000 and 10,000 nodes. We present a systematic study comparing the performance of our proposed LFPC operator against the traditional NBCPM operators. Additionally, we evaluate the effectiveness of our proposed POS algorithm in comparison to the well-known Non-dominated Sorting Genetic Algorithm II and III.