I have the information of 150 companies in terms of their location (latitude and longitude) throughout the UK.
I would like to identify the location for the waste collection centre for all of them, so it requires all of them to be clustered/grouped which will minimise the total travel distance. Each cluster may have their own waste collection centre.
How this clustering can be done? Maybe companies in 50km radius in one group, etc? Anyone can help me on this?
in using the k-means formula try to use the haversine distance instead of the Euclidean distance.
.
an approach has been described here :
https://www.researchgate.net/publication/227727308_A_Clustering-Based_Approach_to_the_Capacitated_Facility_Location_Problem1
.
Article A Clustering‐Based Approach to the Capacitated Facility Loca...
A quick and easy way is to consider the k-means clustering algorithm that is available for example in SAS. This uses clustering terminology but it is somewhat applicable to location --- the X and Y coordinates are the two "attributes" ... I believe you can have it run through a variety of options like how many centers / facilities (that is "k").
One caveat -- latitude and longitude are not like euclidean coordinates ... depending on the region there could be some distortion in that degrees of longitude become smaller as you go north .... but the result might be a start.
I agree that if you want a more sophisticated location theory based approach you will have to look at algorithms for the p-median problem (possibly with capacity constraints which I might mention really make this much more difficult problem).
Thanks Dr Morton, I was informed that Kmeans clustering may not applicable to non-linear case. I am bit confused here because the locations distribution may be it is not linear. any comments sir on this?
Not sure what you mean by non-linear --- it's possible someone used that to mean that the X Y from LAT LON is not suited to a euclidean metric and measuring distance is not accurate by the euclidean formula if you have LAT and LON. (That euclidean measurement is typically what k-means would want to do.) .... So distance from (xi,yi) to (xj,yj) =
sqrt ((xi - xj)^2 + (yi - yj)^2))
I think you can see if you put in LON for X and LAT for Y you would not get the distance between the points in miles, or km, or ....
There are ways around this mostly relying on map projection ideas.
You could for example use the great circle formula on the LAT LON to get a matrix of distances, and then apply multidimensional scaling to that distance matrix to get the X Y coordinates from these distances.
Another way around this is to extract coordinates that correspond to a more grid-like structure. Could you transform the coordinates to some kind of planar system (I'm thinking UTM)?
Indeed, I'm not sure to fully understand what you mean with "non-linear".
I fully agree with the answers of Morton, including his suggestion to use the great circle formula. Note however that, for short distances, the simple euclidian distance is a nearby perfect proxy of the great circle distance.
Morton suggest the use of the K-means clustering method, which is one of the most used hierarchical clustering methods. Other clustering methods can be used. Indeed, the different methods can produce (very) different results. I remember having written a research paper in which several clustering methods were compared. This was applied to the optimal location of container terminals (see attached link to paper, pages 11 & 12). If you are interested in this, please contact my co-author (Sabine Limbourg), who wrote more on this. She is also on Research Gate.
Conference Paper INTER-MODAL FREIGHT TERMINALS LOCATION: Discover the best po...
Dear Morton and Jourquin,
Recently I was informed that kmeans might not be suitable for this case. He said
"The reason is that k-means is designed to minimize variance. This is, of course, appearling from a statistical and signal procssing point of view, but your data is not "linear".
Since your data is in latitude, longitude format, you should use an algorithm that can handle arbitrarydistance functions, in particular geodetic distance functions. Hierarchical clustering, PAM, CLARA, and DBSCAN are popular examples of this.
The problems of k-means are easy to see when you consider points close to the +-180 degrees wrap-around. Even if you hacked k-means to use Haversine distance, in the update step when it recomputes the mean the result will be badly screwed. Worst case is, k-means will never converge!"
Any comments on this?
.
at the uk scale i cannot see where the problem is ...
if you were clustering worldwide, k-means could be a problem but at uk scale the earth is flat !
regarding latitude and longitude, as a first try i would not bother but recode the longitude so that it does not "jump" from 0° to 360° around the Greenwhich meridian (just code longitudes from -180° to 180° with 0 at Greenwhich)
.
I agree with Fabrice.
You could even simplify your problem using a simple offset of +180 for your longitudes and consider your lat/lon points as simple coordinates in a X/Y system to compute a straight-line length to do the job.
Possible use of cluster analysis method which helps to sort the companies in accordance with the line length and width so that secreted companies in the form of clusters each cluster contains a group of companies.
And her style can be applied using a space program
I hope that this thoroughly ... as I understood
- Badges
- Science topic
- Similar topics
- Geoscience
- Cartography