In Location-Based Services (LBS), such as food delivery, a fundamental task is segmenting Areas of Interest (AOIs), aiming at partitioning the urban geographical spaces into non-overlapping regions. Traditional AOI segmentation algorithms primarily rely on road networks to partition urban areas. While promising in modeling the geo-semantics, road network-based models overlooked the service-semantic goals (e.g., workload equality) in LBS service. In this article, we point out that the AOI segmentation problem can be naturally formulated as a Markov Decision Process (MDP), which gradually chooses a nearby AOI for each grid in the current AOI’s border. Based on the MDP, we present the first attempt to generalize Deep Reinforcement Learning (DRL) for AOI segmentation, leading to a novel DRL-based framework called DRL4AOI. The DRL4AOI framework introduces different service-semantic goals in a flexible way by treating them as rewards that guide the AOI generation. To evaluate the effectiveness of DRL4AOI, we develop and release an AOI segmentation system. We also present a representative implementation of DRL4AOI—TrajRL4AOI—for AOI segmentation in the logistics service. It introduces a Double Deep Q-learning Network (DDQN) to gradually optimize the AOI generation for two specific semantic goals: (i) trajectory modularity, i.e., maximize tightness of the trajectory connections within an AOI and the sparsity of connections between AOIs, (ii) matchness with the road network, i.e., maximizing the matchness between AOIs and the road network. Quantitative and qualitative experiments conducted on synthetic and real-world data demonstrate the effectiveness and superiority of our method. The code and system is publicly available at https://github.com/Kogler7/AoiOpt .

Real-world last-mile express datasets are crucial for research in logistics, supply chain management, and spatio-temporal data mining. Despite a plethora of algorithms developed to date, no widely accepted, publicly available last-mile express dataset exists to support research in this field. In this paper, we introduce LaDe, the first publicly available last-mile express dataset with millions of packages from the industry. LaDe has three unique characteristics: (1)Large-scale. It involves 10,677k packages of 21k couriers over 6 months of real-world operation. (2)Comprehensive information. It offers original package information, task-event information, as well as couriers' detailed trajecotries and road networks. (3)Diversity. The dataset includes data from various scenarios, including package pick-up and delivery, and from multiple cities, each with its unique spatio-temporal patterns due to their distinct characteristics such as populations. We verify LaDe on three tasks by running several classical baseline models per task. We believe that the large-scale, comprehensive, diverse feature of LaDe can offer unparalleled opportunities to researchers in the supply chain community, data mining community, and beyond. The dataset and code is publicly available at https://huggingface.co/datasets/Cainiao-AI/LaDe.

Feasible solutions are crucial for Integer Programming (IP) since they can substantially speed up the solving process. In many applications, similar IP instances often exhibit similar structures and shared solution distributions, which can be potentially modeled by deep learning methods. Unfortunately, existing deep-learning-based algorithms, such as Neural Diving [21] and Predict-and-search framework [8], are limited to generating only partial feasible solutions, and they must rely on solvers like SCIP and Gurobi to complete the solutions for a given IP problem. In this paper, we propose a novel framework that generates complete feasible solutions end-to-end. Our framework leverages contrastive learning to characterize the relationship between IP instances and solutions, and learns latent embeddings for both IP instances and their solutions. Further, the framework employs diffusion models to learn the distribution of solution embeddings conditioned on IP representations, with a dedicated guided sampling strategy that accounts for both constraints and objectives. We empirically evaluate our framework on four typical datasets of IP problems, and show that it effectively generates complete feasible solutions with a high probability (> 89.7 %) without the reliance of Solvers and the quality of solutions is comparable to the best heuristic solutions from Gurobi. Furthermore, by integrating our method's sampled partial solutions with the CompleteSol heuristic from SCIP [19], the resulting feasible solutions outperform those from state-of-the-art methods across all datasets, exhibiting a 3.7 to 33.7% improvement in the gap to optimal values, and maintaining a feasible ratio of over 99.7% for all datasets.

