Scientific Program > Talks by Speaker > Lum Oliver

An Open Source Tool for Generating Arc Routing Instances from Real Street Data
Oliver Lum  1@  , Bruce Golden  2@  , Edward Wasil  3@  
1 : University of Maryland - Applied Mathematics and Scientific Computation  (AMSC)  -  Website
2 : University of Maryland - Department of Decision, Operations and Information Technologies Robert H. Smith School of Business
College Park, MD 20742-1815 -  United States
3 : American University - Department of Information Technology

Optimization algorithms for vehicle and arc routing problems often rely on a set of benchmark problems to validate and demonstrate performance. Ideally, these benchmark problems are reflective of the real-world street networks on which practitioners will be solving the problem. However, with few exceptions, these instances are artificially generated to try and approximate real networks. Even if special attention is paid to ensure that relevant parameters fall within practical ranges, there is significant variety between street networks of different cities, for example. Open Street Maps is an open, user-driven map database which allows software developers to query it for map data. We develop and present a software tool that allows users to generate arc routing problem instances directly from this map data. The tool allows the ability to curate (prune edges or vertices or mark them as required) the resulting network either by hand, or according to configurable parameters. The instances generated in the tool can then be exported for use by researchers. In addition, the tool offers a visualization capability which can produce images of routes overlaid on the graph.

Online user: 1 RSS Feed