The p-Median Problem - Location Science - page 31

2.6 Computational Results

In this section, we provide sample results for some of the algorithms outlined above.
We begin with Table 2.2 which shows the results of using a Lagrangian relaxation
algorithm embedded in branch-and-bound for the Beasley dataset. The instances
were all solved using an expanded version of the SITATION software (Daskin 2013 )
on a Macintosh computer running OS X version 10.8.5 with a 2.7 GHz Intel Core i7
processor and 16 GB of 1,600 MHz DDR3 memory using Parallels 7.0.15107. The
average solution time was under 45 s. The longest solution time—for PMED36—
was under 13 min. Seventeen of the 40 instances were solved at the root node and
all but three of the instances required less than 40 branch-and-bound nodes. The
average solution time is 44.9 s and the average number of branch-and-bound nodes
needed is 21.5.
The second part of the table illustrates the impact of using the variable forcing
rules outlined at the end of Sect. 2.5 at the end of the Lagrangian algorithm at the
root node of the branch-and-bound tree. The rules are quite effective at eliminating
candidate nodes; on average nearly 85 % of the candidate sites that could not be
in the solution were excluded at the root node using these rules. (The number of
candidate sites that could not be in the solution was equal to the total number of
candidate sites minus the number of facilities). Overall, 81 % of the candidate sites
were either forced in or out of the solution, on average.
Next we turn our attention to tests performed using the 500 most populous
counties among the 3,109 counties in the contiguous United States. While these
represent less than one sixth of the total counties, they encompass over 75 % of the
population living in the contiguous United States. Great circle distances between
the county centroids were employed. We used SITATION to solve the p -median
problem for this dataset with the number of facilities increasing from 1 to 25.
The solution time for each of these 25 runs was under 5 s and only two instances
required branch-and-bound to obtain provably optimal solutions. In each of these
two instances, only three nodes in the branch-and-bound tree needed to be explored
after the root node forcing rules were employed. Figure 2.2 plots the results for five,
10, 15, 20 and 25 medians. The model locates the first five cities near the major
cities of New York, Los Angeles, Dallas, Chicago and Miami. Additional facilities
are then added to better serve the rest of the counties. Figure 2.3 plots the demand-
weighted average distance versus the number of medians. As expected, the average
distance decreases with the number of medians. Also, the marginal improvement
decreases with the number of medians in this case.