Optimal Traversal Planning in Road Networks with Navigational Constraints
Venue
ACM GIS, ACM (2007)
Publication Year
2007
Authors
Leyla Kazemi, Cyrus Shahabi, Mehdi Sharifzadeh, Luc Vincent
BibTeX
Abstract
A frequent query in geospatial planning and decision making domains (e.g.,
emergency response, data acquisition, street cleaning), is to ¯nd an optimal
traversal plan (OTP) that traverses an entire area (e.g., a city) by navigating
through all its streets. The optimality is de¯ned 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-speci¯c challenges. In this paper, we propose two
algorithms to ¯nd 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.
