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