|
|
| GeoCommunity Mailing List |
| |
| Mailing List Archives |
| Subject: | Re: CLARIFICATION - RE: [gislist] cluster or group points in
AV3.2 |
| Date: |
01/08/2004 10:40:02 AM |
| From: |
Quantitative Decisions |
|
|
At 04:23 PM 1/7/2004 -0500, RICK GRAY wrote:
>My "overall" territory is most of the province of Ontario. I will have
>350+ stations (all identical) spread out in a not very even distribution
>throughout the overall territory - i.e. in some regions the density is
>greater than others - sometimes significantly so. We need to divide
>these into service territories given that an individual can service X
>(+/-) number of stations in a day. In sparsely "populated" territories,
>the number will be less because driving time will increase. However,
>this will not likely greatly affect the overall results.
>
>So... what I need to do is take a point file and divide it somehow into
>groups - either by specifying the number in a group or by specifying the
>number of groups.
Rick,
OK, the clarification is very helpful. Let's take a logical approach to
formulating the problem and identifying a solution method, following the
questions I posed last night and your answers to them:
>(7) Do small improvements in clustering matter a lot, or would a rough
>approximate solution be ok?
>
>>rough is OK.
This suggests you could do the clustering manually, by
trial-and-error. The question comes down to whether a manual approach is
an effective use of your time and whether it is likely to produce
reasonable solutions. I will address this again at the end of this message.
>(2) How will you measure how clustered a group of points is?
>
>>For this project, the level of clustering is not really important. It
>>doesn't really need to be scientifically devised. ...
>>In fact we need to have all stations covered within 3 days of the middle
>>and end of each month ...
I did not phrase this question well, but your other answers have clarified
it for me. Your measure of degree of clustering is total time to service
the stations in the cluster. The "three days" is a constraint on the
maximum cluster size.
>(6) Will there be constraints on cluster size? For instance, in some
>applications (especially territory construction) you might want all
>clusters to have an (approximately) equal number of points.
>
>>Flexible. I can create equal territories then manually modify if
>>necessary.
I intended to state this question more broadly: the reference to number of
points was an illustration only. Your constraint is that the maximum
cluster size must not be greater than three days.
>(1) Will you specify how many clusters must be created, or should the
>number be part of the solution ("natural" clustering)?
>
>>The first will work fine, the latter would be ideal.
You would like to minimize the number of clusters.
>(8) Will the problem be a dynamic one, with data constantly changing
>and the solution developing along with it, or is this a static situation
>where little is likely to change for a long time?
>
>>It will change each year for at least the next 3 years for this project
>>because some new areas will be added and in some areas the density may
>>be increased.
I think we can treat this as a static problem that has to be solved two or
three times over. The potential complication is that each subsequent
solution probably should look as similar to previous solutions as possible,
so that territories do not radically change from year to year.
At this point we can formulate the problem:
Given a network from which travel times can be computed (at least
approximately), and given a set of points on that network, to partition the
points into the smallest number of clusters for which the total time to
service each cluster does not exceed three days. Ideally, among all
possible solutions, the total service times of the clusters should be
minimized. When the network changes, we want to be able to repartition the
points to meet the three day and smallest-number constraints in such a way
that the clustering changes as little as possible.
This formulation presumes either (a) your service agents are free to locate
close to each cluster so they can minimize their travel time or (b) all
agents originate at a common location. A slightly different formulation is
necessary if you have fixed multiple home bases for your current agents or
if they must return to some fixed home base at the end of each day. In any
case, the method I will propose below can handle any of these variations.
>(5) Do there exist geographic obstacles that prevent certain pairs of
>points from being contained in the same cluster?
>
>>Yes. The Great Lakes (especially Georgian Bay) provides a significant
>>barrier, ...
This will automatically be handled by the network, so it does not
complicate the probl
|
|
Sponsored by:
For information
regarding
advertising rates
Click Here!
|