Inbound parcel volume forecasting problem (IPVFP) plays an important role in the logistics system as it can facilitate various downstream applications. Despite the fact that a number of time series forecasting techniques have been developed, existing approaches fail to explicitly consider intrinsic characteristics of the logistics system, e.g., parcel transport patterns, operation patterns, and their spatial-temporal dependencies. To this end, we propose a novel hybrid inbound parcel volume forecasting model to analyze the logistic spatial-temporal graph that is constructed based on logistics data and the physical location of logistics stations. The graph includes engineered features such as the transition matrix and modified Dynamic Time Warping (DTW) distance matrix, which accurately depicts the parcel transfer patterns within the system. In addition, it incorporates a dedicated attention mechanism that introduces a novel bit-embedding representation method for integer tokens, enabling to capture of dynamic correlations among different timestamps. Finally, a collaborative module comprising dilated convolution layers and Gated Recurrent Units (GRU) is integrated to capture long-term dependencies. Extensive experiments on real-world data evaluate the effectiveness of the proposed graph and model, demonstrating its superiority over 16 other advanced baseline models. We release our code and data at https://github.com/YelsAlyssa/IPVFP.

Maximizing a monotone submodular function is a fundamental task in data mining, machine learning, economics, and statistics. In this paper, we present two communication-efficient decentralized online algorithms for the monotone continuous DR-submodular maximization problem, both of which reduce the number of per-function gradient evaluations and per-round communication complexity from T3/2 to 1. The first one, One-shot Decentralized Meta-Frank-Wolfe~(Mono-DMFW), achieves a (1-1/e)-regret bound of O(T4/5). As far as we know, this is the first one-shot and projection-free decentralized online algorithm for monotone continuous DR-submodular maximization. Next, inspired by the non-oblivious boosting function[29], we propose the Decentralized Online Boosting Gradient Ascent (DOBGA) algorithm, which attains a (1-1/e)-regret of O(√T). To the best of our knowledge, this is the first result to obtain the optimal O(√T) against a (1-1/e)-approximation with only one gradient inquiry for each local objective function per step. Finally, various experimental results confirm the effectiveness of the proposed methods.

Instant-logistics (e.g., food delivery and package pick-up) is increasingly calling for Route and Time Prediction (RTP), which aims to predict both future route and arrival time of a courier’s unvisited locations. Accurate RTP can greatly benefit the platform, such as optimizing order dispatching and improving user experience. Although recent years have witnessed various works for solving the RTP problem, they still suffer from the following three limitations: i) Failing to consider the high-level transfer mode of couriers between AOIs (Areas Of Interest, such as residential quarters or office buildings), which can help to build more accurate RTP. ii) Failing to simultaneously make the route and time prediction. Existing works either separately predict route/time or predict them in a two-step way. However, since route and time are strongly correlated (nearby locations in the route should have similar arrival times), jointly predicting them should be more effective. iii) The widely adopted tree-based or sequence-based architecture fails to fully encode the spatial relationship between different locations. To address the above limitations, we propose a multi-level and multi-task graph model, named M2G4RTP, for instant-logistics route and time joint prediction. Specifically, we propose a multi-level graph encoder equipped with a newly-designed GAT-e encoding module to capture couriers’ both high-level transfer modes between AOIs and low-level transfer modes between locations. Moreover, a multi-task decoder is presented to jointly predict the route and time at different levels. Finally, a loss weighting method based on homoscedastic uncertainty is designed to balance the two tasks adaptively. Extensive experiments on an industry-scale real-world dataset, as well as the online deployment on Cainiao Alibaba, demonstrate the superiority of our proposed model.

