Spatiotemporal applications such as taxi order dispatching and warehouse task scheduling depend critically on the algorithms for operational efficiency. However, the inherent dynamic nature of these applications presents challenges in algorithm design. The growth of mobility services has facilitated the collection of extensive spatiotemporal data, which in turn prompted algorithm designers to use data-driven methods. Reinforcement learning (RL), recognized for its strong performance and suitability for spatiotemporal contexts, has garnered considerable research interest. Despite their potential, RL algorithms necessitate the use of a simulator for both training and validation purposes. However, no specific simulation system has been developed for spatiotemporal algorithm design. This vacancy hinders the progress of spatiotemporal algorithm designers. In this demo, we build a system called Data-driven Spatiotemporal Simulator (DSS), hoping to bring convenience for spatiotemporal algorithm designers. DSS is adept at handling problems related to taxi order dispatching and warehouse task scheduling and possesses the versatility to be expanded for other user-defined scenarios. The system includes visualization modules that offer insightful panels, alongside developer tools designed to streamline the development process. This enables designers to efficiently craft, evaluate, and refine their algorithms, potentially accelerating innovation in spatiotemporal application development.

Multi-robot systems are deployed in modern warehouses to reduce operational cost. The robots are tasked to deliver items stored on racks to pickers for fast distribution. A central algorithmic problem is collision-aware route planning, which aims to plan shortest routes for robots to deliver racks while avoiding collision with racks, pickers, and other robots. Prior solutions are inefficient in real-world warehouses, where route planning requests emerge online and at large scale. In this paper, we identify collision judgement in grid-based warehouse representation as the primary efficiency bottleneck, and propose a novel Strip-based Route Planning framework (SRP). Specifically, we exploit the regularity in warehouse layouts, and aggregate grids into strips. The strip-based representation also converts collisions of 3-dimensional (2-dimensional space and 1-dimensional time) routes into 2-dimensional (1-dimensional space and 1-dimensional time) segment intersections, which can be fast checked via computational geometry. We further accelerate the collision judgement via indexing on segments within strips. Theoretical analysis shows a reduction of time complexity from square to linear-logarithmic. Experimental results on datasets collected from real-world robotized warehouses show that our SRP is up to 227× faster than existing methods.

Ride hailing has become prevailing. Central in ride hailing platforms is taxi order dispatching which involves recommending a suitable driver for each order. Previous works use pure combinatorial optimization solutions for taxi dispatching, which suffer in practice due to complex dynamics of demand and supply and temporal dependency among dispatching decisions. Recent studies try to adopt data-driven method into combinatorial optimization hoping knowledge from history data would help overcome these challenges. Among these attempts, adoption of reinforcement learning shows great promise but current adoptions are a unidirectional integration which restricts the potential performance gains. In this work, we proposeLearningToDispatch(LTD), a systematic solution that allows synergic integration of reinforcement learning and combinatorial optimization for large-scale taxi order dispatching. We demonstrate the necessity of online learning and taxi scheduling for reinforcement learning to work in synergy with combinatorial optimization, and devise corresponding algorithms. We also devise many tricks for more efficient calculation of the bipartite matching. Experiments show our methods can improve$36.4\%$and$42.0\%$on utility and efficiency at most, respectively. Especially, it achieves state-of-the-art performance in terms of utility.

Robotized warehouses are deployed to automatically distribute millions of items brought by the massive logistic orders from e-commerce. A key to automated item distribution is to plan paths for robots, also known as task planning, where each task is to deliver racks with items to pickers for processing and then return the rack back. Prior solutions are unfit for large-scale robotized warehouses due to the inflexibility to time-varying item arrivals and the low efficiency for high throughput. In this paper, we propose a new task planning problem called TPRW, which aims to minimize the end-to-end makespan that incorporates the entire item distribution pipeline, known as a fulfilment cycle. Direct extensions from state-of-the-art path finding methods are ineffective to solve the TPRW problem because they fail to adapt to the bottleneck variations of fulfillment cycles. In response, we propose Efficient Adaptive Task Planning, a framework for large-scale robotized warehouses with time-varying item arrivals. It adaptively selects racks to fulfill at each timestamp via rein-forcement learning, accounting for the time-varying bottleneck of the fulfillment cycles. Then it finds paths for robots to transport the selected racks. The framework adopts a series of efficient optimizations on both time and memory to handle large-scale item throughput. Evaluations on both synthesized and real data show an improvement of 37.1% in effectiveness and 75.5% in efficiency over the state-of-the-arts.

Traditional learning-to-rank (LTR) models are usually trained in a centralized approach based upon a large amount of data. However, with the increasing awareness of data privacy, it is harder to collect data from multiple owners as before, and the resultant data isolation problem makes the performance of learned LTR models severely compromised. Inspired by the recent progress in federated learning, we propose a novel framework named Cross-Silo Federated Learning-to-Rank (CS-F-LTR), where the efficiency issue becomes the major bottleneck. To deal with the challenge, we first devise a privacy-preserving cross-party term frequency querying scheme based on sketching algorithms and differential privacy. To further improve the overall efficiency, we propose a new structure named reverse top-K sketch (RTK-Sketch) which significantly accelerates the feature generation process while holding theoretical guarantees on accuracy loss. Extensive experiments conducted on public datasets verify the effectiveness and efficiency of the proposed approach.

Ride hailing is a widespread shared mobility application where the central issue is to assign taxi requests to drivers with various objectives. Despite extensive research on task assignment in ride hailing, the fairness of earnings among drivers is largely neglected. Pioneer studies on fair task assignment in ride hailing are ineffective and inefficient due to their myopic optimization perspective and time-consuming assignment techniques. In this work, we propose LAF, an effective and efficient task assignment scheme that optimizes both utility and fairness. We adopt reinforcement learning to make assignments in a holistic manner and propose a set of acceleration techniques to enable fast fair assignment on large-scale data. Experiments show that LAF outperforms the state-of-the-arts by up to 86.7%, 29.1%, 797% on fairness, utility and efficiency, respectively.

Large ride-hailing platforms, such as DiDi, Uber and Lyft, connect tens of thousands of vehicles in a city to millions of ride demands throughout the day, providing great promises for improving transportation efficiency through the tasks of order dispatching and vehicle repositioning. Existing studies, however, usually consider the two tasks in simplified settings that hardly address the complex interactions between the two, the real-time fluctuations between supply and demand, and the necessary coordinations due to the large-scale nature of the problem. In this paper we propose a unified value-based dynamic learning framework (V1D3) for tackling both tasks. At the center of the framework is a globally shared value function that is updated continuously using online experiences generated from real-time platform transactions. To improve the sample-efficiency and the robustness, we further propose a novel periodic ensemble method combining the fast online learning with a large-scale offline training scheme that leverages the abundant historical driver trajectory data. This allows the proposed framework to adapt quickly to the highly dynamic environment, to generalize robustly to recurrent patterns and to drive implicit coordinations among the population of managed vehicles. Extensive experiments based on real-world datasets show considerably improvements over other recently proposed methods on both tasks. Particularly, V1D3 outperforms the first prize winners of both dispatching and repositioning tracks in the KDD Cup 2020 RL competition, achieving state-of-the-art results on improving both total driver income and user experience related metrics.