Using real-world geospatial data with evolutionary algorithms.

Urquhart, Neil B (2010) Using real-world geospatial data with evolutionary algorithms. In: Universities' Transport Study Group, 5th-7th January 2010, Plymouth, UK. (Unpublished)

Full text not available from this repository. (Request a copy)


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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: geo-spatial data; evolutionary algorithms; routing services; logistics-based scheduling;
University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Computing
Dewey Decimal Subjects: 000 Computer science, information & general works > 000 Computer science, knowledge & systems > 006 Special Computer Methods > 006.3 Artificial intelligence
300 Social sciences > 380 Commerce, communications & transportation > 388 Transportation; ground transportation
Library of Congress Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Item ID: 3706
Depositing User: Computing Research
Date Deposited: 19 Mar 2010 16:32
Last Modified: 27 Jul 2011 15:35

Actions (login required)

View Item View Item

Edinburgh Napier University is a registered Scottish charity. Registration number SC018373