Simple Trip Planner
This assignment is inspired by the problem of planning a European holiday by train, making optimal use of travel time. Your aim is to take each of a number of given train trips, e.g. London to Paris. Your journey must include a number of given trips, but may include additional trips to "link up" the cities in the trips you want to take. For simplicity, we assume that trains run frequently, so that you can focus on scheduling a journey that includes all of your specified trips and minimizes time takes to complete the journey (so you don't have to consider time lost waiting around for departures). The trips in your journey can be scheduled in any order, but your journey always starts in London. The aim is to minimize the total journey time, taking into account travel time and a transfer time in each city (except in London at the start of the journey).We assume that all cities can be reached by train directly from any other city, and that the travel time between any two cities is the same in either direction (so need only be specified in one direction). This means that the travel times between each pair of cities will be given. Furthermore, we assume the following "triangle inequality" on travel times: for any cities 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 trip planning problem. In your program 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. You should submit at least a UML class diagram used for the design of your program, i.e. not generated from code afterwards. All input will be a sequence of lines of the following form, and all cities and travel times will be declared before any trip requirements:
Transfer <time> <name>
# Transfer time is <time> minutes in city <name>
Time <time> <name1> <name2>
# Travel time is <time> minutes from city <name1> to city <name2>
Trip <name1> <name2>
# Journey requires a trip from <name1> to <name2>
Create all your Java source files in the default package. Call your main Java file TripPlanner.java. Read input from a file whose name is passed as an argument to the main method in the call to java TripPlanner 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 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 TripPlanner input.txt), use code such as:
Scanner sc = null;
try {
sc = new Scanner(new FileReader(args[0]));
# args[0] is the first command line argument } catch (FileNotFoundException e) {
} finally {
if (sc != null) {
sc.close();
}
}
Sample Input:
For example, the following input has five cities and four required trips as indicated. This means that 10 travel times between cities need to be specified (which can be given in any order). The format and meaning of the input is as follows (comments are for explanation and should not appear in the actual input):
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 path. 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.
Comments
Post a Comment