The S-Distance software project, mentioned earlier in this subsection and described further in Sirigos and Photis (2005), provides tools to compute solutions to quite large p-median and p-center problems using a range of heuristics, together with solutions for selected coverage problems. The heuristics they implement include many of those described in Taillard (2003), Daskin (1995) and Dyer and Frieze (1985). Data may be read from various file formats, including OR-Library files and network node/link files in dbf format. These various methods may then be compared in order to obtain an estimate of their relative efficiency. For the purposes of this exercise we used an S-Distance test dataset comprising the street network in Tripolis, in the region of Arcadia, Southern Greece. The data consist of 1358 vertices and 2256 edges. Each vertex or node has an integer demand value associated with it, ranging from 1 to 137, plus 35 nodes with 0 demand. Each edge or street link has a “to-from” and/or “from-to” cost of travel assigned to it, with selected edges being designated as one-way. In this test we sought 5 locations to service the demand using several different heuristics.

Figure 7‑15A to Figure 7‑15C show the results of running these procedures on the test dataset. In these figures the red circles identify the solution points (median locations) and the darker lines show the network edges that each center uses to service the demand. The figure in brackets in each case shows the objective function value, z, achieved, in millions of units (sum of demand times cost of travel). The basic greedy-random heuristic used by S-Distance is that defined by Dyer and Frieze (1985). This simply involves selecting the highest weighted demand point (or any at random if there are multiple locations with equal weights). The next location is then chosen by selecting the demand point that has the largest weighted distance from its nearest center. The algorithm is of complexity O(np) and yields results that are within 2-3 times the optimum (and so are not very good!). By contrast, the CLS procedure often produces very good results (within 1% generally) but requires longer to run, with a complexity of at least O(np(n+1)). CLS is essentially a form of alternating location-allocation (ALT) procedure, like that of Cooper described earlier. Initial solutions are then perturbed according to a greedy interchange rule that attempts to swap each ALT solution point in turn with another candidate site, and examines whether the resultant solution improves the ALT local optimum.

The greedy heuristics shown in Figure 7‑15A and B ran in almost no processor time, with the greedy-add algorithm producing a much improved z-value. The five locations it chose, however, are very different from those in Figure 7‑15C, which was the solution found by three other algorithms: candidate list search (CLS), Lagrangian relaxation (upper bound solution, LR), and variable neighborhood search (VNS). Of these VNS was fastest to run, requiring under a second of processor time, whilst CLS took around 3 seconds and LR over 3 minutes. However, the LR procedure provides both upper and lower bounds on the solution, which in this case showed that the lower bound was 1.177, but this solution is infeasible, so it is extremely likely that the solution shown is, in fact, the true optimum. The final image, Figure 7‑15D, shows the allocation of customer demand to the individual centers. The size of the colored circles reflects the demand weights assigned to the network vertices.