Blue Cow Round the World Challenge - Optimisation Software Solution

Overview: The 'Round the World Challenge'

Overview: The ‘Round the World Challenge’

The energy drink company, Blue Cow, is organising a ‘round-the world’ aeroplane race. Any country’s capital can bid to be one of the stage points around the tour; most do. So Blue Cow will have well over 100 offers of money but they can’t take all of them. They need optimisation software, which will find the subset of cities (and tour of these cities) that maximises their income – subject to the following restrictions:

• The tour starts and finishes in the same city (it’s a complete circuit)

• There’s a given minimum and maximum number of cities in the tour (it was 30-50 in 2020 but that could change year-on-year)

• There’s a given minimum and maximum total distance for the tour (in miles or km)

• There’s a given minimum and maximum distance for each flight between cities (m/km)

• Flying directly between some cities isn’t permitted due to local politics, etc.

• The tour must have a given minimum and maximum number of cities in each of the main continents:

o Europe

o Asia
o Africa
o Australasia
o South America
o North America

The actual values for all of these minima and maxima vary from year to year so the optimisation algorithm must be flexible enough to solve a different ‘Blue Cow’ problem each time.

Instructions

You will work in groups of two, three or four on this assignment (to be determined once we know class sizes). The end-product will be a software package (of one or more actual programs, written in any language), which provides a general solution to the problem described above – with any appropriate values for the constraints entered either at run-time or via a configuration file.

So, here’s what you have to do:

1. Consider the above challenge carefully. Discuss it as a team and with your module leader. Be sure you understand the problem before you start. There is a risk that you’ll head off in the wrong direction and eventually write inappropriate code if you misinterpret the requirements.

2. Consider how the requirements of this challenge relate to known optimisation problems. Investigate these problems, and their potential solutions, carefully. Determine where existing algorithms may be relevant to this problem (and where they won’t). Decide (using relevant calculations) whether an exact solution will be achievable or if approximation/heuristics will be needed. Iterate 1 and 2 until everyone’s agreed and you’re ready to start 3.

3. Design and develop a complete software package to address the challenge. The objective is to maximise income from the selected cities, subject to there being a valid tour around them. Your package must be flexible enough to accept the following parameters as runtime input or stored in a configuration file (you may find the latter easier in the long run):

• The tour starts and finishes in the same (any) city (a closed circuit/tour)

• There is a minimum and maximum number of cities in the tour (for example 30-50)

• There is a minimum and maximum total distance for the tour (in miles or km)

• There is a minimum and maximum distance for each flight between cities (‘hop’ – m/km)

• Flying directly between some cities is not permitted (for political, geographical, etc. reasons) even if the distance is between the maximum and minimum above

• The tour must have a minimum and maximum number of cities in each of the main continents:
o Europe
o Asia
o Africa
o Australasia
o South America
o North America

You may also wish to store a configuration file of pre-processed data such as a matrix of distances between cities, which cities belong to which continents, etc.)

4. Test and evaluate your solution under various conditions and, if heuristics are used, suggest performance guarantees where possible.

5. Produce a short report on 1-4.

And, here’s what you have to present:

a. Submit a brief report (1,000 words maximum) describing your approach to solving the problem, your background research into related optimisation problems, complexity analysis, software design and development, key algorithmic elements, results of testing and overall evaluation.

b. Demonstrate the operation of your package (including all of the above requirements) to your module leader and internal verifier/second-marker. Explain and defend your approach.

c. Submit your complete software solution to your module leader.

Assessment

To obtain a pass mark you must achieve all of the learning outcomes (see below)

A grade C will be awarded for a report showing limited awareness of some of the optimisation issues involved in the challenge and a software package that goes some way to providing an appropriate solution to the problem.

A grade B will be awarded for a report showing good awareness of most of the optimisation issuesinvolved in the challenge and a software package that goes a considerable way to providing an appropriate solution to the problem.

A grade A will be awarded for a report showing excellent awareness of all optimisation issues involved in the challenge and a software package that provides an appropriate solution to the problem in all cases.

The group demonstration will also serve as a form of ‘viva’ to determine the contribution each member of the group has made. A common mark may be awarded for the group as a whole or individual marks may be awarded to reflect levels of engagement.

Your attention is also drawn to the student handbook, which contains generalised guidelines for the grading of assessments.