A perturbation heuristic for a class of location problems
- PDF / 220,600 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 94 Downloads / 234 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
A perturbation heuristic for a class of location problems S Salhi University of Birmingham, UK A constructive heuristic which has the ¯exibility of perturbing the solution while guiding the search toward a better solution is developed. Interesting ®ndings are obtained when this heuristic is tested against reputable methods on a class of uncapacitated location problems. Keywords: perturbation heuristic; Lagrangian heuristic; facility location
Introduction The location problems considered in this study include the p-median, the p-uncapacitated and the uncapacitated facility location problems. To remind the reader of these problems, a short description is provided. In the p-median problem, the values for the ®xed depot cost is considered the same for all depots (for clarity it is usually set to zero) and the number of facilities to open is set to p. In the puncapacitated case, there are also p facilities to open but the ®xed depot cost is not necessarily the same for all depots. In the uncapacitated case, the ®xed cost of the facilities is not necessarily the same and the number of facilities to open is an endogeneously determined quantity. The latter problem is usually referred to as the ®xed charge uncapacitated location problem. In these problems, each customer is served by one facility only and there is no restriction on the capacity of the facilities. The object is the minimisation of the total distribution cost. Applications of these models arise in both public and private sectors.1,2 For a comprehensive survey see the edited books by Mirchandani and Francis,3 Drezner,4 and for background reading the recent textbook of Daskin.5 There exist several exact methods for solving these location problems, the most recognised approaches include Lagrangian relaxation heuristics6 and linear programming based approaches.7 Although these methods have proved to be successful, they have the handicap of not being easily extendable to handle ef®ciently more complex problems such as capacitated and single source location problems. To overcome such potential shortcomings, heuristic methods were devised to provide the user with some reasonable solutions which may not be necessarily optimal. For further
Correspondence: Dr S Salhi, The University of Birmingham, School of Mathematics and Statistics, Edgbaston, Birmingham B15 2TT, UK.
discussion on heuristic search techniques see Reeves8 and Salhi.9 In general, most heuristic search methods fall into one of the following categories: constructive (descent/perturbation/multi-phase approach) local search (tabu search, simulated annealing, noisy method) population based (genetic algorithms) mathematically based (Lagrangian heuristic/incomplete branch&bound) human/graphical interaction hybrid search (combination of any of the above) We shall describe brie¯y two of the above categories, namely constructive and Lagrangian relaxation heuristics as these will be used in this study. For references on
Data Loading...
