Data-driven discrete geofence design using binary quadratic programming

Abstract

Abstract Geofences have attracted significant attention in the design of spatial and virtual regions for managing and triggering spatiotemporal events; for example, content providers can trigger spatiotemporal events through mobile devices. Traditionally, geofences were hand-crafted by providers. In addition to the hand-crafted approach, recent advances in collecting human mobility data through mobile devices can accelerate the automated, data-driven design of geofences, also known as the geofence design problem. Previous approaches assume circular shapes; thus, their flexibility is insufficient, and they are mainly suited to geofence-based applications over large areas at coarse resolutions. A challenge with using circular geofences in urban and high-resolution areas is that they often overlap and fail to align with political district boundaries and road segments, such as one-way streets and median barriers. This study proposes a discrete geofence design formulation that represents a geofence as selected spatial cells and optimizes the selection by binary quadratic programming. Although binary quadratic programming problems are computationally hard, modern optimization solvers can often find practical solutions. Furthermore, expressing the model in a quadratic binary form provides a computational interface to specialized quadratic and heuristic solvers, including annealing-based approaches. We then develop and compare different formulation methods to extract discrete geofences. In our numerical evaluation, we validate the formulation using a real-world GeoLife case study and synthetic multiple-POI scenarios, and compare it with circular geofences and density-based top- k , connected top- k , and DBSCAN + alpha-shape baselines. The evaluation uses user-level coverage ratio, user-point-level coverage ratio, shape connectivity, POI-aware separation, and runtime and scalability. The results show that the proposed formulation can generate area-controlled, non-circular geofences that better reflect mobility patterns than circular baselines, while the computational cost and the choice of discretization level remain important practical limitations.