Using real-world geospatial data with evolutionary algorithms.

Urquhart, Neil B

Abstract

Developments in the field of Geographical Information Systems (GIS) have increased the availability of on-line road network data and associated routing services. The ability to integrate such data and services into web sites and other business systems provides opportunities to further optimise logistics-based scheduling and routing problems. Evolutionary Algorithms (EAs) are one possible technique for solving such problems. EAs are able to produce robust solutions to benchmark problems, but such problems are frequently based on simplistic Euclidean distances. During the evolutionary process EAs will query the data frequently, many of these queries being used to evaluate what transpire to be sub-optimal solutions. The authors’ experience suggests that querying of such on-line GIS systems will incur a time penalty and, may also incur a financial cost per query. The storing, or caching, of routing data or the underlying mapping data is not normally permitted by the suppliers of such data, instead it must be reloaded from the data source each time it is required. The author examines the potential to utilise a mixture of GIS-based routing and estimated distances when using an EA to solve a real-world travel planning problem. Experiments within this paper investigate the extent to which Euclidean based calculations may be substituted for GIS queries without determent to the final problem solution. Initial experiments examine the relative differences between journey lengths when using both types of calculation. Experiments with the EA compare two approaches; that of switching from estimated to actual distances during the run and that of evaluating two sub populations using the differing methods. Full conclusions are presented that show it is possible to reduce the calls to the GIS without adversely affecting the final solution. It is hoped that the results presented will increase the adoption of EA based techniques when solving real-world scheduling and routing problems.

Citation

Urquhart, N. B. (2010, January). Using real-world geospatial data with evolutionary algorithms. Paper presented at Universities' Transport Study Group

• Presentation Conference Type: Conference Paper (unpublished)
• Conference Name: Universities' Transport Study Group
• Start Date: Jan 5, 2010
• End Date: Jan 7, 2010
• Publication Date: 2010-01
• Deposit Date: Mar 19, 2010
• Peer Reviewed: Not Peer Reviewed
• Keywords: geo-spatial data; evolutionary algorithms; routing services; logistics-based scheduling
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/3706