2024 : 5 : 13
Hamid Farvaresh

Hamid Farvaresh

Academic rank: Associate Professor
ORCID: 0000-0002-9979-7712
Education: PhD.
ScopusId: 36124788700
Faculty: Faculty of Engineering
Address: Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran.
Phone: +988733624019

Research

Title
A new formulation and algorithm for the maximum leaf spanning tree problem with an application in forest fire detection
Type
JournalPaper
Keywords
Maximum leaf spanning tree; network flow; genetic algorithm; forest fire detection; wireless sensor network
Year
2023
Journal Engineering Optimization
DOI
Researchers Amir Masoud Hosseinmardi ، Hamid Farvaresh ، Isa Nakhai Kamalabadi

Abstract

This article proposes a new formulation for the maximum leaf spanning tree problem (MLSTP) using network flow concepts to ensure the graph connectivity of the problem’s solutions. Since the MLSTP is NP hard, the MLSTP genetic algorithm (MGA) is also developed to solve large-scale instances. The proposed formulation optimally solved 37 out of 41 instances of existing benchmarks, comparable with results of the available formulations in the literature. MGA solved all of the existing benchmarks in less than 1 min without a significant optimality gap. MGA also found qualified solutions for large-scale instances of up to 2000 vertices in a reasonable time. As a realistic application of MLSTP, a forest fire detection system was developed and successfully simulated for the Iranian Arasbaran forest using a wireless sensor network (WSN). The proposed formulation was used to find the optimal topology of the WSN responsible for the early detection and timely warning of fires in Arasbaran.