Last-mile delivery, which refers to delivering packages from the depot to customers, is a crucial step for logistics service. The Route and Time Prediction (RTP) in last-mile package delivery is beneficial to improve customers’ experience and supervise couriers’ behavior. However, the limited raw information brings great challenges to accurately predict the route and delivery time. In this paper, we propose a deep model named I2RTP, which explores the heterogeneous representation of the package’s community to help predict the delivery route and estimate the arrival time of each package. Specifically, for the entire delivery route prediction, we model the inter- and intra-community information to learn the route features from global and local perspectives. Besides, by integrating the community representation with package features, our model could make more accurate predictions of the next-delivery package and its time duration. Experiments on the offline dataset and the online deployment on Cainiao’s Delivery System demonstrate the effectiveness of our proposed method, as well as validate the rationality of the global and local prediction pipeline.

Pick-up and Delivery Route Prediction (PDRP), which aims to estimate the future service route of a worker given his current task pool, has received rising attention in recent years. Deep neural networks based on supervised learning have emerged as the dominant model for the task because of their powerful ability to capture workers' behavior patterns from massive historical data. Though promising, they fail to introduce the non-differentiable test criteria into the training process, leading to a mismatch in training and test criteria. Which considerably trims down their performance when applied in practical systems. To tackle the above issue, we present the first attempt to generalize Reinforcement Learning (RL) to the route prediction task, leading to a novel RL-based framework called DRL4Route. It combines the behavior-learning abilities of previous deep learning models with the non-differentiable objective optimization ability of reinforcement learning. DRL4Route can serve as a plug-and-play component to boost the existing deep learning models. Based on the framework, we further implement a model named DRL4Route-GAE for PDRP in logistic service. It follows the actor-critic architecture which is equipped with a Generalized Advantage Estimator that can balance the bias and variance of the policy gradient estimates, thus achieving a more optimal policy. Extensive offline experiments and the online deployment show that DRL4Route-GAE improves Location Square Deviation (LSD) by 0.9%-2.7%, and Accuracy@3 (ACC@3) by 2.4%-3.2% over existing methods on the real-world dataset.

Large-scale commercial platforms usually involve numerous business scenarios for diverse business strategies. To provide click-through rate (CTR) predictions for multiple scenarios simultaneously, existing promising multi-scenario models explicitly construct scenario-specific networks by manually grouping scenarios based on particular business strategies. Nonetheless, this pre-defined data partitioning process heavily relies on prior knowledge, and it may neglect the underlying data distribution of each scenario, hence limiting the model's representation capability. Regarding the above issues, we propose Adaptive Distribution Learning (ADL): an end-to-end optimization distribution framework which is composed of a clustering process and classification process. Specifically, we design a distribution adaptation module with a customized dynamic routing mechanism. Instead of introducing prior knowledge for pre-defined data allocation, this routing algorithm adaptively provides a distribution coefficient for each sample to determine which cluster it belongs to. Each cluster corresponds to a particular distribution so that the model can sufficiently capture the commonalities and distinctions between these distinct clusters. Our results on both public and large-scale industrial datasets show the effectiveness and efficiency of ADL: the model yields impressive prediction accuracy with more than 50% reduction in time cost during the training phase when compared to other methods.

Pick-up and delivery (P&D) services such as food delivery have achieved explosive growth in recent years by providing customers with daily-life convenience. Though many service providers have invested considerably in routing tools, more and more practitioners realize that significant deviations exist between workers' actual routes and planned ones. So it is not wise to feed "optimal routes" as workers' actual service routes into downstream tasks (e.g., arrival-time prediction and order dispatching), whose performances count on the accuracy of route prediction, i.e., to predict the future service route of a worker's unfinished tasks. Therefore, to meet the rising calling for route prediction models that can capture workers' future routing behaviors, in this paper, we formulate the Pick-up and Delivery Route Prediction task (PDRP task for short) from the graph perspective for the first time, then propose a dynamic spatial-temporal graph-based model, named Graph2Route. Unlike previous sequence-based models, our model leverages the underlying graph structure and features into the encoding and decoding process. Moreover, the dynamic graph-based nature can spontaneously describe the evolving relationship between different problem instances. As a result, abundant decision context information and various spatial-temporal information of node/edge can be fully utilized in Graph2Route to improve the prediction performance. Offline experiments over two real-world industry-scale datasets under different P&D services (i.e., food delivery and package pick-up) and online A/B test demonstrate the superiority of our proposed model.

