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.
- 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:
- PY_12345678.py: The file containing the code for the assignment
- PDF_12345678.pdf: The file containing the written task
- 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.
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.
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.
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.
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:
- For each unvisited cruise ship, calculate how long it would take the support ship to intercept it from the support ship’s current position.
- Choose the cruise ship, i, which can be reached in the shortest amount of time.
- 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.
Your code should output two CSV files, one with the solution and another one with some key performance indicators (KPIs) of the solution.
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:
- Ship index: Index of the ship to be visited (remember that the first cruise ship should have index “0”)
- interception_x_coordinate: The x coordinate where the ship will be intercepted
- interception_y_coordinate: The y coordinate where the ship will be intercepted
- estimated_time_of_interception: The estimated time of the interception, i.e. the time elapsedsince the service ship leaves the dock until it reaches this ship.
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:
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).
2.3.Your written task
To complement your code submission, you must submit a PDF document alongside, consisting of the following three sections:
- 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:
- 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.
- 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.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipdue