Facility location problems aim to identify the best locations to set up new services. The 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, MAX-TIPS, is to minimize the maximum inconvenience faced by any user, while that of the second, AVG-TIPS, 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.

Optimal location queries identify the best locations to set up new facilities for providing service to its users. For several businesses such as fuel stations, cellphone base-stations, etc., placement queries require taking into account the mobility patterns (or trajectories) of the users. In this work, we formulate the TOPS (Trajectory-Aware Optimal Placement of Services) query that locates the best k sites on a road network for the prevailing user trajectories. The problem is NP-hard. The greedy approach, which is the state-of-the-art technique for this problem, is not scalable and practical for real urban-scale scenarios, primarily due to its high memory footprint beyond the capabilities of commodity machines. To overcome these challenges, we develop an indexing framework called NETCLUS that derives its power through an unique combination of FM sketches with network clustering. Empirical studies show that NETCLUS requires less than 100 s to answer the TOPS query on real datasets comprising of more than 250,000 sites and 120,000 trajectories.