Python项目：The Ship Rendezvous Problem，利用贪心算法解决船舶交会问题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

1 Introduction

该项目是Msc授课型研究生作业，课程代码：MATH6005-33055-21-22，具有一定挑战性。

Your company has been contracted to provide a tool in Python to solve the Ship Rendezvous problem (SRP) to enable a cruise company to minimize 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 minimize 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 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.
   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.

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

Note that the speed of ship i (denoted by si) can be obtained from its velocity with the following equation:

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:

where the coefficients are obtained as follows:

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