1. Solving a new variant of the capacitated maximal covering location problem with fuzzy coverage area using metaheuristic approachesAnirban Mukhopadhyay, Priya Ranjan Sinha Mahapatra, Soumen Atta, 2022, original scientific article Abstract: The Maximal Covering Location Problem (MCLP) is concerned with the optimal placement of a fixed number of facilities to cover the maximum number of customers. This article considers a new variant of MCLP where both the coverage radii of facilities and the distance between customer and facility are fuzzy. Moreover, the finite capacity of each facility is considered. We call this problem the capacitated MCLP with fuzzy coverage area (FCMCLP), and it is formulated as a 0–1 linear programming problem. In this article, two classical metaheuristics: particle swarm optimization, differential evolution, and two new-generation metaheuristics: artificial bee colony algorithm, firefly algorithm, are proposed for solving FCMCLP. Each of the customized metaheuristics utilizes a greedy deterministic heuristic to generate their initial populations. They also incorporate a local neighborhood search to improve their convergence rates. New instances of FCMCLP are generated from the traditional MCLP instances available in the literature, and IBM’s CPLEX solver is used to generate benchmark solutions. An experimental comparative study among the four customized metaheuristics is described in this article. The performances of the proposed metaheuristics are also compared with the benchmark solutions obtained from CPLEX.
Found in: osebi
Keywords: Facility Location Problem (FLP), Fuzzy Capacitated Maximal Covering Location Problem (FCMCLP), Particle Swarm Optimization (PSO), Differential Evolution (DE), Artificial Bee Colony (ABC), Firefly Algorithm (FA)
Published: 08.03.2023; Views: 294; Downloads: 0
 Fulltext (2,21 MB) |
