Excel Solver

The towns in Kent with their corresponding x and y coordinates as well as their population are given overleaf. This data is also in an excel file that can be downloaded from Moodle under the name “Kent-Towns”.

(a) Using Excel Solver, or otherwise, establish a location in the plane, that minimises:

(i) the sum of distances to all Kent towns,

(ii) the sum of weighted distances to all Kent towns, with populations as weights,

(iii) the maximum distance to any Kent town, and

(iv) the maximum weighted distance to any Kent town. [8]

(b) Assume from now on that facilities can only be established at the given towns, rather than anywhere in the plane.

(i) Establish at which town a single facility should be built, if the aim is to minimise the sum of distances from the facility to all Kent towns.

(ii) Having established this facility, use the ADD heuristic to find the location of a second facility. Allocate every town to its nearest facility. Explain why these two facilities are not necessarily the optimal solution to the p-facility discrete location problem (p=2). Can you find (using your own heuristic thinking) a pair of locations that gives a better result? [12]

In your answers to the above, clearly explain how you have arrived at your results.

 

TOWN/CITY	X	Y	POPULATION
Ashford	600985	142805	58,178
Broadstairs	639320	167760	24,370
Canterbury	614880	157830	42,249
Chatham	575785	167920	70,540
Dartford	554200	174325	50,000
Deal	637510	152745	29,248
Dover	631650	141835	39,078
Faversham	601530	161425	18,000
Folkestone	622765	135915	53,411
Gillingham	577350	168385	99,773
Gravesend	564730	174170	51,150
Herne Bay	617900	167945	31,000
Maidstone	576150	155705	75,000
Margate	635460	170580	58,465
Northfleet	562235	174310	13,590
Ramsgate	638365	165180	37,967
Rochester	574375	168475	25,000
Royal Tunbridge Wells	558360	139265	45,000
Sevenoaks	552375	155295	18,588
Sheerness	591955	174725	20,000
Sittingbourne	590740	163660	55,000
Tonbridge	559080	146600	31,600
Whitstable	610670	166740	30,000