Visualisation of branch and bound search tree for TRACS II

10,000 3,000

Topic Description


The aim of the subject of this report is to provide a tool for post-hoc visualisation of the branch & bound search tree generated by the TRACS II Driver-Scheduling System (DSS). A visualisation tool is required to help the developers of TRACS II analyse the branch & bound search used within TRACS II’s solution process.
TRACS II is a drivers scheduling system for scheduling drivers; a task conducted as part of operating a public transport network. A branch & bound search is conducted as part of TRACS II’s schedule selection process. Details of the process are output as a log file, which can contain may hundreds of pages of text. The branch & bound search tree analysis tool, takes this data and produces a visualisation of the branch and bound tree it describes. Trees may contain thousands of nodes, which the tool must enable the user to analyse The tool was developed using an incremental process model with the increments developing a method for extracting the tree’s data from the log file, visualising the tree, and packaging the visualisation within a graphical user interface.
The tool has been designed using an object-oriented approach and implemented in Java. It has adhered to a three sets of guidelines, which have provided excellent advice on data visualisation, user interface design and usability. The design of the data extraction method uses the structure of the tree data in the log file. The visualisation represents the tree as a graph, plotting its progression toward feasible solutions as the search develops. The user interface packages the visualisation in a graphical user interface containing a directly
interactive panel on which the graph is displayed, side windows containing details of the tree,
the most recently viewed node, and the most recently selected path in the tree, and menus
with which the user can interact with the graph. The interface enables the user to perform
tasks such as pruning the tree, selecting paths, and zooming. The graph can also be saved both
as an image and as a restorable file.
The tool has been successfully tested and evaluated by the user and will now be used by the developers of TRACS II to analyse the rules and strategies used within the branch & bound search and to improve user default settings.