2. A multi-objective formulation of maximal covering location problem with customers’ preferences: Exploring Pareto optimality-based solutionsAnirban Mukhopadhyay, Priya Ranjan Sinha Mahapatra, Soumen Atta, 2021, original scientific article Abstract: The maximal covering location problem (MCLP) is a well-known combinatorial optimization problem with several applications in emergency and military services as well as in public services. Traditionally, MCLP is a single objective problem where the objective is to maximize the sum of the demands of customers which are served by a fixed number of open facilities. In this article, a multi-objective MCLP is proposed where each customer has a preference for each facility. The multi-objective MCLP with customers’ preferences (MOMCLPCP) deals with the opening of a fixed number of facilities from a given set of potential facility locations and then customers are assigned to these opened facilities such that both (i) the sum of the demands of customers and (ii) the sum of the preferences of the customers covered by these opened facilities are maximized. A Pareto-based multi-objective harmony search algorithm (MOHSA), which utilizes a harmony refinement strategy for faster convergence, is proposed to solve MOMCLPCP. The proposed MOHSA is terminated based on the stabilization of the density of non-dominated solutions. For experimental purposes, 82 new test instances of MOMCLPCP are generated from the existing single objective MCLP benchmark data sets. The performance of the proposed MOHSA is compared with the well-known non-dominated sorting genetic algorithm II (NSGA-II), and it has been observed that the proposed MOHSA always outperforms NSGA-II in terms of computation time. Moreover, statistical tests show that the objective values obtained from both algorithms are comparable.
Found in: osebi
Keywords: Maximal covering location problem (MCLP), Multi-objective MCLP, Customers’ preferences, Multi-objective harmony search algorithm (MOHSA), NSGA II, CPLEX
Published: 17.04.2023; Views: 102; Downloads: 0
Fulltext (1,43 MB) |
3. L (D, 2, 1)-labeling of Square GridPriya Ranjan Sinha Mahapatra, Soumen Atta, 2019, original scientific article Abstract: For a fixed integer $D (\geq 3)$ and $\lambda$ $\in$ $\mathbb{Z}^+$, a $\lambda$-$L(D, 2, 1)$-$labeling$ of a graph $G = (V, E)$ is the problem of assigning non-negative integers (known as labels) from the set $\{0, \ldots, \lambda\}$ to the vertices of $G$ such that if any two vertices in $V$ are one, two and three distance apart from each other then the assigned labels to these vertices must have a difference of at least $D$, 2 and 1 respectively. The vertices which are at least $4$ distance apart can receive the same label. The minimum value among all the possible values of $\lambda$ for which there exists a $\lambda$-$L(D, 2, 1)$-$labeling$ is known as the labeling number. In this paper $\lambda$-$L(D, 2 ,1)$-$labeling$ of square grid is considered. The lower bound on the labeling number for square grid is presented and a formula for $\lambda$-$L(D, 2 ,1)$-$labeling$ of square grid is proposed. The correctness proof of the proposed formula is given here. The upper bound of the labeling number obtained from the proposed labeling formula for square grid matches exactly with the lower bound of the labeling number.
Found in: osebi
Keywords: Graph labeling, Square grid, Labeling number, Frequency assignment problem (FAP)
Published: 17.04.2023; Views: 88; Downloads: 0
Fulltext (304,64 KB) |
4. Multi-objective uncapacitated facility location problem with customers’ preferences: Pareto-based and weighted sum GA-based approachesAnirban Mukhopadhyay, Priya Ranjan Sinha Mahapatra, Soumen Atta, 2019, original scientific article Abstract: The uncapacitated facility location problem (UFLP) is a well-known combinatorial optimization problem having single-objective function. The objective of UFLP is to find a subset of facilities from a given set of potential facility locations such that the sum of the opening costs of the opened facilities and the service cost to serve all the customers is minimized. In traditional UFLP, customers are served by their nearest facilities. In this article, we have proposed a multi-objective UFLP where each customer has a preference for each facility. Hence, the objective of the multi-objective UFLP with customers’ preferences (MOUFLPCP) is to open a subset of facilities to serve all the customers such that the sum of the opening cost and service cost is minimized and the sum of the preferences is maximized. In this article, the elitist non-dominated sorting genetic algorithm II (NSGA-II), a popular Pareto-based GA, is employed to solve this problem. Moreover, a weighted sum genetic algorithm (WSGA)-based approach is proposed to solve MOUFLPCP where conflicting two objectives of the problem are aggregated to a single quality measure. For experimental purposes, new test instances of MOUFLPCP are created from the existing UFLP benchmark instances and the experimental results obtained using NSGA-II and WSGA-based approaches are demonstrated and compared for these newly created test instances.
Found in: osebi
Keywords: Uncapacitated facility location problem (UFLP), Multi-objective UFLP with customers’ preferences (MOUFLPCP), NSGA-II, Weighted sum genetic algorithm (WSGA)
Published: 17.04.2023; Views: 95; Downloads: 0
Fulltext (534,37 KB) |
5. Population-based improvement heuristic with local search for single-row facility layout problemPriya Ranjan Sinha Mahapatra, Soumen Atta, 2019, original scientific article Abstract: The Single-Row Facility Layout Problem (SRFLP) is a well-known combinatorial optimization problem. The objective of SRFLP is to find out the arrangement of facilities with given lengths on a line so that the weighted sum of the distances between all pairs of facilities is minimized. This problem is known to be NP-hard. Hence, a population-based improvement heuristic algorithm with local search is presented in this article to solve SRFLP. The proposed algorithm works well also for the Single-Row Equidistant Facility Layout Problem (SREFLP), where the length of each facility is equal. The computational efficiency of the proposed algorithm is checked with the instances of sizes ranging from 5 to 300 available in the literature for SRFLP and SREFLP. The obtained results are compared to those from different state-of-the-art algorithms. The proposed algorithm achieves best known solutions to date for every instance considered in this article in reasonable computational time.
Found in: osebi
Keywords: Single-row facility layout problem (SRFLP), single-row equidistant facility layout problem (SREFLP), population-based heuristic, improvement heuristic, local search
Published: 17.04.2023; Views: 142; Downloads: 0
Fulltext (1,43 MB) |
6. Solving tool indexing problem using harmony search algorithm with harmony refinementAnirban Mukhopadhyay, Priya Ranjan Sinha Mahapatra, Soumen Atta, 2019, original scientific article Abstract: The tool indexing problem (TIP) is the problem of allocating cutting tools to different slots in a tool magazine of Computer Numerically Controlled machine to reduce the processing time of jobs on the machine. This is one of the mostly encountered optimization problems in manufacturing systems. In TIP, the number of tools used by the machine is at most the number of slots available in the tool magazine. In this article, a customized harmony search (HS) algorithm, which utilizes a harmony refinement strategy for faster convergence, is presented to solve TIP. The harmony refinement method also helps to avoid getting stuck into local optima. The performance of the proposed method is tested on 27 instances taken from the literature and out of these it is found to improve the best known solutions for 16 instances. For the remaining instances, it gives the same results as found in the literature. Moreover, the performance of the proposed algorithm is tested on newly adapted 41 instances and for some of these instances the results obtained using the proposed algorithm are compared with that obtained using CPLEX.
Found in: osebi
Keywords: Tool indexing problem (TIP), Computer Numerically Controlled (CNC) machine, Harmony search (HS) algorithm, Automatic tool changer (ATC), CPLEX
Published: 17.04.2023; Views: 95; Downloads: 0
Fulltext (974,57 KB) |
7. Solving uncapacitated facility location problem using heuristic algorithmsAnirban Mukhopadhyay, Priya Ranjan Sinha Mahapatra, Soumen Atta, 2019, original scientific article Abstract: A well-known combinatorial optimization problem, known as the uncapacitated facility location problem (UFLP) is considered in this article. A deterministic heuristic algorithm and a randomized heuristic algorithm are presented to solve UFLP. Though the proposed deterministic heuristic algorithm is very simple, it produces good solution for each instance of UFLP considered in this article. The main purpose of this article is to process all the data sets of UFLP available in the literature using a single algorithm. The proposed two algorithms are applied on these test instances of UFLP to determine their effectiveness. Here, the solution obtained from the proposed randomized algorithm is at least as good as the solution produced by the proposed deterministic algorithm. Hence, the proposed deterministic algorithm gives upper bound on the solution produced by the randomized algorithm. Although the proposed deterministic algorithm gives optimal results for most of the instances of UFLP, the randomized algorithm achieves optimal results for all the instances of UFLP considered in this article including those for which the deterministic algorithm fails to achieve the optimal solutions.
Found in: osebi
Keywords: Uncapacitated Facility Location Problem (UFLP), Simple Plant Location Problem (SPLP), Warehouse Location Problem (WLP), Heuristics, Randomization
Published: 17.04.2023; Views: 102; Downloads: 0
Fulltext (2,29 MB) |
8. Solving maximal covering location problem using genetic algorithm with local refinementAnirban Mukhopadhyay, Priya Ranjan Sinha Mahapatra, Soumen Atta, 2018, original scientific article Abstract: The maximal covering location problem (MCLP) deals with the problem of finding an optimal placement of a given number of facilities within a set of customers. Each customer has a specific demand and the facilities are to be placed in such a way that the total demand of the customers served by the facilities is maximized. In this article an improved genetic algorithm (GA)-based approach, which utilizes a local refinement strategy for faster convergence, is proposed to solve MCLP. The proposed algorithm is applied on several MCLP instances from literature and it is demonstrated that the proposed GA with local refinement gives better results in terms of percentage of coverage and computation time to find the solutions in almost all the cases. The proposed GA-based approach with local refinement is also found to outperform the other existing methods for most of the small as well as large instances of MCLP.
Found in: osebi
Keywords: Facility location problem, Covering location problem, Maximal covering location problem (MCLP), Genetic algorithm (GA), Local refinement
Published: 17.04.2023; Views: 95; Downloads: 0
Fulltext (835,25 KB) |
9. Perturbation-minimising frequency assignment to address short term demand fluctuation in cellular networkPriya Ranjan Sinha Mahapatra, Soumen Atta, 2018, original scientific article Abstract: In cellular network short term demand fluctuation is a very common phenomenon. The demand of any cell may increase or decrease slightly or the system may expand by adding additional cells or the system may shrink if the demands of certain number of cells become zero. In this paper, the perturbation-minimising frequency assignment problem (PMFAP) is considered to address the short term fluctuation in demand vector. PMFAP is a frequency assignment problem in which newly generated demands are satisfied with minimum changes in the already existing frequency assignment keeping all the interference constraints. In this paper, an efficient heuristic algorithm for PMFAP is presented. The efficiency of this algorithm is compared with the existing results from literature. With a slight modification to the proposed algorithm, it can solve the well-known frequency assignment problem (FAP) and its performance is also compared with the existing results using the standard benchmark data sets for FAP.
Found in: osebi
Keywords: short term demand fluctuation, frequency assignment problem, FAP, PMFAP, cellular network, perturbation, heuristic algorithm
Published: 17.04.2023; Views: 116; Downloads: 0
Fulltext (951,77 KB) |
10. Deterministic and randomized heuristic algorithms for uncapacitated facility location problemAnirban Mukhopadhyay, Priya Ranjan Sinha Mahapatra, Soumen Atta, 2018, published scientific conference contribution Abstract: A well-known combinatorial optimization problem, known as the Uncapacitated Facility Location Problem (UFLP) is considered in this paper. Given a set of customers and a set of potential facilities, the objective of UFLP is to open a subset of the potential facilities such that sum of the opening cost for opened facilities and the service cost of customers is minimized. In this paper, deterministic and randomized heuristic algorithms are presented to solve UFLP. The effectivenesses of the proposed algorithms are tested on UFLP instances taken from the OR-Library. Although the proposed deterministic algorithm gives optimal results for most of the instances, the randomized algorithm achieves optimal results for all the instances of UFLP considered in this paper including those for which the deterministic algorithm fails to achieve the optimal solutions.
Found in: osebi
Keywords: Uncapacitated facility location problem (UFLP), Simple plant location problem (SPLP), Warehouse location problem (WLP), Heuristics Randomization
Published: 17.04.2023; Views: 118; Downloads: 0
Fulltext (191,27 KB) |
