Facility-Location Set-Covering Problem

District Wonderville has 58 small towns (towns 1 to 58). The district council is in the process of determining the locations of building fire stations to serve the community of these 58 towns. The district council has limited fund and the council wants to build the minimum number of fire stations.

You are hired by the district council to help them in making such decisions. The district council wants you to advise them on the  minimum  number of fire stations  needed to ensure that at  least one fire station  is within the following driving times of each city.

a)    3 minutes

b)   5 minutes

c)    10 minutes

d)    15 minutes

e)    20 minutes

In other words, for  each  of the abovementioned scenarios, the  district  council  needs  a  decision of the minimum number of fire stations to be built.

drivingtime.csv  shows  the  driving  times  (in  minutes)  required  to  drive  between  the  towns  in  District Wonderville.

You  intend  to  develop  a  Genetic  Algorithm  (GA)  to  help  the  district  council  in  deciding  the  minimum number of fire stations to be built in the district. The proposed GA must cover the following aspects:

1.    Problem modeling: variables and representation scheme.

2.    Fitness function design and constraints management.

3.    Parents and offspring population management models.

4.    Parent and survivor selection mechanism.

5.    Crossover and mutation operators.

6.    Initialization.

7.    Parameter tuning and termination criteria: For each scenario, tune the parameter of the GA. Based on a particular setting, use a maximum of 100 fitness function evaluations for each run and report your results averaged over 10 runs.

This assignment can be implemented using any of the programming languages, but preferably Java .

Assignment due date: 11 Dec 2022 (Sunday), 11:59 p.m. (Week 08).

Assignment type: Pair assignment (a group of two members). The member grouping will be done via the eLearn@USM.

Submission procedure: A zip/rar package which consists of the following items is to be submitted via the eLearn@USM:

1.    An assignment report (Times New Roman, font size 12, single spacing, not more than ten pages) which explains the algorithm and technique used as well as the experiments performed to obtain the best results. All the important aspects such as representation scheme, parent population size, offspring population size, parent selection mechanism, survival selection mechanism, reproductive operators, initialization, parameter setting, stopping criteria, and fitness function design. [Hint to create a good report: The report should be prepared in such a way that it allows one to replicate your experiments]

2.    A cover page which contains your details is expected to be included in your assignment report.

3.    All other supporting documents which can make the evaluator understand your work (e.g. source codes, screenshots, additional files from the relevant tools used in implementing the assignment).

The zip/rar package must be named according to the following notation: CCS516_[GroupNumber]_A01. For example, for Group03, they must name the zip/rar package as CCS516_Group03_ A01.

Reference:  Kindly  state  any  source  of  reference  should  you  refer  to  various  sources  to  complete  this assignment.

Grading rubric:

The total mark for this project is  100 marks. The total will be scaled to 8% of your overall grade.  It will consider the followings:

1.    Problem  modeling/formulation  (30%):  Illustrate  and  explain the  problem  modeling/formulation, fitness function design, and constraints management.

2.    Application  (40%):  Describe  and  implement the technique/algorithm that  are  used to  solve the facility-location set-covering problem.

3.    Parameter setting & results (20%): Explain the results and show how the results are used to support decisions. Inclusion of what-if analysis based on the four scenarios is expected.

4.    Problem  and  pitfalls  (10%):  Discuss  the  mistakes  that  have  been  done  and  the  knowledge  & experience gained throughout the project implementation.