Transform - Select Service Centers

Manifold includes four transform operators to find optimal locations for service centers. These include:

· Select Critical Service Centers

· Select N Critical Service Centers

· Select Service Centers

· Select N Service Centers

The operators solve two types of network tasks: to find regular service centers and to find critical, or emergency service centers. Both types of task occur in two forms: to find just one location for a service center or to find an N number of that type of service center.

Regular Service Centers

Given a set of nodes, called clients, finds the "central" node that minimizes the path length to travel from the center to each of the clients and to then return to the center. This is the classic problem for locating a regular or daily service center, where every day one must make the rounds of each of the clients. A real life example would be locating an industrial bakery that every morning must send a truck to deliver bread to the stores and restaurants that resell its baked goods. Every day the truck visits the same clients. The job is to place the bakery so that the overall distance travelled is minimized.

Critical Service Centers

Given a set of nodes, called clients, finds the "central" node that minimizes the maximum path length to any of the clients without regard to return travel. This is the classic problem for locating an emergency service center, where at any time one may be called upon to travel to a given client. A real life example would be locating a fire station that is equipped with regional facilities for fighting certain types of hazardous chemical fires. The possible clients are those factories that use such hazardous chemicals, but it is not known in advance at which factory an accident requiring the specialized equipment will occur. Thus the task is to place the fire station to minimize the distance to any one of the factories at which an accident might occur.

Variations

Clearly, both of the above examples are somewhat artificial. However, the general idea of minimizing distance for regular service or minimizing distance for emergency service can be applied to many network problems besides the siting of bakeries or fire stations. The Manifold transforms are deliberately kept fast and simple so they are easy to use. The main option is the use of the source / argument box in the Transform toolbar to specify the number of different service centers that are to be found. The "N" versions of the operators will find a dispersed pattern of the given number of service centers, placing each to optimize the service overall. The non-"N" version of the operators assumes we really intend to place only one service center, but it provides several backup options that are less optimal near the central location found.

Requirements

All four of the service center solvers require a connected network to function. In a connected network each point is exactly placed at the end of a line and all lines that are incident to other lines have their end coordinates exactly coincident. There are no gaps, points that are not located exactly on the lines, or lines that are intended to be incident but where the ends don't exactly coincide.

Examples

We begin with drawing of a network that has nodes at the ends of all links.

$images\sc_select_centers_net.gif$

Nodes are shown as small black squares.

$images\tbar_select_centers.gif$

To find the four best locations for regular service centers, we run the Select N Service Centers operator with a parameter of 4 in the transform toolbar.

$images\sc_select_centers_nreg.gif$

The operator selects the four optimal nodes. We could then copy these nodes and paste them into a new drawing if we wanted to record our findings.

$images\sc_select_centers_reg.gif$

The selection made by the Select Service Centers operator run with a parameter of 4 is seen above. The assumption is we are looking for only one regular service center but we want to have a choice of the four best candidates.

$images\sc_select_centers_ncrit.gif$

Running the Select N Critical Service Centers operator with a parameter of 4 creates the selection above. Note that although the nodes selected are similar to those selected for the regular centers, there is one node that is different from the similar node selected by the regular centers algorithm (blue arrow).

$images\sc_select_centers_crit.gif$

The Select Critical Service Centers operator with a parameter of 4 provides very different results than the regular service centers operator. These are the best four choices if an unpredicted dispatch must be made to any other node.

$images\sc_select_centers_crit2.gif$

If the results for four centers seem counter-intuitive, consider the result for a parameter of 2. The lower of the two selected nodes is the best (determined by running the transform with a parameter of 1), while the upper one is second best. This shows the power of graph theory to reveal solutions that one might not pick out by eye.