  Facility location problems aim to identify the best locations to set up new
services. Majority of the existing works typically assume that the users are
static. However, there exists a wide array of services such as fuel stations,
ATMs, food joints, etc., that are widely accessed by mobile users besides the
static ones. Such trajectory-aware services should, therefore, factor in the
trajectories of its users rather than simply their static locations. In this
work, we introduce the problem of optimal placement of facility locations for
such trajectory-aware services that minimize the user inconvenience. The
inconvenience of a user is the extra distance traveled by her from her regular
path to avail a service. We call this the TIPS problem (Trajectory-aware
Inconvenience-minimizing Placement of Services) and consider two variants of
it. The goal of the first variant, MAXTIPS, is to minimize the maximum
inconvenience faced by any user, while that of the second, AVGTIPS, is to
minimize the average inconvenience over all the users. We show that both these
problems are NP-hard, and propose multiple efficient heuristics to solve them.
Empirical evaluation on real urban-scale road networks validate the efficiency
and effectiveness of the proposed heuristics.
