Garden routing

Towards a cost-based routing system for visitors to Kew Gardens.

This project is a collaborative project between the Royal Botanic Gardens, Kew, and the Department of Geomatic Engineering, at University College London.

Vidar Brekke produced this thesis for the M.Sc. Degree in Geographic Information Science (GIS), at UCL, working closely with Justin Moat and Steve Ruddy, Royal Botanic Gardens, Kew.

Example of route produced

This study set out to investigate a method of conducting least-cost path analysis, connecting multiple destinations in succession, to provide the core of a routing system for visitors to Kew Gardens. The proposed system was required to take input from visitors, in the form of what they wished to see, exit gate and mode of travel; to conduct processing in real-time.

A method to conduct the analysis is presented and data has been prepared for use and applied in analysis. The method suffers from very high runtime; typically 20 minutes for five destination points. In general, this is due to the ‘spread’ algorithm used being unsuitable for the application. It analyses the surface for all possible combinations in all directions, which means it guarantees the resulting route to be correct. Total accuracy of the resulting route is not necessary in this application, and a heuristic approach would be much more appropriate. However, it is crucial to search in all directions, because the next destination is not known prior to running the ‘costpath’ function. Although, the same applies to the identification of the next destination; it does not have to be accurate. J. Berry has developed a function to produce what he calls a ‘stepped accumulation surface’ implemented in his MapCalc GIS. This will undoubtedly have solved the challenge of automation, but is not likely to effect runtime significantly, given that he is using an adaptation of the same algorithm (personal communication).

ArcInfo is thus not a suitable environment for such implementations in its current state, although it can be conducted and also automated. Implementing such a system in a real application, potentially in kiosk based touch screen systems in the garden, is likely to be a very resource-demanding task. The original data will need consideration, in addition to the method. However, by altering the resolutions of the cost grids and fine tuning the relative costs it is possible to reduce runtime significantly. This will require considerable effort in resampling the cost grids to decrease resolution, and manually evaluating barriers. Chances are the method need consideration down to algorithmic level to reduce processing requirements down to acceptable levels.