Distance-Aware Competitive Spatiotemporal Searching Using Spatiotemporal Resource Matrix Factorization

GIS Cup is an annual contest of SIGSPATIAL. ACM SIGSPATIAL Cup 2019 was about optimization of agents’ maneuvers based on the ride-hailing simulation provided by the contest organizers. The main challenge was how smartly the agents (or drivers) seeking customers relocate their cars without any communication with other agents while globally minimizing search time of all agents and wait time of all customers. My approach is to learn a spatiotemporal resource model using non-negative matrix factorization. Then, our SmartAgents strive to avoid both oversupply and undersupply, considering balance of greed for travel-distance and resource distribution.


Our paper was accepted as one of four finalists who achieved the best results. The final result of the contest will be revealed at ACM SIGSPATIAL'19, November 7, 2019. For more information, please visit my project web site http://giscup19.joonseok.org

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

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.

J.-S. Kim, D. Pfoser, and A. Züfle, Distance-Aware Competitive Spatiotemporal Searching Using Spatiotemporal Resource Matrix Factorization (GIS Cup), In Proceedings of ACM SIGSPATIAL GIS ’19, November 5-8, 2019. Chicago, IL, USA (to appear)