Developing dynamic maximal covering location problem considering capacitated facilities and solving it using hill climbing and genetic algorithm
Keywords:
maximal covering location problem, dynamic (multi-period) MCLP, capacitated MCLP, genetic algorithm, Hill climbing heuristicAbstract
The maximal covering location problem maximizes the total number of demands served within a maximal service distance given a fixed number of facilities or budget constraints. Most research papers have considered this maximal covering location problem in only one period of time. In a dynamic version of maximal covering location problems, finding an optimal location of P facilities in T periods is the main concern. In this paper, by considering the constraints on the minimum or maximum number of facilities in each period and imposing the capacity constraint, a dynamic maximal covering location problem is developed and two related models (A, B) are proposed. Thirty sample problems are generated randomly for testing each model. In addition, Lingo 8.0 is used to find exact solutions, and heuristic and meta-heuristic approaches, such as hill climbing and genetic algorithms, are employed to solve the proposed models. Lingo is able to determine the solution in a reasonable time only for small-size problems. In both models, hill climbing has a good ability to find the objective bound. In model A, the genetic algorithm is superior to hill climbing in terms of computational time. In model B, compared to the genetic algorithm, hill climbing achieves better results in a shorter time.Downloads
Published
Issue
Section
License
Engineering review uses the Creative Commons Attribution-NonCommercial-NoDerivatives (CC-BY-NC-ND) 4.0 International License, which governs the use, publishing and distribution of articles by authors, publishers and the wider general public.
The authors are allowed to post a digital file of the published article, or the link to the published article (Enginering Review web page) may be made publicly available on websites or repositories, such as the Author’s personal website, preprint servers, university networks or primary employer’s institutional websites, third party institutional or subject-based repositories, and conference websites that feature presentations by the Author(s) based on the published article, under the condition that the article is posted in its unaltered Engineering Review form, exclusively for non-commercial purposes.
The journal Engineering Review’s publishing procedure is performed in accordance with the publishing ethics statements, defined within the Publishing Ethics Resource Kit. The Ethics statement is available in the document Ethics Policies.