Python辅导 | MATH6005 Final Assignment

本次英国CS辅导为数学编程相关，主要是完成一个船舶交会问题（SRP）的求解，包括代码和写作两个大的部分。

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

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:

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.

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:

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:

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:

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:

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:

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:

2.3.Your written task

To complement your code submission, you must submit a PDF document alongside, consisting of the following three sections: