Online spatio - Temporal demand supply matching

• Main Author: LOWALEKAR, Meghna
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Online Matching; Online Stochastic Optimization; Sequential Decision Making; Artificial Intelligence and Robotics; Systems Architecture
• Online Access: https://ink.library.smu.edu.sg/etd_coll/295; https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1295&context=etd_coll
• Institution: Singapore Management University

The rapid growth of cities in developing world coupled with the increase in rural to urban migration have led to cities being identified as the key actor for any nation's economy. Shared mobility has become an integral part of life of people in cities as it improves efficiency and enhances transportation accessibility. As a result, the mismatch between the demand and supply of shared mobility resources has a direct impact on people's life. Thus, the goal of my dissertation is to develop solution strategies for these real-time (online) spatio-temporal demand supply matching problems for shared mobility resources which can enhance the service quality by considering expected future demand. These problems involve a set of customer requests which need to be matched with the available resources (taxis, bikes at stations etc.). The key characteristic that affect the complexity of these problems is the nature of the customer requests involved which in turn affects the matching decisions. We categorize these matching problems into two categories based on the nature of customer requests. In the first category, each customer request is associated with an origin and destination. These customer requests need to be matched with servers/vehicles which pick them from their origin and drop at their destination. The applications include ridesharing, food delivery systems etc. When the servers are of unit-capacity, the matching graph is a bipartite graph with servers on one side and customer requests on the other side. The complexity of the problems increases when multi-capacity servers are used as the underlying matching graph is no longer bipartite but a tripartite graph with servers, requests and request groups (combinations of requests that can travel together). The second category involves problems where customer requests for resources stored at different warehouses/stations either by walking into the warehouse or from a remote location. In this category, each customer request is either requesting a pick-up or drop-off of resources but not both. For example, in bikesharing systems, customers either request to pick-up a bike from a station or request to drop-off (return) an earlier picked bike at stations. The multi-capacity servers in these problems provide an assistance in matching these customer requests with required resources by performing a redistribution of these resources across different stations. The matching graph is complex as in addition to matching customer requests with the resources at stations, it also involves matching servers with the decisions of redistributing resources across stations. The other characteristics which make these matching problems hard, is the scale of the problem (thousands of resources and customer requests), uncertainty in the environment (uncertain customer demand) and the need of making real-time sequential and connected decisions. To tackle these different challenges, I develop online data driven optimization approaches which consider expected future demand. To evaluate the performance of these algorithms, I perform experiments on real world datasets and where possible, I also provide a theoretical bound on the algorithm's performance which is measured using a metric called competitive ratio. Specifically, for solving the first category of problems, I propose an online data- driven multi-period two-stage stochastic optimization approach and a neural approximate dynamic programming approach which can compute the future effect of current assignments based on the historical data samples. The experimental results on three real world datasets show significant improvement in performance over existing approaches. For a special case, I propose an online adaptive algorithm which can achieve a competitive ratio of $\gamma$, where $\gamma$ is a solution to the equation $(1-\gamma)^{\kappa+1} = \gamma$ and $\kappa$ is the maximum capacity of the servers. For solving the second category of problems, I propose an online data driven multi-period two-stage stochastic optimization approach and a greedy online anticipatory heuristic which use historical demand samples to compute the future effect of current assignments. Experimental results on two real world datasets show that our future demand driven matching approaches provide 20% gain over existing approaches.