← Back to Publications List

Optimizing NP-Hard Problems: A Comparative Study of Metaheuristic Algorithms with Benchmark Performance Analysis

Students & Supervisors

Student Authors
Md. Maruf Hossain Munna
Bachelor of Science in Computer Science & Engineering, FST
Riazul Zannah
Bachelor of Science in Computer Science & Engineering, FST
Sajedul Islam
Bachelor of Science in Computer Science & Engineering, FST
Syeda Shakira Akter
Bachelor of Science in Computer Science & Engineering, FST
Supervisors
Md. Faruk Abdullah Al Sohan
Lecturer, Faculty, FST

Abstract

Metaheuristic algorithms play a key role in solving complex NP-hard optimization problems by offering scalable and efficient solutions. This study evaluates the performance of four popular metaheuristic algorithms: Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), and Ant Colony Optimization (ACO). These algorithms were tested on three NP-hard problems: Job Shop Scheduling Problem (JSSP), Vehicle Routing Problem (VRP), and Network Design Problem (NDP). Despite having different goals, these problems share common challenges such as resource allocation and conflict resolution. The algorithms were evaluated using profiling tools such as , gperftools, and Valgrind’s Callgrind. Metrics like execution time, memory usage, cache performance, and instruction count were analyzed. SA achieved the fastest execution and lowest resource use for JSSP. ACO performed best for VRP with fewer cache misses and fast performance. GA provided the best results for NDP with efficient instruction handling. TS delivered balanced results across all problems. These findings help in selecting the most suitable algorithm for specific optimization tasks in scheduling, transportation, and network systems.

Keywords

Metahuristic Algorithm NP-Hard Network Design Optimization Performance Evaluation

Publication Details

  • DOI: http://dx.doi.org/10.1007/978-3-031-98161-6_19
  • Type of Publication: Conference 
  • Conference Name: International Conference on Computational Intelligence in Engineering Science (ICCIES 2025)
  • Date of Conference: 23/07/2025 - 23/07/2025
  • Venue: Ton Duc Thang University No. 19, Nguyen Huu Tho Street, Tan Hung Ward, Ho Chi Minh City, Vietnam
  • Organizer: Ton Duc Thang University
View on Publisher