Course: MATH6005-Introduction to Python and MATH6181-Python & Forecasting
Semester: 2021:2022
March 22, 2022
Final Assignment: Part 2 (week 8)
Rules for the Final Assignment: Part 2 (week 8) solution
• You will upload, on Blackboard, one single file.
• The file name, with all functions, must be in the format: .py, e.g.:
fdoo1r22.py. This file is the Final Assignment: Part 2 (week 8) solution that will be
uploaded on Blackboard.
• All functions must follow the prototypes, i.e., they must have the name specified, have the
input(s) set, and output the variables in the order specified in the prototypes.
• No partial credit will be given if the function is not working correctly, i.e., due to syntax
error, neglect to follow the prototype, etc..
• Only the functions must be in the upload file; any auxiliary or debugging code must be
removed of the upload file.
• Please include comments in your code to explain how it works. Fail to comment on your
code will result in 10 points reduction on your final assignment mark. Comment every
line of your code.
• You can use any function/package/library, including NumPy, Pandas, etc.
• The solution must have only functions. Do not define any function within another function.
• A template solution file is available on Blackboard.
1
Faculty of Social Sciences
School of Mathematical Sciences
The Ship Rendezvous Problem
1 Introduction
Your company has been contracted to provide a tool in Python to solve the Ship Rendezvous
problem (SRP) to enable a cruise company to minimise the time it takes for the support ship to
visit each of the cruise ships in the fleet.
The support ship must visit each of the n cruise ships exactly once and then return to the
port (where it started). The support ship travels at a constant speed and changes direction with
negligible time. Each cruise ship moves at a constant velocity (i.e. speed and direction). The
objective is to minimise the total time taken to visit all the cruise ships (i.e. the time taken
to reach the final ship).
This problem is considered in 2-dimensional (2D) Euclidean space. A problem instance is defined by specifying the starting (x, y) coordinates for all ships (including the support ship), the
velocity of the support ship, and the velocity of the cruise ships.
Note that it is certain that the SRP has a finite solution if the support ship is faster than all
other ships in the fleet. However, it is very likely (but not certain) that the SRP will not have a
complete solution (one where all the cruise ships are visited) if one or more of the cruise ships are
faster than the support ship.
2 Your Python Task
You must implement the greedy heuristic for the 2D Euclidean SRP in Python. Your program
must perform the following tasks:
• Read the data from a CSV file (a sample data file is provided on Blackboard sample_srp_data.csv);
• Run the greedy heuristic against the problem instance to obtain a solution;
• Output a list of indexes of unvisited cruise ships, a list of indexes of the visited cruise ships,
and the total time to visit all visitable cruise ships.
Greedy Heuristic for the SRP
A simple way of finding a solution to the SRP is to use a greedy heuristic. The greedy heuristic
works as follows
1. For each unvisited cruise ship, calculate how long it would take the support ship to intercept
it from the support ship’s current position.
2. Choose the cruise ship, i, which can be reached in the shortest amount of time.
3. Visit cruise ship i and update the positions of the ships in the fleet.
4. Return to 1 if there are any unvisited cruise ships that can be reached by the support ship.
2
Faculty of Social Sciences
School of Mathematical Sciences
In order to make the heuristic deterministic (i.e. to guarantee the same result each time it is run
on the same problem instance) you must specify how ties in Step 2 are broken. If there is a tie,
the algorithm should choose to visit the ship with the smallest index (for example, if ships 5 and
7 are tied, ship 5 should be chosen in preference to ship 7).
The Technical Appendix (at the end of this document) provides details on how to calculate
intercept times.
Function prototypes
import pandas as pd
def read_srp_input_data ( csv_file ):
’’’
function description
’’’
input_data =pd . read_csv ( csv_file )
return input_data
• The function must use the input variable csv_file to read the TXT file, inside of the
function. You cannot use a fixed path file. If the function does not read the file using the
input variable csv_file no partial credit will be given.
def findPath ( input_data ):
’’’
function description
’’’
unvisited_index = [] # It must be a LIST . It cannot be a tuple nor NumPy array .
visited_path = [] # It must be a LIST . It cannot be a tuple nor NumPy array .
total_time = 0 # it must be a float .
return unvisited_index , visited_path , total_time
• The function outputs must be in the order as specified on the prototype. If the function
outputs are not in the set order no partial credit will be given.
Example: There are 5 cruise ships on the fleet. Suppose that, using the Greedy Heuristic, the
support ship can only visit 3 of them with the indexes 1, 2, 4 (e.g. the 2 remained cruise ships with
the indexes 3, 5 cannot be visited). Remember that support ship should have index "0" and the
first cruise ship has index "1" and so on. Then an example for a solution looks like:
[3 , 5], [2 ,4 ,1], 45 .3
which mean that unvisited_index = [3,5], visited_path = [2,4,1] and total_time = 45.3. The
visited_path = [2,4,1] means that the support ship will visit the cruise ship with index 2 first, and
then the cruise ship with index 4, and finally the cruise ship with index 1.
Please, the debugging/testing code must not be in your solution file
that will be uploaded on Blackboard.
3
Faculty of Social Sciences
School of Mathematical Sciences
Advice on writing the code
Make sure you follow the guidelines below when writing your code:
• You can (and are encouraged to) create new functions if needed. These must follow the good
coding practices we have taught in the lectures and labs. However, your submission must
include all the functions provided in the template, with the exact same names provided in
the template.
• Your code should implement exactly the algorithm described above. Do not use an alternative. If you use a different algorithm (even if the algorithm solves the problem correctly and
the results seem better) your assignment will be marked as incorrect.
• We will test your code against an unseen set of problem instances. We recommend that you
test your algorithm and make sure that your code returns the expected solutions for different
scenarios. To help you do this, you may create and test new CSV files for which you think
you know the expected behaviour.
• We will only use correct input CSV files to test your code. The assignment does not ask
you to include logic to handle non-numeric or incorrect CSV files. There are no extra marks
available for including this functionality.
4
Faculty of Social Sciences
School of Mathematical Sciences
Technical Appendix
This appendix contains some technical information to help you solve the proposed problem in the
assignment. Please, pay attention to these formula and specifications to ensure that your algorithm
produces the correct results.
Notation
We denote the starting coordinates of the support ship by (X0; Y0) and its speed by S. We consider
the ship i in the task force, where 1 ≤ i ≤ n. We denote its starting coordinates by (xi0; yi0).
Its velocity is split into x-component and y-component, vix and viy , respectively. Therefore the
position of ship i at time t > 0 is given by
(xit; yit) = (xi0 + tvix; yi0 + tviy)
Note that the speed of ship i (denoted by si) can be obtained from its velocity with the following
equation:
si = q v2
ix + v2
iy.
Calculating intercept times
To calculate intercept times, it is simplest to update the position of the ships at every step, so
that (X0; Y0) represents the current coordinates of the support ship and (xi0; yi0) represents the
current coordinates of ship i for 1 ≤ i ≤ n. Then the time, T, taken for the support ship to move
from its current position and intercept ship i is found by finding the smallest positive root of the
quadratic equation:
aT2 + bT + c = 0
where the coefficients are obtained as follows:
a = v2
ix + v2
iy − S2 b = 2 ((xi0 − X0)vix + (yi0 − Y0)viy) c = (xi0 − X0)2 + (yi0 − Y0)2.
Input Data
The input data for each problem instance will be presented in a comma separated value (CSV)
file. A correctly-formatted input file consists of N rows of data, where N ≥ 2. Row 1 corresponds
to the support ship, and the remaining rows (i.e. rows 2; ...; N) correspond to the ships to be
intercepted. Each row contains five pieces of information in the following order:
• Ship name/description (text).
• Start x-coordinate (decimal number).
• Start y-coordinate (decimal number).
• Velocity x-component (decimal number).
• Velocity y-component (decimal number).