Ship Rendezvous Problem 2. The Problem
Your company has been contracted to provide a tool in Excel to solve the Ship Rendezvous problem (SRP) to enable P&Q cruises 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. 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 task force. However, it is very likely (but not certain) that the SRP has no solution if one or more of the cruise ships is faster than the support ship.
2.2. Your VBA task
You must implement the greedy heuristic for the 2D Euclidean SRP in a VBA project in
Excel. Additional information is given in the Technical Document.
Note that your program must have a single user interface so that the user can: l Read data from a comma-separated (CSV) file (see sample data file);
l Validate the data (recognise if there are any problems with the data);
l Runthegreedyheuristic;and
l Outputtheresults. Greedy Heuristic for the SRP
A simple way of finding a solution to the SRP is to use a greedy heuristic if the support ship is faster than all the cruise ships. This guarantees a solution, but it is very unlikely to be optimal.
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, 𝑖, which can be reached in the shortest amount of time.
- Visit cruise ship 𝑖 and update the positions of the ships in the task force.
- Return to 1 if there are unvisited cruise ships.
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. The most commonly used tie-breaker is to choose the ship with the smallest index (for
example, if ships 5 and 7 can be reached in the same amount of time, ship 5 should be chosen in preference to ship 7).
The Technical Document provides details on how to calculate intercept times.
Getting Started…
One of your colleagues started forming a solution in the Excel workbook ShipRendezvous_Starter.xls and this may be useful as a starting point. The code needs extending – search for the phrase “\TO DO” in the VBA project. You are welcome to use as much or as little of ShipRendezvous_Starter.xls.
Your colleague also created some test data files that you might find useful for testing your code. User error is common when entering data and you are strongly recommended to create your own data sets to test the data validation in your program and to test the results of your algorithm, ensuring they match solutions derived independently (e.g. by hand).
2.3. Your written task
To convince users that the tool you have developed functions as necessary, you are required to produce a logbook which contains the following.
l User guide section (worth 10%). The user guide should explain to an Excel-literate (but not VBA-literate) user how to use the software from the point of opening the workbook. This document should be a concise guide, bearing in mind that a well- designed user interface which follows a clear and natural workflow needs little explanation.
n Screenshots are not essential, but may be useful.
n Assumptions and limitations must be specified.
n Warnings and/or messages given by the program must be explained. It is not essential, but you might want to extend this to be a section on how to troubleshoot the software when things go wrong.
l Technical section (worth 10%). The technical documentation should describe the structure and components of the VBA project to a VBA-literate reader so that it can be maintained and enhanced in the future.
n Concisely describe the purpose of each file (module, class, UserForm) in the VBA project.
n Provide a brief description of the purpose of each routine, method, property and event. (This should be no more than a few sentences for each; often one will suffice.)
n An explanation of how the files and the main elements of the program are linked together – what is the structure of the code, when is a routine called and from where?
Remember: Option Explicit must be included in all the files used. Otherwise, a zero mark will be given for the electronic submission!
Since Object-Oriented Programming is one of the most important topics in MATH6005, you are asked to make use of classes. A submission can only obtain a Distinction if your program contains at least one proper class with appropriate data and methods. The program should make significant use of this class (instead of just design it and leave it there). However, if you aim for a Pass/Merit, it is possible to avoid use of classes (but instead use UDT or a number of arrays).