Conference Papers
Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/123456789/28506
Browse
3 results
Search Results
Item Near Optimal Solution for Traveling Salesman Problem using GPU(Institute of Electrical and Electronics Engineers Inc., 2018) Yelmewad, P.; Talawar, B.Traveling Salesman Problem (TSP) is an NP-complete, a combinatorial optimization problem. Finding an optimal solution is intractable due to its time complexity. Therefore, approximation approaches have great importance which gives a good quality solution in a reasonable time. This paper presents the importance of constructing the initial solution using construction heuristic rather than setting up arbitrarily. Proposed GPU based Parallel Iterative Hill Climbing (PIHC) algorithm solves large TSPLIB instances. We demonstrate the efficiency of PIHC approach with the state-of-the-art approximation based and GPU based TSP solvers. PIHC produces 181× speedup over its sequential counterpart and 251× over the state-of-the-art GPU based TSP solver. Moreover, PIHC receives a better cost quality than the state-of-the-art GPU based TSP solvers which has gap rate in range of 0.72 % - 8.06%. © 2018 IEEE.Item MMAS on GPU for Large TSP Instances(Institute of Electrical and Electronics Engineers Inc., 2019) Yelmewad, P.; Kumar, A.; Talawar, B.This paper presents a GPU-based Ant Colony Optimization (ACO) algorithm to solve the large-size Traveling Salesman Problem (TSP). The aim of this study is to provide an effective and efficient GPU-based parallel strategy for the ACO algorithm to solve larger size TSPLIB instances in a reasonable time, preserving its solution quality. Till the date, all GPU-based parallel implementations of the ACO algorithm is only available for TSPLIB instances up to 2392 cities. We have studied the limiting factors of the existing GPU implementations to solve larger instances and designed the parallel model which solves TSPLIB instances up to 33810 cities. Our parallel approach receives speedup up to 60× over its sequential counterpart. In terms of solution quality, our parallel ACO produces the local optimal solution which has error rates in range of 0.52% - 4.97% compared to the optimal solution. © 2019 IEEE.Item GPU-based Parallel Heuristics for Capacited Vehicle Routing Problem(Institute of Electrical and Electronics Engineers Inc., 2020) Yelmewad, P.; Talawar, B.This paper presents the novel GPU-based parallel strategy for the heuristic algorithms to solve the large-scale Capacited Vehicle Routing Problem (CVRP). A combination of five improvement heuristic approaches has been used to improve the constructed feasible solution. It is noticed that a large amount of CPU time is spent in the solution improvement phase while improving a feasible solution. We aim to discover an independent part of the improvement heuristic approaches and make it run over the GPU platform simultaneously. The proposed parallel version has been tested on large-scale instances of up to 20000 customers. The parallel version offers speedup up to 176.12 × compared to the corresponding sequential version. © 2020 IEEE.