Solving Multifacility Huff Location Models on Networks Using Variable Neighborhood Search and Multi-Start Local Search Metaheuristics

Solving Multifacility Huff Location Models on Networks Using Variable Neighborhood Search and Multi-Start Local Search Metaheuristics Sanja Roksandi´ca,1Emilio Carrizosa b,2Dragan Uroˇsevi´ca,3 Nenad Mladenovi´cc,4 aMathematical Institute, Serbian Academy of Sciences and Arts, Belgrade, Serbia bFaculty of Mathematics, University of Seville, Seville, Spain cDepartment of Mathematics, SISCM, Brunel University, London, UK Abstract We consider multifacility Huff location problems on networks. The mixed integer nonlinear optimization problem is solved using Variable Neighborhood Search and Multi-Start Local Search metaheuristics. Computational experience is reported. Keywords: network, facility location, Huff model, variable neighborhood search, multi-start local search, global optimization. 1 Introduction Location optimization problems on a network in a competitive environment have been extensively studied in OR. The problem was first presented by 1Email: [email protected] 2Email: [email protected] 3Email: [email protected] 4Email: [email protected] Available online at www.sciencedirect.com Electronic Notes in Discrete Mathematics 39 (2012) 121–128 1571-0653/$ – see front matter © 2012 Elsevier B.V. All rights reserved. www.elsevier.com/locate/endm doi:10.1016/j.endm.2012.10.017 Hakimi [2]. He formulated the competitive problem under the assumption that consumers deterministically choose the nearest store. In the real world, however, this assumption is not always acceptable, because consumers do not always choose the nearest store. Rather, consumers probabilistically choose among several stores. This probabilistic choice behavior is modeled by Huff, known as the Huff model. Huff formulated a model for capturing market share assuming that the probability that a consumer patronizes a shopping center is proportional to the attractiveness of the center and inversely proportional to a power of the distance to it. Although the original Huff model was based on an assumption that a market area is represented by a continuous plane with Euclidean distance, the model was extended to the network Huff model by Okabe and Kitamura [6] which was defined on a network with the shortestpath distance. Ghosh and McLafferty [1] considered their problem under the same assumption of discrete demand (nodal demand). Okunuki and Okabe [7] considered link based demand with slightly changed objective function. In this paper we apply the network Huff model to a competitive location problem optimizing new facility locations on a network. We apply Variable Neighborhood Search and Multi-Start Local Search metaheuristics to solve this problem assuming that new facilities can be located at any point on the network and demand generated in the nodes. 1.1 Problem definition We assume that customers are located in the vertices of a network N=(V,E), V={v1,...,v n},n∈N,E⊆V2. The customers raise demand. We also assume that there are mfacilities already located on the network. The facilities provide service and hence satisfy the raised demand. They are located at points y1,...,y mon network N. The demand w(vi)=wiassociated with the vertex vi,i∈{1,...,n}, has the following properties: w(vi)≥0and  vi∈V w(vi)=1. The demand wmay vary from vertex to vertex. For instance, it can be distributed uniformly to each vertex. Our goal is to locate pnew facilities x1,...,x pon the network which will respond to the customers’ demand so that the captured demand is maximal. To state the above location optimization problem more explicitly, let us formulate the network Huff model on N.Firstly, let us introduce facility attractiveness, a property of each facility in the system. Facility attractiveness S. Roksandi´c et al. / Electronic Notes in Discrete Mathematics 39 (2012) 121–128122 of a specific facility may be measured by the floor area, by the number of services/items that specific facility offers or in any other predefined way. Therefore, let us denote with ay1,...,a ymand ax1,...,a xpthe attractiveness of the existing and new facilities, respectively. In order to unify the notations and simplify formulas, let us denote with afjthe attractiveness of •the existing facility when f≡y,j∈{1,...,m}and •the new facility when f≡x,j∈{1,...,p} located at point fj.Letd(vi,f j) be the distance from the customer located in vertex vito the facility at fjon network N. Let us now introduce distance deterrence function F(d(vi,f j)) of the customer in vifrom the facility at fj. The distance deterrence function is a monotonically decreasing function with respect to d(vi,f j). In his original model, Huff specified the distance deterrence function Fas a power function, i.e. F(d(vi,f j)) = d(vi,f j)−λ,λ>0. Eventually, let P(vi,f j) be the probability of customer in vichoosing facility at fjamong the m+ppossible facilities. In these terms, the network Huff model is as follows P(vi,f j)= afjd(vi,f j)−λ fkafkd(vi,f k)−λ. Using the network Huff model, we proceed with formulating a problem for obtaining the demand D(fj) captured by facility at fj.LetD(vi,f j)bethe demand in vicaptured by facility at fj. Since the Huff model gives us the choice probability of customer in vichoosing the facility at fj,D(vi,f j)is obtained from multiplying the probability P(vi,f j)byw(vi), i.e. D(vi,f j)=P(vi,f j)w(vi)= afjd(vi,f j)−λ fkafkd(vi,f k)−λw(vi).(1) To obtain the demand D(fj) captured by facility at fjwe need to sum the equation (1) over all vertices vi∈V, i.e. D(fj)= vi∈V D(vi,f j)= vi∈V afjd(vi,f j)−λ fkafkd(vi,f k)−λw(vi). With mexisting facilities located at points y1,...,y mof network Nwe are supposed to locate pnew facilities at points x1,...,x pin order to compete S. Roksandi´c et al. / Electronic Notes in Discrete Mathematics 39 (2012) 121–128 123 them and capture maximal demand. The total demand captured only by new facilities is given by formula p  j=1 D(xj)= p  j=1  vi∈V axjd(vi,x j)−λ fkafkd(vi,f k)−λw(vi), where f∈{y,z};j∈{1,...,m}if f=y, and j∈{1,...,p}if f=z. Since it has to be maximal, problem we have to solve is max x1,...,xp∈N p  j=1  vi∈V axjd(vi,x j)−λ fkafkd(vi,f k)−λw(vi). 2 Variable Neighborhood Search and the application to Huff location problem 2.1 Variable Neighborhood Search concept Variable Neighborhood Search (VNS) ([3],[5]) is a well known metaheuristic method. It is designed for solving various combinatorial optimization problems. It uses local search procedure as one of its basic tools. Moreover, it involves systematic change of neighborhoods in the search. Unlike metaheuristics based on local search methods, VNS does not follow a trajectory, but explores increasingly distant neighborhoods of the current incumbent solution. Then, a local search routine is applied repeatedly to find local optima starting from these neighboring solutions. The search is re-centered around a new solution if and only if an improvement has been made with respect to global best solution. Therefore, to construct different neighborhood structures and to perform a systematic search, we need to have a way for finding the distance between any two solutions, i.e., one needs to supply the solution space with some metric (or quasi-metric) and then induce neighborhoods from it. In the following sections we answer this problem-specific question for our particular problem. The basic idea of VNS metaheuristic is to use more than one neighborhood structure and to proceed to a systematic change of them within a local search. The algorithm remains in the same solution until another solution better than the incumbent is found and then jumps there. Neighborhoods are usually ranked in such a way that intensification of the search around the current solution is followed naturally by diversification. The level of intensification or diversification can be controlled by a few easy to set parameters. We may view S. Roksandi´c et al. / Electronic Notes in Discrete Mathematics 39 (2012) 121–128124 the VNS as a ”shaking” process, where a movement to a neighborhood further from the current solution corresponds to a harder shake. Unlike random restart, the VNS allows a controlled increase in the level of the shake. 2.2 The application to the Huff network model In order to implement VNS for the specific variant of the Huff location problem, we need to define solution representation as well as neighborhood structures and local search strategy. A particular solution consists of the location set for the new facilities on the given network. The location of each facility is uniquely determined by the edge, i.e. by the pair of vertices, and the position on the edge. The position on the edge is given by 1-dimension coordinate belonging to the [0,1] interval with respect to one of the vertices of the edge. Therefore, the location of the particular facility is given by the ordered pair (x, (u, v)), where the first entry refers to the position on the edge given by the second entry of the pair. The position xis calculated with respect to the first vertex of the pair related to the edge. As the particular solution consists of p facility locations, it will be presented as a list [(x1,(u1,v 1)),...,(xp,(up,v p))] of pordered pairs where the ith pair corresponds to the ith facility location. Let us now define a neighborhood structure in the solution space we introduced. If s=[(x1,(u1,v 1)),...,(xp,(up,v p))] is a solution, we may chose at random one of the pfacilities and move it to one of the adjacent edges. Then we perform local search on the new edge by some of the well known techniques (line search, Fibonacci search, etc.) in order to reach the location which influences the objective function the most. We call this operation the rank 1stepping. If we repeat this operation ktimes, k<=p,wecallitthe rank kstepping. We say that a solution sis at the step-distance kfrom the solution sif scan be transformed into sby applying the rank kstepping. In order to improve the implementation performances, we have introduced another type of neighborhood structures. If s=[(x1,(u1,v 1)),...,(xp,(up,v p))] is a solution, we may chose at random two of the pnew facilities of the solution and swap their locations. We call this operation the rank 1swapping.Ifwe repeat this operation ktimes, k<p/2,wecallittherank kswapping.We say that a solution sis at the swap-distance kfrom the solution sif scan be transformed into sby applying the rank kswapping. The best results are obtained combining these two types of neighborhood structures. To complete the VNS implementation, we have to define local search strategy. A first improvement local search strategy is performed: starting from a solution swe move a new facility to each of the adjacent edges until the first S. Roksandi´c et al. / Electronic Notes in Discrete Mathematics 39 (2012) 121–128 125 improvement of the objective function value is found. After repeating this for each of the pnew facilities, the best of the obtained plocations is kept. Let us denote by Nk,k=1,...,k max a finite sequence of pre-selected neighborhood structures, and by Nk(x) the set of feasible solutions corresponding to neighborhood structure Nkat the point x,wherexis an initial solution. Let us note that most local search metaheuristics use one neighborhood structure, i.e. kmax = 1. The algorithm presented here demonstrates the application of the basic VNS heuristic to the multifacility Huff location model on a network. Algorithm 1 VNS algorithm for Huff location model. 1. Find an initial solution 2. Choose a stopping criterion 3. repeat 4. k=1 5. while (k<=kmax) 6. (Shaking) Choose at random either stepping or swapping neighborhood type with equal probability. Generate randomly a point xfrom Nk(x) 7. (Local search) Apply first improvement local search method with xas the initial solution; the obtained local minimum denote by x 8. (Move or not) if x is better than the incumbent 9. move to x (x=x) 10. k=1 11. else k=k+1 12. until the stopping criterion is met Usually, the initial solution is determined by some constructive heuristic and then improved by local search before the beginning of actual VNS procedure. In this case the initial solution is generated randomly and then improved by Fibonacci local search method. The stopping criterion may be e.g. the predetermined maximal allowed CPU time, the maximal number of all iterations or the iterations between two improvements. Here the stopping criterion is maximal allowed CPU time. Often successive neighborhoods Nk are nested, but it is not necessary to be always the case. Let us note that the point xis generated at random in order to avoid cycling which might occur if any deterministic rule was used. Basic VNS is a simple metaheuristic and its only parameter is kmax the preselected number of neighborhoods. Although, for each particular problem the solution representation, number and order of neighborhoods, and stopping condition should be defined in a way to ensure S. Roksandi´c et al. / Electronic Notes in Discrete Mathematics 39 (2012) 121–128126 Table 1 Computational results Instance VNS MSLS No. n q p best avg st.dev best.time best best.time 1lin105.tsp 105 13 850.00 50.00 0.00 3077.89 20.77 102.06 2pr124.tsp 124 15 10 49.71 49.65 0.07 3844.65 22.55 2599.89 3pr136.tsp 136 17 11 41.50 41.22 0.30 4205.92 23.41 3572.44 4kroA150.tsp 150 18 12 41.67 41.39 0.22 4783.25 19.68 2157.19 5kroB200.tsp 200 25 16 47.64 47.28 0.21 14687.06 17.96 8959.79 efficient execution of the search. 3 Computational results The VNS algorithm for the specific Huff location model is implemented in C programming language on Linux platform. Test instances have been run on the computer with the i686 Intel Core 2 Duo CPU E6750 at 2.66GHz and 8GB RAM. Since there does not exists the set of benchmark problems for the Huff location model, we have chosen small problems from the TSPLIB library where network dimension varies from 100 to 200. The number qof existing facilities is set to n/8 and the number of new ones to 2/3q. The locations of existing facilities are created in the following way. Firstly, they have been chosen randomly. Then the VNS method was applied with 10% of total running time planned for the VNS algorithm execution for the particular test instance. In the end, randomly chosen pout of qexisting facility locations were switched with the new facility locations obtained by the VNS algorithm. The attractiveness of each facility has been chosen randomly. Our experience shows that the best results are obtained if the probability of choosing either stepping or swapping shaking strategy is set to 0.5. kmax should be set to p/2. Maximal running time depends on the size of the particular test instance and it varies from1to5hours. The results obtained by VNS are compared with the results obtained by the Multi-Start Local Search metaheuristic (MSLS). It is an iterative approach where a single iteration consists of generating a random solution and performing a local search strategy with the random solution as a starting point. In case there was the improvement of the objective function value, the incumS. Roksandi´c et al. / Electronic Notes in Discrete Mathematics 39 (2012) 121–128 127 bent is updated. We applied first improvement local search strategy. Initial solution was generated randomly. The algorithm is implemented in C programming language on Linux platform. The obtained results are presented in the Table 1. Both of the algorithms were given the same total execution time, although, only time when the best solution was reached is reported. Solutions (either best or average) are expressed as the percentage of the total demand. 4Conclusion We may conclude that VNS behaves better than MSLS in all tested examples in the sense of the objective function value, although for the same running period MSLS reaches its best solution in less time. References [1] Ghosh, A., McLafferty, S., and C. S. Craig, Multifacility retail networks,in Facility Locations, (Drezner, Z., ed). (1995), 301-330. [2] Hakimi, S. L., On locating new facilities in a competitive environment,European Journal of Operational Research. 12, (1983), 29–35. [3] Hansen, P., and N. Mladenovi´c, Variable neighborhood search methods, Encyclopedia of Optimization, 2nd Ed., Springer. part(22), (2009), 3975–3989. [4] Huff, D. L., A Probabilistic Analysis of Shopping Center Trade Areas,Land Economics. 39, (1963), 81–90. [5] Mladenovi´c, N., and P. Hansen, Variable neighborhood search: principles and applications, European Journal of Operational Research. 130, (1997), 449–467. [6] Okabe, A., and M. Kitamura, A computational method for market area analysis on a network, Geographical Analysis. 28, (1996), 330-349. [7] Okunuki, K.-I., and A. Okabe, Solving the Huff-Based Competitive Location Model on a Network with Link-Based Demand, Annals of Operations Research. 111, (2002), 239-252. S. Roksandi´c et al. / Electronic Notes in Discrete Mathematics 39 (2012) 121–128128