  Finding a location for a new facility such that the facility attracts the
maximal number of customers is a challenging problem. Existing studies either
model customers as static sites and thus do not consider customer movement, or
they focus on theoretical aspects and do not provide solutions that are shown
empirically to be scalable. Given a road network, a set of existing facilities,
and a collection of customer route traversals, an optimal segment query returns
the optimal road network segment(s) for a new facility. We propose a practical
framework for computing this query, where each route traversal is assigned a
score that is distributed among the road segments covered by the route
according to a score distribution model. The query returns the road segment(s)
with the highest score. To achieve low latency, it is essential to prune the
very large search space. We propose two algorithms that adopt different
approaches to computing the query. Algorithm AUG uses graph augmentation, and
ITE uses iterative road-network partitioning. Empirical studies with real data
sets demonstrate that the algorithms are capable of offering high performance
in realistic settings.
