مشخصات پژوهش

عنوان	A new formulation and algorithm for the maximum leaf spanning tree problem with an application in forest fire detection
نوع پژوهش	مقاله چاپ‌شده در مجلات علمی
کلیدواژه‌ها	Maximum leaf spanning tree; network flow; genetic algorithm; forest fire detection; wireless sensor network
چکیده	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.
پژوهشگران	عیسی نخعی کمال آبادی (نفر سوم)، حمید فرورش (نفر دوم)، امیرمسعود حسینمردی (نفر اول)