Solving Uncapacitated Facility Location Problem Using Heuristic Algorithms

Solving Uncapacitated Facility Location Problem Using Heuristic Algorithms

Soumen Atta (JIS University, Kolkata, India), Priya Ranjan Sinha Mahapatra (University of Kalyani, Kalyani, India) and Anirban Mukhopadhyay (Department of Computer Science and Engineering, University of Kalyani, Kalyani, India)
Copyright: © 2019 |Pages: 33
DOI: 10.4018/IJNCR.2019040102


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.
Article Preview

1. Introduction

The uncapacitated facility location problem (UFLP) is the problem of finding the optimal placement of facilities of unrestricted capacities among n potential facility locations such that the cost of satisfying demands of all the customers is minimized (Balinski, 1964; Erlenkotter, 1978; Krarup and Pruzan, 1983; Cornuéjols et al., 1983; Al-Sultan and Al-Fawzan, 1999; Sun, 2006; Atta et al., 2018a, 2018b). Here, cost is of two types: the service or connection cost to provide service to a customer by a facility and the opening cost to open a facility. UFLP is also known as the Simple Plant Location Problem (SPLP) (Krarup and Pruzan, 1983; Kratica et al., 2001), or the Warehouse Location Problem (WLP) (Khumawala, 1972). UFLP is known to be an NP-hard problem (Garey and Johnson, 1979; Lenstra and Kan, 1979). So, different heuristic approaches are used to solve this problem to obtain near-optimal solution. Some of the approaches are mentioned here. An efficient branch-and-bound algorithm for WLP was proposed by Akinc and Khumawala (1977). Bilde and Krarup (1977) provided sharp lower bounds for SPLP and also proposed a branch-and-bound algorithm to solve this problem. Al-Sultan and Al-Fawzan (1999) and Sun (2006) used tabu search algorithm for solving UFLP. Shmoys et al. (1997) first obtained the constant factor approximation algorithm for UFLP. Guha and Khuller (1999) combined a simple greedy heuristic algorithm with the algorithm of Shmoys et al. (1997) to obtain an approximation guarantee of 2.408 for UFLP. Approximation algorithms for metric UFLP are proposed in (Sviridenko, 2002; Byrka, 2007; Byrka and Aardal, 2010; Li, 2011; Chudak and Shmoys, 2003; Li, 2013; Mahdian et al., 2002). Neighborhood search-based heuristic was proposed by Ghosh (2003). Resende and Werneck (2006) proposed a hybrid multi-start heuristic to solve UFLP. The semi-Lagrangian relaxation approach was used to solve UFLP in (Beltran-Royo et al 2007). Message passing based heuristic algorithm for UFLP was proposed by Lazic et al (2010). Some large instances of SPLP were investigated by Letchford and Miller (2012). Monabbati (2014) solved UFLP using the method of surrogate semi-Lagrangian dual. Ardjmand et al. (2014) applied discrete version of Unconscious search (Ardjmand and Amin-Naseri 2012) to UFLP. A relatively new swarm intelligence-based technique known as the monkey algorithm is applied to UFLP by Atta et al (2018b). Over the years many variations of UFLP have been introduced by many researchers. Two-level UFLP has been extensively studied in (Tcha and Lee, 1984; Klose, 1999; Leung et al., 1994; Aardal et al., 1996; Klose, 2000; Zhang, 2006). The two-level UFLP with single assignment constraints has been studied by Gendron et al. (2016, 2017). Multi-level UFLP has been studied in (Aardal et al., 1999; Barros and Labbé, 1993; Kochetov and Goncharov, 2001; Kratica et al., 2014; Krishnaswamy and Sviridenko, 2016). A review on hierarchical UFLP can be found in (Şahin and Süral 2007). UFLP with penalties was studied by Xu and Xu (2005, 2009). Multi-objective UFLP for green logistics was proposed by Harris et al. (2009).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 8: 4 Issues (2019)
Volume 7: 4 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing