Microsoft Word – 文件1
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 Run the greedy heuristic; and
l Output the results.
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:
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, 𝑖, which can be reached in the shortest amount of time.
3. Visit cruise ship 𝑖 and update the positions of the ships in the task force.
4. 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).