8

I am trying to compare locations of where several thousand facilities have been actually built to where they would be optimally located to minimize travel times of the population (represented by census block or tract centroids). I'm having trouble finding much of anything on how to optimally locate points.

I've got some idea of how to go about choosing these locations, but the sheer number of points to be placed in space means that any non-cleverly optimized algorithm is going to take a long time, possibly years. Thus my question: Are there standard algorithms for choosing where to locate a fixed number of points?

I will ultimately take whatever algorithm I find as a starting point and adapt it to incorporate more information than just the population counts. Thus the preferred answer would include a detailed description of the algorithm, code, or be written in an open-source language, so that I can replicate and extend it. However, if ArcGIS has a convenient function for this optimization, I'd be happy to start with that.

Improve this question
2
  • 1
    It would help to have a clearer--preferably quantitative--description of what "optimal" means. For instance, are you interested in average round-trip travel time to the nearest facility or some other measure of proximity? Regardless of your measure of trip cost, do you wish to compare the cost of the existing configuration to the best cost that could be achieved by relocating any existing facility, or do you also wish to allow facilities to be removed altogether? Although removing a facility increases mean trip time, it reduces the cost of building and maintaining the facilities.
    – whuber
    Commented Dec 23, 2012 at 16:24
  • @whuber For now I'm merely interested in minimizing some reasonable function of distance (either as-the-crow-flies or the square thereof). The eventual optimization problem will include the factors you've identified and more (cost to relocate a facility, etc.). But for now I just wanted a standard way of choosing locations to minimize distance, both because it's a starting point to extend in moving towards the ultimate algorithm, and because I'm on the fence about continuing this project and want to explore the cruder estimate before refining it.
    – Ari B. Friedman
    Commented Dec 23, 2012 at 18:22

2 Answers 2

Reset to default
3

You might want to check out the K-means clustering algorithm.

In data mining, k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. This results in a partitioning of the data space into Voronoi cells.

Here's another definition:

k-means clustering is a method of classifying/grouping items into k groups (where k is the number of pre-chosen groups). The grouping is done by minimizing the sum of squared distances (Euclidean distances) between items and the corresponding centroid.

A centroid is "the center of mass of a geometric object of uniform density", though here, we'll consider mean vectors as centroids.

enter image description here

Figure 1. A clustered scatter plot. The black dots are data points. The red lines illustrate the partitions created by the k-means algorithm. The blue dots represent the centroids which define the partitions

In your situation, the census block or track centroids would be the input and the number of points N would be the number of clusters. Here's a tutorial to get you started.

Improve this answer
5
  • Interesting. I'd never thought of K-means for this, but I guess the centroids do rather have the property that I want.
    – Ari B. Friedman
    Commented Dec 23, 2012 at 1:34
  • You might want to test it and see how it performs :)
    – R.K.
    Commented Dec 23, 2012 at 1:36
  • It seems to perform well on sample data, but R's implementation lacks the ability to weight (by population, in this case). I might have to rewrite the function to allow weighting. There goes my weekend ;-)
    – Ari B. Friedman
    Commented Dec 23, 2012 at 15:09
  • 1
    Take some care: k-means does not optimally locate points for most travel problems. It is optimal when the cost of a trip is proportional to the square of its distance. The solution for typical costs, which have a linear relationship to distance, is extremely difficult to obtain.
    – whuber
    Commented Dec 23, 2012 at 16:16
  • @whuber Indeed. This is made plain in a quick exposition with detailed code (Fortran and C++) here. The travel costs are in relation to emergency care, so a supra-linear travel cost is not entirely unreasonable, although the square is unlikely to be exactly right.
    – Ari B. Friedman
    Commented Dec 23, 2012 at 20:06
1

I co-wrote a paper on this problem in 1996, see

Modelling and Optimising Flows Using Parallel Spatial Interaction Models (1996), Turton & Openshaw, PROCEEDINGS OF EURO-PAR'96, VOLUME II.

You can download a copy from citeseer

We also wrote

Turton I., Openshaw S. (1997) Parallel Spatial Interaction Models. Geographical and Environmental Modelling, Volume 1, number 2, pages 179-197.

but I can't find an online copy.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.