NDLI: Optimal traversal planning in road networks with navigational constraints

Please wait, while we are loading the content...

The big-O of global visualization: challenges in scaling GIS to one billion users

Handling spatial data in distributed environments

Exploiting automatically inferred constraint-models for building identification in satellite imagery

Where were we: communities for sharing space-time trails

Multilevel object-oriented classification of quickbird images for urban population estimates

Quality-driven geospatial data integration

Optimal traversal planning in road networks with navigational constraints

Robust location search from text queries

TerraStream: from elevation data to watershed hierarchies

GeoModeler: tightly linking spatially-explicit models and data with a GIS for analysis and geovisualization

An object-oriented approach to the representation of spatiotemporal geographic features

Geometric algorithms for clearance based optimal path computation

Recognizing cars in aerial imagery to improve orthophotos

An interactive framework for raster data spatial joins

Modeling satellite image streams for change analysis

Dynamics-aware similarity of moving objects trajectories

The road extension model in the land change modeler for ecological sustainability of IDRISI

Automatic alignment of large-scale aerial rasters to road-maps

Evacuation route planning: scalable heuristics

STEWARD: architecture of a spatio-textual search engine

Multi-scale dual morse complexes for representing terrain morphology

GeoAnalytics visual inquiry and filtering tools in parallel coordinates plots

Approximate order-k Voronoi cells over positional streams

Optimal route selection with route planners: results of a desktop usability study

Dynamic storage balancing in a distributed spatial index

High-level web service for 3D building information visualization and analysis

Using fuzzy clustering methods for delineating urban housing submarkets

Hierarchical photo organization using geo-relevance

Proximity queries in large traffic networks

Semantically-assisted geospatial workflow design

Smugglers and border guards: the GeoStar project at RPI

A web-enabled extension of a spatio-temporal DBMS

Partition-based lazy updates for continuous queries over moving objects

Visual analytic services for geomarketing in spatial data infrastructures

Comparing global and interest point descriptors for similarity retrieval in remote sensed imagery

Near-real time motion analysis for APLIS 2007: a systems modeling perspective

A model for enriching trajectories with semantic geographical information

Environmental scenario search and visualization

Distributed computation of drainage basin delineations from uncertain digital elevation models

CLAM: concurrent location management for moving objects

Using object deputy database to realize multi-representation geographic information system

Randomization in traffic information sharing systems

Location anonymity in continuous location-based services

The definition and computation of trajectory and subtrajectory similarity

A middle-insertion algorithm for Markov chain simulation of soil layering

Efficient AKNN spatial network queries using the M-Tree

Analysis of implicit interest indicators for spatial data

Using geoprocessing specification as semantic metadata with GEOLEM

Pipelined spatial join processing for quadtree-based indexes

Constraints-preserving GML storage in object-relational databases

A parallel multi-scale region outlier mining algorithm for meteorological data

Development of web-based decision support system for field-based crop management

Cluster By: a new sql extension for spatial data aggregation

Cell-based generalization of 3D building groups with outlier management

Predicting future locations using clusters' centroids

Selective decompression of vector maps

Towards the automatic generation of web GIS

TS2-tree - an efficient similarity based organization for trajectory data

Spatial and temporal analysis of pedestrian egress behavior and efficiency

Scale, population, and spatial analysis: a methodological investigation

Topological maps from signals

An efficient framework for similarity query optimization

Defining edges on a round earth

Linear feature extraction using perceptual grouping and graph-cuts

On supervised density estimation techniques and their application to spatial data mining

Geospatial data qualities as web services performance metrics

A new simplification method for terrain model using discrete particle swarm optimization

Efficient KNN processing over moving objects with uncertain velocity

Optimal traversal planning in road networks with navigational constraints

Content Provider	ACM Digital Library
Author	Kazemi, Leyla Shahabi, Cyrus Vincent, Luc Sharifzadeh, Mehdi
Abstract	A frequent query in geospatial planning and decision making domains (e.g., emergency response, data acquisition, street cleaning), is to find an optimal traversal plan (OTP) that traverses an entire area (e.g., a city) by navigating through all its streets. The optimality is defined in terms of the time it takes to complete the traversal. This time depends on the number of times each street segment is traversed as well as the navigation time such as the time spent on changing direction at each intersection. While the problem roots in the classic problems of graph theory, real-world geospatial constraints of road network introduce new application-specific challenges. In this paper, we propose two algorithms to find OTP of a directed road network. Our greedy algorithm employs a classic graph traversal algorithm. During the traversal, it utilizes a set of heuristics at each intersection to minimize the total travel time. Our near-optimal algorithm, however, reduces an OTP problem to an Asymmetric Traveling Salesman Problem (ATSP) by extracting the dual graph of the original network in which each edge is represented by a graph node. Using an approximate solution for ATSP, our algorithm finds a near optimal answer. Our experiments using real-world road networks verify that our near-optimal algorithm outperforms the greedy algorithm in terms of the overall cost of its generated traversal by a factor of two, while its complexity is tolerable in real-world cases.
Starting Page	1
Ending Page	8
Page Count	8
File Format	PDF
ISBN	9781595939142
DOI	10.1145/1341012.1341038
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-11-07
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Gis applications Traversal planning Road-network Navigational constraints
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in