The ubiquity of mobile internet has led to the success of Spatial Crowdsourcing platforms like real-time taxi-hailing services, online food ordering services, etc. A critical component of such services is the task assignment algorithm employed for assigning the tasks to the workers of the platform. Our study of the literature in this domain shows that most of the task assignment algorithms developed for spatial crowdsourcing platforms address the problem from a utilitarian perspective, i.e., they optimise for only kind of entity. In contrast, we address the task assignment problem in spatial crowdsourcing platforms from an egalitarian perspective. An egalitarian approach aims to optimise the expectation of all entities involved. Specifically, we aim to minimise the waiting time for the customers and workers, while maximising the profit earned by the platform. To the best of our knowledge, ours is the only study that achieves this objective in a fully-online setting, with deadlines for both customers and workers. We propose two heuristic algorithms to solve the problem, and evaluate our algorithms on a real taxi-trips records dataset. Our algorithms exhibit a superior performance than the state-of-the-art algorithm for the fully-online bottleneck matching problem with deadlines, in terms of solution quality, running time and response time.

Globally, women are cautious when planning their routine travel routes. In a recent survey on street harassment, 82% of international respondents reported taking a different route to their destination than the conventional route due to fear of harassment. Such studies indicate an increasing need for `Safe Routing', especially in developing nations where the lack of infrastructure such as street lights, may contribute to higher crime rates. However, to the best of our knowledge, no state-of-the-art navigation system provides the option of `Safe Routing'. In this work, we propose a novel system that recommends "Safe Routes". Routes recommended by our system balance the conflicting requirements of increasing the safety and constraining the total length of the path to be within a reasonable limit (as desired by the user). From a theoretical perspective, the problem of `Safe Routing' can be modeled as the Arc Orienteering Problem, which is a well-known NP-hard combinatorial optimization problem.

Modern vehicles are increasingly being equipped with rich instrumentation that enables them to collect location aware data on a wide variety of travel related phenomena such as the real-world performance of engines and powertrain, driver preferences, context of the vehicle with respect to others nearby, and--indirectly--traffic on the transportation network itself. Combined with their increased access to the Internet, these connected vehicles are opening up vast opportunities to improve the safety, environmental friendliness, and the overall experience of urban travel. However, significant spatial computing challenges need to be addressed before we can realize the full potential of connected vehicles. This paper presents some of the open research questions under this theme from the perspectives of query processing, data science and data engineering.

Given a spatio-temporal network, a source, a destination, and a desired departure time interval, the All-departure-time Lagrangian Shortest Paths (ALSP) problem determines a set which includes the shortest path for every departure time in the given interval. ALSP is important for critical societal applications such as eco-routing. However, ALSP is computationally challenging due to the non-stationary ranking of the candidate paths across distinct departure-times. Current related work for reducing the redundant work, across consecutive departure-times sharing a common solution, exploits only partial information e.g., the earliest feasible arrival time of a path. In contrast, our approach uses all available information, e.g., the entire time series of arrival times for all departure-times. This allows elimination of all knowable redundant computation based on complete information available at hand. We operationalize this idea through the concept of critical-time-points (CTP), i.e., departure-times before which ranking among candidate paths cannot change. In our preliminary work, we proposed a CTP based forward search strategy. In this paper, we propose a CTP based temporal bi-directional search for the ALSP problem via a novel impromptu rendezvous termination condition. Theoretical and experimental analysis show that the proposed approach outperforms the related work approaches particularly when there are few critical-time-points.

Given a spatio-temporal network (STN) and a set of STN operations, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient method of storing STN data that minimizes disk I/O costs for given STN operations. The SSTN problem is important for many societal applications, such as surface and air transportation management systems. The problem is NP hard, and is challenging due to an inherently large data volume and novel semantics (e.g., Lagrangian reference frame). Related works rely on orthogonal partitioning approaches (e.g., snapshot and longitudinal) and incur excessive I/O costs when performing common STN queries. Our preliminary work proposed a non-orthogonal partitioning approach in which we optimized the LGetOneSuccessor() operation that retrieves a single successor for a given node on STN. In this paper, we provide a method to optimize the LGetAllSuccessors() operation, which retrieves all successors for a given node on a STN. This new approach uses the concept of a Lagrangian Family Set (LFS) to model data access patterns for STN queries. Experimental results using real-world road and flight traffic datasets demonstrate that the proposed approach outperforms prior work for LGetAllSuccessors() computation workloads.

Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in the event of natural disasters. Hurricane Rita and the recent tsunami revealed limitations of traditional approaches to provide emergency preparedness for evacuees and to predict the effects of evacuation route planning (ERP). Challenges arise during evacuations due to the spread of people over space and time and the multiple paths that can be taken to reach them; key assumptions such as stationary ranking of alternative routes and optimal substructure are violated in such situations. Algorithms for ERP were first developed by researchers in operations research and transportation science. However, these proved to have high computational complexity and did not scale well to large problems. Over the last decade, we developed a different approach, namely the Capacity Constrained Route Planner (CCRP), which generalizes shortest path algorithms by honoring capacity constraints and the spread of people over space and time. The CCRP uses time-aggregated graphs to reduce storage overhead and increase computational efficiency. Experimental evaluation and field use in Twin Cities Homeland Security scenarios demonstrated that CCRP is faster, more scalable, and easier to use than previous techniques. We also propose a novel scalable algorithm that exploits the spatial structure of transportation networks to accelerate routing algorithms for large network datasets. We evaluated our new approach for large-scale networks around downtown Minneapolis and riverside areas. This article summarizes experiences and lessons learned during the last decade in ERP and relates these to Professor Goodchild's contributions.