Solving planar location problems by global optimization
- PDF / 361,725 Bytes
- 7 Pages / 595.276 x 790.866 pts Page_size
- 80 Downloads / 184 Views
REVIEW ARTICLE
Solving planar location problems by global optimization Zvi Drezner
Received: 5 December 2011 / Accepted: 23 September 2012 / Published online: 4 October 2012 Springer-Verlag Berlin Heidelberg 2012
Abstract In this paper we review global optimization techniques and their application to location problems. The following techniques are reviewed: Big Square Small Square, Big Cube Small Cube, Big Triangle Small Triangle, Big Segment Small Segment, DC Optimization and the Ordered Median formulation. These techniques are described, and examples for their implementation for various location problems are given. Keywords Facility location Global optimization DC optimization Ordered median
1 Introduction Planar facility location problems were investigated by mathematicians for hundreds of years [32, 54]. In the last 50 years, with the advent of computers, operations research and logistics practitioners recognized the importance of such models in providing efficient and cost-effective solutions to logistics problems. There are many applications to facility location models. For example: •
• •
Desirable Facilities: warehouses, schools, post offices, public swimming pools, product positioning, cell phone transmission towers. Competitive Facilities: stores, shopping malls, restaurants, gas stations, bank branches. Emergency Facilities: hospitals, fire stations, ambulance depots, police stations.
Z. Drezner (&) Steven G. Mihaylo College of Business and Economics, California State University-Fullerton, Fullerton, CA, USA e-mail: [email protected]
• •
Obnoxious Facilities: airports, jails, nuclear power plants, dump sites, polluting factories. Miscellaneous Models: satellite orbits, roads, networks.
Common to these models is that (a) a set of demand points is given, and (b) the objective function is a function of the distances between demand points and the unknown locations of the facilities. The first proposed location problem is the Weber problem which seeks the location of a facility minimizing the weighted sum of distances to the demand points [32, 54]. This model is in the category of desirable facilities because shorter distances are preferable. The objective of competitive facility location models is to locate facilities that attract the most buying power associated with demand points in the presence of competing facilities. A typical objective function in emergency facilities models is the minimization of the maximum distance to all demand points. A typical objective function in obnoxious facility models is the maximization of the minimum distance to demand points. We first present the ordered median formulation that provides a unified scheme to model many of the location problems discussed above. We then review various global optimization techniques to solve planar location problems that are based on a non-convex objective. When the objective function is convex, finding the optimal solution is relatively easy. There is only one local optimum which must be the global one. A simple gradient
Data Loading...
