An Optimized OpenMP-Based Genetic Algorithm Solution to Vehicle Routing Problem

摘要

Vehicle routing problem is an interesting combinatoric research problem of NP-complete class for investigation. Many researchers in the past have targeted this interesting combinatorial problem with a number of methodologies. The classic methods like brute-force approach, dynamic programming, and integer linear programming methods were used in earlier attempts to find the most optimized route for a vehicle. However, these methods met their computational limitation for a large number of coverage points. Owing to the exhaustive evaluation for the number of routes, the genetic algorithm-based heuristic approach was proposed to find accurate approximate solutions. The method involves solving a traveling salesman problem (TSP) using the genetic algorithm approach for a large number of route combinations which were very high. This research document proposes a solution to this by using the multi-core architecture, where it has been shown that implementing GA as heuristic approach for a large solution space is not sufficient. A contrast has been shown between the serial and parallel implementation of the solution using OpenMP multi-processing architecture which shows a considerable speedup for the execution time of the algorithm to search the best path. For a varied degree of graph structures, this implementation has highly reduced execution time.