SIGSPATIAL CUP '19

Distance-Aware Competitive Spatiotemporal Searching Using Spatiotemporal Resource Matrix Factorization

Authors

Joon-Seok Kim (George Mason University), Dieter Pfoser (George Mason University), Andreas Züfle (George Mason University)

Abstract

Congested traffic wastes billions of liters of fuel and is a significant contributor to Green House Gas (GHG) emissions. Although convenient, ride sharing services such as Uber and Lyft are becoming a significant contributor to these emissions not only because of added traffic but by spending time on the road while waiting for passengers. To help improve the impact of ride sharing, we propose an algorithm to optimize the efficiency of drivers searching for customers. In our model, the main goal is to direct drivers represented as idle agents, i.e., not currently assigned a customer or resource, to locations where we predict new resources to appear. Our approach uses non-negative matrix factorization (NMF) to model and predict the spatio-temporal distributions of resources. To choose destinations for idle agents, we employ a greedy heuristic that strikes a balance between distance greed, i.e., to avoid long trips without resources and resource greed, i.e., to move to a location where resources are expected to appear following the NMF model. To ensure that agents do not oversupply areas for which resources are predicted and under supply other areas, we randomize the destinations of agents using the predicted resource distribution within the local neighborhood of an agent. Our experimental evaluation shows that our approach reduces the search time of agents and the wait time of resources using real-world data from Manhattan, New York, USA.

Smart Agent vs. Random Destination

Main challenges:

Learning spatio-temporal resource distribution
Predicting future resources
Avoiding herding (oversupply, undersupply)
Avoiding unnecessary long distance trips

Our contributions:

Generalization: Assuming that resources vary between days, the algorithm should adapt to random deviations in resource distributions, rather than overfitting to the resource distribution in the training data set.
Balancing Utility and Distance: Agents should find a balance between exploration (moving to more useful locations) and exploitation (remaining in the current location). The algorithm must find a balance between these two aspects.
Fairness: Without allowing agents to communicate with each other, the algorithm should evade flocking towards the same destination, to avoid oversupplying some regions while causing starvation in others.
Timing: Agents should move towards regions where their is a maximal chance of finding a resource at the time of arrival.

Screen captures: simulation during morning rush hour

08:10 am

08:20 am

08:30 am

08:40 am

08:50 am

09:00 am

09:10 am

09:20 am

09:30 am

09:40 am

09:50 am

10:00 am

10:10 am

10:20 am

10:30 am

10:40 am

Comparison with baselines

Random Walk: requires agents to cruise in random directions. Thus, whenever a random walk agent reaches an intersection, they will continue into a direction chosen uniformly at random.
Random Destination: chooses a random destination uniformly random from all network nodes.

Average agent search time

Average resource wait time

Resource expiration rate

The search time of an agent is the amount of time from when the agent is labeled as empty until it picks up a resource. An agent may experience multiple search times, each corresponding to one assignment.
The wait time of a resource is the period of time from its introduction until its pick-up or expiration.
The expiration percentage is the percentage of expired resources.

Source code is available at https://github.com/joonseok-kim/SmartAgent