A multidimensional fitness function based heuristic algorithm for set covering problems

Ahmad Hashemi

doi:10.1016/j.asoc.2025.113038

A multidimensional fitness function based heuristic algorithm for set covering problems

2025-04-01

0

PRE

AI

DOI：10.1016/j.asoc.2025.113038

Original

Original request for help

Save

Abstract

En 中文

The set covering problem (SCP) is a conventional integer programming challenge in combinatorial optimization, with applications spanning fields such as transportation, logistics, and location problems. Solving SCPs efficiently is crucial for optimizing operations in these domains, particularly in location problems, where traditional algorithms often struggle with multidimensional objective spaces. To address such challenges, this study proposes a novel problem-dependent heuristic algorithm to solve SCPs, featuring a new multi-dimensional fitness function, which was evaluated by benchmarking against other heuristic and metaheuristic algorithms. A collection of reproduced and selected OR-library problems of various scales were chosen as benchmark instances to assess the performance of the algorithm. The performance of the algorithm was confirmed as it constructs solutions by leveraging a novel fitness function to address the limitations of time complexity, applicability, and scalability. Computational results demonstrate that the developed algorithm offers competitive solutions for SCPs, showing improvements of up to 88 % and 20 % in terms of time compared to simulated annealing and a preliminary heuristic algorithm, respectively. In terms of quality, the developed algorithm achieved cost reductions of up to 21 % and 11 % compared to these algorithms, respectively.

Keywords:

Heuristics

Set covering problems

Polynomial-time

Fitness function

Multidimensional

Optimization

A multidimensional fitness function based heuristic algorithm for set covering problems

Abstract

Journal

Organization