Genetic algorithm combined with variable neighborhood search to solve the one-to-one shortest path problem
Résumé
The shortest path problem (SPP) is widely applied in various fields of application such as trans-portation, telecommunication and computer networks. It aims at determining a path between twopoints with the minimum associated/allocated resource (distance, time, cost...) in a directed or un-directed graph. Several algorithms have been proposed to solve the standard SPP such as Dijkstra,Bellman-Ford. However, such approaches become less performant or even inapplicable when thesize of the network becomes very large or when additional constraints are added such as dynamicarcs weight, multi-criteria paths optimization. To address these issues, researchers have thoughtabout applying meta-heuristics to solve the standard SPP and its different variants. We introduce inthis paper a novel approach to solve the one-to-one version of SPP. Our method is based on a com-bination of Genetic Algorithm (GA) and Variable Neighborhood Search (VNS). We compare ourmethod with two exact algorithms Dijkstra and Integer Programming (IP). We made experimenta-tions using random generated, complete and real graph instances. In most case studies, numericalresults show that the average speed of our algorithm is 20-times faster than Dijkstra and more than1000-times compared to IP. While the algorithm of Dijkstra and the IP techniques provide optimalsolutions, the average gap to the optimality of our approximate approach is 5%.