MATH6005 2018-19

MATH6005 Final Assignment

1. Instructions

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.

代写MATH6005作业

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. 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.

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):

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

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:

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:

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.

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. A paragraph (between 250 – 500 words) describing a situation where you think the proposed

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 Functionality when it runs (correct results and output);

o User-friendliness when running (robustness, error-handling);

o Design and maintainability

o Readability and reusability (eg. clearly defined and well commented functions,

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.

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:

(2)

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:

aT2 + bT + c = 0 (3)

where the coefficients are obtained as follows:

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

 

因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱： 

微信：codinghelp