MATH6005
2018-19
1. Instructions
MATH6005 Final Assignment
Your Assignment 3 should consist of three files (a “.py” file, a “.pdf” file and a “.csv” file) submitted electronically via Blackboard. This assignment will count for 80% of the assessment for MATH6005. The deadline is 16:00 on Friday 29th March 2019. This applies to all files. The deadline is strict. Normal penalties for late assignment apply: 10% of your marks are deducted per working day late, with no submission permitted after 5 days.
Ensure that you take frequent and multiple backups of your work, since excuses concerning lost or corrupted files will not be treated sympathetically. Please, verify that you follow all instructions carefully and your work has been uploaded successfully.
1.1.Electronic submission
The code should be all written in a single “.py” file.
Please, name all your files with the following pattern: File extension, underscore, student
number. For example, a student with student number 12345678 must submit only the following three files:
1. PY_12345678.py: The file containing the code for the assignment
2. PDF_12345678.pdf: The file containing the written task
3. CSV_12345678.csv: The CSV file supporting the written task (details in Section 2.3)
Ensure that your name does not appear anywhere in your submission.
Your files should be submitted via Blackboard by the deadline above.
Please also keep a copy of your project in case there is a problem with the file you submit.
1.2.Collaboration, plagiarism and cheating
You should work on your own when carrying out the assignment.
Please refresh your memory of the University’s code on academic integrity, see University
of Southampton Calendar 2018/19 .
Please note that allowing somebody else to copy your work is counted as plagiarism: it
carries the same penalty as copying work.
Submissions will be strictly tested for plagiarism with specialised software and penalties
strictly enforced.
1.3.Purpose of assessment
The purpose of this assignment is to assess your ability to:
Write a structured computer program to solve a given problem.
Demonstrate good programming practice, as discussed in the course notes, lectures and
computer workshops.
Demonstrate good and correct use of Python.
Understand how an algorithm works and hypothesise on how it could behave on different
data
Although the focus of this assessment is on programming skills and not on report writing, your written task should be sensibly formatted (including page numbers and section headings) and well presented.
1
MATH6005 2018-19
2. Content: The Ship Rendezvous Problem
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.
2.1.Introduction
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 speed 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.2.Your Python Task
You must implement the greedy heuristic for the 2D Euclidean SRP in Python. To help you with this task, we are providing you with the following support file in Blackboard:
• assignment_3_student.py: This file contains a basic structure for the assignment. You must use this file as a template to start your assignment, and use the variables and functions provided. These functions will be used to mark your assignment. However, you are expected to define other functions and variables when needed. You must rename this file before submitting it, as per the instructions above.
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 the resulting path to a CSV file.
Output key performance indicators of the solution to a second CSV file.
2
MATH6005 2018-19
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. Visitcruiseshipiandupdatethepositionsoftheshipsinthefleet.
4. Return to 1 if there are any unvisited cruise ships that can be reached by the support ship.
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. As it is anticipated that there might be the worst weather in the north, the ship with the highest y-coordinate should be visited first. If there is still a tie, the algorithm should choose to visit next 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.
Output format
Your code should output two CSV files, one with the solution and another one with some key performance indicators (KPIs) of the solution.
Solution file:
Should be named: “solution.csv”
This would be used by the support ship to determine their schedule. It should contain one line per cruise ship (in the visiting order), and the following columns:
1. Ship index: Index of the ship to be visited (remember that the first cruise ship should have index “0”)
2. interception_x_coordinate: The x coordinate where the ship will be intercepted
3. interception_y_coordinate: The y coordinate where the ship will be intercepted
4. estimated_time_of_interception: The estimated time of the interception, i.e. the time elapsed
since the service ship leaves the dock until it reaches this ship.
An example solution for an instance with only two ships would be the following table (headers must be included):
The file should not include coordinates or arrival times to / from the port, only to the visited cruise ships.
Note: If it is not possible to intercept some ships (e.g. they go faster than the support ship), their rows should appear after the visited ships and they should have a -1 in all columns (including the index column). For example, if the previous instance had another ship (with index 2) that could not be reached by the support ship, the solution file should look like the table below:
Ship_index
interception_x_coordinate
interception_y_coordinate
estimated_time_of_interception
1
7.30
6.31
5.63
0
5.96
2.30
12.31
3
MATH6005 2018-19
Ship_index
interception_x_coordinate
interception_y_coordinate
estimated_time_of_interception
1
7.30
6.31
5.63
0
5.96
2.30
12.31
-1
-1
-1
-1
KPI file:
Should be named: “kpi.csv”
The KPI file should be a CSV file with a single column with values for the following quantities:
The number of cruise ships visited
The total time taken by the service ship since it leaves the port until it returns to it.
The maximum time a cruise ship has to wait before it receives the visit of the service ship
The highest y-coordinate the service ship has to visit during the trip
The furthest away from the port the service ship has to go (counted as Euclidean distance
from its initial location)
The average time the cruise ships have to wait to be intercepted
Note: If one or more cruise ships cannot be intercepted, the KPIs should be adjusted to reflect the information about the visited ships only (e.g. average waiting time of the visited ships only). If this information is not available (e.g. if no ships can be visited, it is not possible to find out their average intercept time), the affected KPIs should be replaced with a -1, so the resulting file always contains one column and six rows.
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.
If you include comments in your code to explain workings then these must be in understandable English.
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.
The support ship speed is constant. This speed is stored in the x-speed column of the CSV file. The y-speed column for the support ship should be ignored (it is set to zero in the supplied example so that the CSV file can be read into a Numpy array).
4
MATH6005 2018-19
2.3.Your written task
To complement your code submission, you must submit a PDF document alongside, consisting of the following three sections:
1. A table showing the function names of your code and a short description of what the function does and when it is called. See an example below for one of the functions provided by the template file:
2. A plot showing the path planned by your algorithm for the service ship, based on your solution for the test data. The code to produce this image does not need to be part of your assignment and will not be marked.
3. Aparagraph(between250–500words)describingasituationwhereyouthinktheproposed algorithm would provide a feasible solution (i.e. it is not an impossible problem) but have a particularly bad performance (i.e. its solution would be very far from the optimal). You must also submit a CSV file with your proposed example. The CSV should be a valid input for the program (i.e. you should be able to run it with your code), and named as described in Section 1.1.
3. Marking Scheme
The first 80% of the marks available for this assignment are for the Python project and the remaining 20% of the marks are available for the written task.
Marks for the Python project (80%) will be awarded on the basis of: o Functionalitywhenitruns(correctresultsandoutput);
o User-friendlinesswhenrunning(robustness,error-handling); o Designandmaintainability
o Readabilityandreusability(eg.clearlydefinedandwellcommentedfunctions, compliance with the style guideline PEP8, etc.)
Marks for the written task (20%) will be awarded on the basis of: o Accuracy;
o Completeness o Presentation.
Function
Description
read_srp_input_data(csvfile)
Reads the csv file “csvfile” and returns a Numpy matrix with its contents. It is called at the beginning to read the data into the program.
5
MATH6005 Final Assignment 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.
A Notation
Let us denote the starting coordinates of the support ship by (X0, Y0) and its speed by S. Let us now consider the ship i in the task force, where 0 ≤ i < n. We denote its starting coordinates by (xi0, yi0). Its velocity is split into x− and y−components, vix and viy , respectively. Therefore the position of ship i at time t > 0 is given by
(xit, yit) = (xi0 + tvix, yi0 + tviy) (1) Note that the speed of ship i (denoted by si) can be obtained from its velocity
with the following equation:
si=v2 +v2 (2) ix iy
B 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 0 ≤ 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:
aT 2 + bT + c = 0 (3) where the coefficients are obtained as follows:
a=v2 +v2 −S2 (4) ix iy
b = 2(vix(xi0 − X0) + viy(yi0 − Y0)) (5) c = (xi0 −X0)2 +(yi0 −Y0)2 (6)
i
C 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).
ii