In recent years, multi-task learning models based on deep learning in recommender systems have attracted increasing attention from researchers in industry and academia. Accurately estimating post-click conversion rate (CVR) is often considered as the primary task of multi-task learning in recommender systems. However, some advertisers may try to get higher click-through rates (CTR) by over-decorating their ads, which may result in excessive exposure to samples with lower CVR. For example, some only eye-catching clickbait have higher CTR, but actually, CVR is very low. As a result, the overall performance of the recommender system will be hurt. In this paper, we introduce a novelty auxiliary task called CTnoCVR, which aims to predict the probability of events with click but no-conversion, in various state-of-the-art multi-task models of recommender systems to promote samples with high CVR but low CTR. Plentiful Experiments on a large-scale dataset gathered from traffic logs of Taobao's recommender system demonstrate that the introduction of CTnoCVR task significantly improves the prediction effect of CVR under various multi-task frameworks. In addition, we conduct the online test and evaluate the effectiveness of our proposed method to make those samples with high CVR and low CTR rank higher.

Randomness exists either due to the inherent noise of the problem or lack of important input features, which could lead to multimodality of the data distribution. Therefore, in more and more scenarios, it is required not only to predict a single point-value, but also the distribution of the prediction. However, well-studied prediction models usually focus on point prediction that minimizes the mean squared error or the mean absolute error. These approaches could miss important knowledge when their outputs are applied to the downstream decision process. In this paper, we combine the advantages of both GANs (Generative Adversarial Nets) and VAEs (Variational Auto-Encoders), and introduce a latent-based conditional generative model (LB-CGM) to handle the distribution regression problems. The VAE framework is adopted, and the adversarial network is applied to estimate the validity of the generated sample. Besides, the latent-based reconstruction loss is introduced to mitigate mode collapse, in which the direct pairwise comparison between the original and generated samples ensures the correctness and completeness of the generated mode pattern. In this work, we explore a path for the generative model to be used in probabilistic prediction problems. This method can produce conditional prediction distribution close to the actual distribution and is verified on both the synthetic dataset and benchmark dataset.

Balanced order batching problem (BOBP) arises from the process of warehouse picking in Cainiao, the largest logistics platform in China. Batching orders together in the picking process to form a single picking route, reduces travel distance. The reason for its importance is that order picking is a labor intensive process and, by using good batching methods, substantial savings can be obtained. The BOBP is a NP-hard combinational optimization problem and designing a good problem-specific heuristic under the quasi-real-time system response requirement is non-trivial. In this paper, rather than designing heuristics, we propose an end-to-end learning and optimization framework named Balanced Task-orientated Graph Clustering Network (BTOGCN) to solve the BOBP by reducing it to balanced graph clustering optimization problem. In BTOGCN, a task-oriented estimator network is introduced to guide the type-aware heterogeneous graph clustering networks to find a better clustering result related to the BOBP objective. Through comprehensive experiments on single-graph and multi-graphs, we show: 1) our balanced task-oriented graph clustering network can directly utilize the guidance of target signal and outperforms the two-stage deep embedding and deep clustering method; 2) our method obtains an average 4.57m and 0.13m picking distance reduction than the expert-designed algorithm on single and multi-graph set and has a good generalization ability to apply in practical scenario.

Our model is based on the graph convolutional network (GCN) with node feature (coordination and demand) and edge feature (the real distance between nodes) as input and embedded. Separate decoders are proposed to decode the representations of these two features. The output of one decoder is the supervision of the other decoder. We propose a strategy that combines the reinforcement learning manner with the supervised learning manner to train the model. Through comprehensive experiments on real-world data, we show that 1) the edge feature is important to be explicitly considered in the model; 2) the joint learning strategy can accelerate the convergence of the training and improve the solution quality; 3) our model significantly outperforms several well-known algorithms in the literature, especially when the problem size is large; 3) our method is generalized beyond the size of problem instances they were trained on.