This assignment is inspired by the problem of scheduling a shipping plan for
one ship to deliver cargo. Your aim is to schedule an optimal plan for the
ship to complete a set of shipments, where only one shipment is carried at a
time. While all of the required shipments need to be part of the final plan,
the plan may contain trips where the ship does not carry any cargo, but
needs to travel somewhere else to pick up a new shipment. The ship requires
time for refuelling before undertaking each trip (whether with or without
cargo).
More precisely, you will be given a number of distinct specified shipments
(e.g. Shanghai to Sydney) that have to be made. The shipments can be
scheduled in any order, but the ship always starts in Sydney (and can finish
anywhere). The aim is to minimize the total time for the plan, taking into
account travel time between ports and a refuelling time before each trip. For
simplicity, the name of each port will be just one word. Assume also that the
travel time between any two ports is the same in either direction (so need
only be specified in one direction) and that the travel time for all possible
trips between ports is specified. Furthermore, assume the following "triangle
inequality" on travel times: for any ports A, B and C, the travel time from A
to C is always less than or equal to the travel time from A to B plus the
travel time from B to C.
In this assignment, you will implement an A* search procedure for the
shipping plan problem. In your design, make use of the Strategy pattern
to supply a heuristic to the search procedure, and don't forget to ensure that
your heuristic is admissible. Implementing A* is the main requirement
for this assignment, so that your program is guaranteed to produce an
optimal solution. If your program does not always produce an optimal
solution, then it is wrong.
Assessment will be based on the design of your program in addition to
correctness and efficiency. You should submit at least a UML class diagram
used for the design of your program, i.e. not generated from code afterwards.
You should also include a runtime complexity analysis of your heuristic in
the comments of your ShipmentPlanner class.
All input will be a sequence of lines of the following form, and all ports and
travel times will be declared before any shipment requirements:
Refuelling
# Refuelling time is days in port
Time
# Travel time is days from port
to port
Shipment
# Shipment is required from to
Create all your Java source files in the default package. Call your main
Java file ShipmentPlanner.java. Read input from a file whose name
is passed as an argument to the main method in the call tojava
ShipmentPlanner and print output to System.out. For machine
marking, the output will be redirected to a text file that will be compared to
the expected output (so do not print out extra spaces, etc.) and remember to
close the input file. For the purposes of machine marking, problems will
be used for which there is only one optimal solution, though in the case
of multiple optimal solutions, your program should produce one of
them.
To read input from a text file (whose name should be passed as a command
line argument to java, e.g. java ShipmentPlanner input.txt), use
code such as:
Scanner sc = null;
try
{
sc = new Scanner(new File(args[0])); // args[0] is the first
command line argument
// Read input from the scanner here
}
catch (FileNotFoundException e)
{
System.out.println(e.getMessage());
}
finally
{
if (sc != null) sc.close();
}
Sample Input
Below is an example of the input form. and meaning. Note that you will have
to submit at least three input test files with your assignment. These test files
should include one or more comments to specify what scenario is being
tested. However, the following sample input includes many comments
added only to explain the input format; your input test files do not need to
contain this many comments.
Refuelling 6 Sydney # Refuelling time is
6 days in Sydney
Refuelling 4 Shanghai # Refuelling time is
4 days in Shanghai
Refuelling 4 Singapore # Refuelling time is
4 days in Singapore
Refuelling 6 Vancouver # Refuelling time is
6 days in Vancouver
Refuelling 8 Manila # Refuelling time is
8 days in Manila
Time 18 Sydney Shanghai # Travel time is 18 days
from Sydney to Shanghai
Time 24 Sydney Singapore # Travel time is 24 days
from Sydney to Singapore
Time 18 Sydney Vancouver # Travel time is 18 days
from Sydney to Vancouver
Time 10 Sydney Manila # Travel time is 10 days
from Sydney to Manila
Time 10 Shanghai Singapore # Travel time is 10 days
from Shanghai to Singapore
Time 24 Shanghai Vancouver # Travel time is 24 days
from Shanghai to Vancouver
Time 12 Shanghai Manila # Travel time is 12 days
from Shanghai to Manila
Time 24 Singapore Vancouver # Travel time is 24 days
from Singapore to Vancouver
Time 22 Singapore Manila # Travel time is 22 days
from Singapore to Manila
Time 20 Vancouver Manila # Travel time is 20 days
from Vancouver to Manila
Shipment Singapore Vancouver # Shipment is required
from Singapore to Vancouver
Shipment Shanghai Singapore # Shipment is required
from Shanghai to Singapore
Shipment Sydney Vancouver # Shipment is required
from Sydney to Vancouver
Shipment Sydney Manila # Shipment is required
from Sydney to Manila
Sample Output
The above example does not have a unique optimal solution. One valid
output corresponding to the above input is as follows. The first line in the
output should give the number of nodes n expanded in your search, the
number of nodes taken off the queue, which will vary according to the
heuristic used. The second line of the output should give the cost of the
solution found as an integer, which is the total time taken, and should be the
same regardless of the heuristic and the solution. The remainder of the
output should give a sequence of trips that make up an optimal solution. If
your program produces a different optimal solution from the one shown
(with the same cost) then it is correct.
n nodes expanded
cost = 126
Ship Sydney to Manila
Ship Manila to Shanghai
Ship Shanghai to Singapore
Ship Singapore to Vancouver
Ship Vancouver to Sydney
Ship Sydney to Vancouver
In particular, for this problem, the following output is also correct.
n nodes expanded
cost = 126
Ship Sydney to Vancouver
Ship Vancouver to Sydney
Ship Sydney to Manila
Ship Manila to Shanghai
Ship Shanghai to Singapore
Ship Singapore to Vancouver