Learning to Optimize Industry-Scale Dynamic Pickup and Delivery Problems

• URL: http://arxiv.org/abs/2105.12899v1
• Date: Thu, 27 May 2021 01:16:00 GMT
• Title: Learning to Optimize Industry-Scale Dynamic Pickup and Delivery Problems
• Authors: Xijun Li, Weilin Luo, Mingxuan Yuan, Jun Wang, Jiawen Lu, Jie Wang, Jinhu Lu and Jia Zeng
• Abstract summary: The Dynamic Pickup and Delivery Problem (D PDP) is aimed at dynamically scheduling vehicles among multiple sites in order to minimize the cost when delivery orders are not known a priori. We propose a data-driven approach, Spatial-Temporal Aided Double Deep Graph Network (ST-DDGN), to solve industry-scale D PDP. Our method is entirely data driven and thus adaptive, i.e., the relational representation of adjacent vehicles can be learned and corrected by ST-DDGN from data periodically.
• Score: 17.076557377480444
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The Dynamic Pickup and Delivery Problem (DPDP) is aimed at dynamically scheduling vehicles among multiple sites in order to minimize the cost when delivery orders are not known a priori. Although DPDP plays an important role in modern logistics and supply chain management, state-of-the-art DPDP algorithms are still limited on their solution quality and efficiency. In practice, they fail to provide a scalable solution as the numbers of vehicles and sites become large. In this paper, we propose a data-driven approach, Spatial-Temporal Aided Double Deep Graph Network (ST-DDGN), to solve industry-scale DPDP. In our method, the delivery demands are first forecast using spatial-temporal prediction method, which guides the neural network to perceive spatial-temporal distribution of delivery demand when dispatching vehicles. Besides, the relationships of individuals such as vehicles are modelled by establishing a graph-based value function. ST-DDGN incorporates attention-based graph embedding with Double DQN (DDQN). As such, it can make the inference across vehicles more efficiently compared with traditional methods. Our method is entirely data driven and thus adaptive, i.e., the relational representation of adjacent vehicles can be learned and corrected by ST-DDGN from data periodically. We have conducted extensive experiments over real-world data to evaluate our solution. The results show that ST-DDGN reduces 11.27% number of the used vehicles and decreases 13.12% total transportation cost on average over the strong baselines, including the heuristic algorithm deployed in our UAT (User Acceptance Test) environment and a variety of vanilla DRL methods. We are due to fully deploy our solution into our online logistics system and it is estimated that millions of USD logistics cost can be saved per year.

Related papers

• DiFSD: Ego-Centric Fully Sparse Paradigm with Uncertainty Denoising and Iterative Refinement for Efficient End-to-End Autonomous Driving [55.53171248839489]
  We propose an ego-centric fully sparse paradigm, named DiFSD, for end-to-end self-driving. Specifically, DiFSD mainly consists of sparse perception, hierarchical interaction and iterative motion planner. Experiments conducted on nuScenes dataset demonstrate the superior planning performance and great efficiency of DiFSD.
  arXiv  Detail & Related papers  (2024-09-15T15:55:24Z)
• DNN Partitioning, Task Offloading, and Resource Allocation in Dynamic Vehicular Networks: A Lyapunov-Guided Diffusion-Based Reinforcement Learning Approach [49.56404236394601]
  We formulate the problem of joint DNN partitioning, task offloading, and resource allocation in Vehicular Edge Computing. Our objective is to minimize the DNN-based task completion time while guaranteeing the system stability over time. We propose a Multi-Agent Diffusion-based Deep Reinforcement Learning (MAD2RL) algorithm, incorporating the innovative use of diffusion models.
  arXiv  Detail & Related papers  (2024-06-11T06:31:03Z)
• Model-free Learning of Corridor Clearance: A Near-term Deployment Perspective [5.39179984304986]
  An emerging public health application of connected and automated vehicle (CAV) technologies is to reduce response times of emergency medical service (EMS) by indirectly coordinating traffic. Existing research on this topic often overlooks the impact of EMS vehicle disruptions on regular traffic, assumes 100% CAV penetration, relies on real-time traffic signal timing data and queue lengths at intersections, and makes various assumptions about traffic settings when deriving optimal model-based CAV control strategies. To overcome these challenges and enhance real-world applicability in near-term, we propose a model-free approach employing deep reinforcement learning (DRL) for designing CAV control strategies
  arXiv  Detail & Related papers  (2023-12-16T06:08:53Z)
