Parallel Metaheuristic Approaches to Solve Combinatorial Optimization Problems

Abstract

The time complexity of many optimization problems falls under either exponential time or factorial time. Finding an optimal solution for such optimization problems is of great significance for scientific and engineering applications. Metaheuristic approaches have vast influence while solving optimization problems that provide satisfactory solutions in a reasonable amount of time. A metaheuristic is a guiding strategy to an underlying heuristic approach to solve a specific optimization problem. The metaheuristic approach helps determine an acceptable solution by applying constraints on the exploration space of feasible solutions. However, metaheuristics consume large amounts of CPU time while solving larger instances. Parallel computation reduces overall execution time by executing independent tasks simultaneously. Parallel computing enables faster convergence to solutions of large instances of optimization problems. Challenges facing designers implementing parallel strategies are - cost quality reduction in large problem instances, arriving at near-optimal solutions for a subset of input instances (but not all), large search-space exploration to reach a satisfactory solution. In this thesis work, efficient parallel metaheuristic models are developed that resolve some of the issues mentioned above. Further, satisfactory solutions are arrived at in a reasonable amount of time. The proposed parallel versions of metaheuristics have been applied to three combinatorial optimization problems: traveling salesman problem, minimum latency problem, and vehicle routing problem. The Traveling Salesman Problem (TSP) is an NP-hard combinatorial optimization problem. Metaheuristic methods are used to produce the satisfactory solution by limiting the search-space exploration. Moreover, CPU implementations of metaheuristic methods are too time-consuming for large input instances. The GPU-based Parallel Iterative Hill Climbing (PIHC) approach is presented for solving large TSPLIB instances in a reasonable time. Multiple GPU-based thread mapping strategies have been presented to solve large-scale TSPLIB instances. The improved cost quality has been demonstrated using the symmetric TSPLIB instances having up to 85,900 cities. The PIHC GPU implementation gives up to 193 speedup over its sequential counterpart and up to 979.96 speedup over a state-of-the-art GPU-based TSP solver. The PIHC gives a cost quality with error rate 0.72% in the best case and 8.06% in the worst case. Moreover, two GPU-based parallel strategies have been developed for ant colony algorithm to solve larger instances than existing approaches. The Minimum Latency Problem (MLP) is an NP-Hard combinatorial optimization problem. Metaheuristics use perturbation and randomization to arrive at a satisfactory solution under time constraints. The proposed work uses Deterministic Local Search Heuristic (DLSH) to identify a satisfactory solution without setting up metaheuristic parameters. A move evaluation procedure is proposed for the swap approach which computes a move in a constant time. A GPU-based Parallel Deterministic Local Search Heuristic (PDLSH) is proposed to mitigate the execution time spent in the solution improvement phase. The PDLSH parallelizes the solution improvement phase and solves MLP for larger instances than the state-of-the-art. The DLSH and PDLSH implementations are tested on the TRP and TSPLIB standard instances. DLSH reaches new best solutions for five TSPLIB instances, namely eil51, berlin52, pr107, rat195, and pr226. The proposed PDLSH achieves a speedup of up to 179.75 for the instances of size 10- 11849 nodes compared to its sequential counterpart. The Vehicle Routing Problem (VRP) is an NP-hard, goods transportation scheduling problem with vehicle capacity and transportation cost constraints. This work presents GPU-based parallel strategies for the Local Search Heuristic (LSH) algorithm to solve the large-scale Capacitated Vehicle Routing Problem (CVRP) instances. This work employs a combination of five improvement heuristic approaches to improve the constructed feasible solution. It is noticed that a large amount of CPU time is spent in the feasible solution improvement phase. Two GPU-based parallel strategies, namely, route level and customer level parallel designs, have been developed to reduce the execution time of solution improvement phase. The proposed parallel version of the LSH has been tested on large-scale instances of up to 30000 customers. The customer level parallel design offers speedup up to 147:19 compared to the corresponding sequential version. From this thesis work, the proposed parallel version of IHC solves larger TSPLIB ii instances up to 85900 cities with a speedup of up to 193 times. Also, it reduces error rates of local solutions, i.e., in the range of 0.72% - 8.06%. The limitation of existing GPU-based MLP solver has been overcome in the proposed GPU-based parallel strategy to solve instances above 1000 nodes. PDLSH significantly mitigates the overall execution time while solving MLP, which achieves a speedup of 179 over its sequential counterpart for instances up to 11849 nodes. In the case of CVRP, two parallel strategies, namely route-level and customer-level, are developed to reduce execution time spent in the improvement phase. The customer-level parallel design reduces the execution time significantly and generates the speedup up to 147 for the instances having up to 30000 nodes.