Advertisement
Published in:
2009 | OriginalPaper | Chapter
1. Distance Functions in Location Problems
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Distance is a numerical description of how far apart objects are at any given moment in time. In physics or everyday discussion, distance may refer to a physical length, a period of time, or it is estimated based on other criteria.
While making location decisions, the distribution of travel distances among the service recipients (clients) is an important issue.
Most classical location studies focus on the minimization of the mean (or total) distance (the median concept) or the minimization of the maximum distance (the center concept) to the service facilities. (Ogryczak 2000) In these studies, the location modeling is divided into four broad categories:
Analytic models. These models are based on a large number of simplifying assumptions such as the fix cost of locating facility. The travel distances follow the Manhattan metric.
Continuous models. These models are the oldest location models, deal with geometrical representations of reality, and are based on the continuity of location area. The classic model in this area is the Weber problem. Distances in the Weber problem are often taken to be straight-line or Euclidean distances but almost all kind of the distance functions can be used here (Jiang and Xu 2006; Hamacher and Nickel 1998).
In the study of continuous location theory, it is generally assumed that the customers may be treated as points in space. This assumption is valid when the dimensions of the customers are small relative to the distances between the new facility and the customers. However, it is not always the case. Sometimes, we should not ignore the dimensions of the customers. Some researchers have treated the customers as demand regions representing the demand over a region.
Jiang and Xu (2006) discussed that some researchers such as Brimberg andWesolowsky in 1997, 2000 and 2002 and Nickel et al. in 2003 used the distance between the facility and the closest point of a demand region; and in the others, the distance between the facility and a demand region may be calculated as some form of expected or average travel distance.
Network models. Network models are composed of links and nodes. Absolute 1-median, un-weighted 2-center and q-criteria L-median on a tree models are some well-known models in this area. Distances are measured with respect to the shortest path.
Discrete models. In these models, there are a discrete set of candidate locations. Discrete N-median, un-capacitated facility location, and coverage models are some well-known models in this area. Like the distances in continuous models, all kind of the distance functions can be used here but sometimes it could be specified exogenously (Hamacher and Nickel 1998; Fouard and Malandain 2005).
Distances and norms are usually defined on the finite space En and take real values. In discrete geometry, however, we sometimes need to have discrete distances defined on Zn with their values in Z. Since Zn is not a vector space, the notion of distances and norms had to be extended.