• Pre-training on Synthetic Driving Data for Trajectory Prediction [61.520225216107306]
  We propose a pipeline-level solution to mitigate the issue of data scarcity in trajectory forecasting. We adopt HD map augmentation and trajectory synthesis for generating driving data, and then we learn representations by pre-training on them. We conduct extensive experiments to demonstrate the effectiveness of our data expansion and pre-training strategies.
  arXiv  Detail & Related papers  (2023-09-18T19:49:22Z)
• V2N Service Scaling with Deep Reinforcement Learning [0.0]
  We employ Deep Reinforcement Learning (DRL) for vertical scaling in Edge computing to support vehicular-to-network communications. We show that DDPG outperforms existing solutions, reducing the average number of active CPUs by 23% while increasing the long-term reward by 24%.
  arXiv  Detail & Related papers  (2023-01-30T23:13:18Z)
• Federated Deep Learning Meets Autonomous Vehicle Perception: Design and Verification [168.67190934250868]
  Federated learning empowered connected autonomous vehicle (FLCAV) has been proposed. FLCAV preserves privacy while reducing communication and annotation costs. It is challenging to determine the network resources and road sensor poses for multi-stage training.
  arXiv  Detail & Related papers  (2022-06-03T23:55:45Z)
• Cooperative Behavioral Planning for Automated Driving using Graph Neural Networks [0.5801044612920815]
  This work proposes to leverage machine learning algorithms to optimize traffic flow at urban intersections by jointly planning for multiple vehicles. Learning-based behavior planning poses several challenges, demanding for a suited input and output representation as well as large amounts of ground-truth data. We train and evaluate the proposed method in an open-source simulation environment for decision making in automated driving.
  arXiv  Detail & Related papers  (2022-02-23T09:36:15Z)
• Efficient and Robust LiDAR-Based End-to-End Navigation [132.52661670308606]
  We present an efficient and robust LiDAR-based end-to-end navigation framework. We propose Fast-LiDARNet that is based on sparse convolution kernel optimization and hardware-aware model design. We then propose Hybrid Evidential Fusion that directly estimates the uncertainty of the prediction from only a single forward pass.
  arXiv  Detail & Related papers  (2021-05-20T17:52:37Z)
• AdaPool: A Diurnal-Adaptive Fleet Management Framework using Model-Free Deep Reinforcement Learning and Change Point Detection [34.77250498401055]
  This paper introduces an adaptive model-free deep reinforcement approach that can recognize and adapt to the diurnal patterns in the ride-sharing environment with car-pooling. In addition to the adaptation logic in dispatching, this paper also proposes a dynamic, demand-aware vehicle-passenger matching and route planning framework.
  arXiv  Detail & Related papers  (2021-04-01T02:14:01Z)
• Data-Driven Intersection Management Solutions for Mixed Traffic of Human-Driven and Connected and Automated Vehicles [0.0]
  This dissertation proposes two solutions for urban traffic control in the presence of connected and automated vehicles. First, a centralized platoon-based controller is proposed for the cooperative intersection management problem. Second, a data-driven approach is proposed for adaptive signal control in the presence of connected vehicles.
  arXiv  Detail & Related papers  (2020-12-10T01:44:45Z)
• Data Freshness and Energy-Efficient UAV Navigation Optimization: A Deep Reinforcement Learning Approach [88.45509934702913]
  We design a navigation policy for multiple unmanned aerial vehicles (UAVs) where mobile base stations (BSs) are deployed. We incorporate different contextual information such as energy and age of information (AoI) constraints to ensure the data freshness at the ground BS. By applying the proposed trained model, an effective real-time trajectory policy for the UAV-BSs captures the observable network states over time.
  arXiv  Detail & Related papers  (2020-02-21T07:29:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.