A Multi-Agent System for Solving the Dynamic Capacitated Vehicle Routing Problem with Stochastic Customers using Trajectory Data Mining

• URL: http://arxiv.org/abs/2009.12691v1
• Date: Sat, 26 Sep 2020 21:36:35 GMT
• Title: A Multi-Agent System for Solving the Dynamic Capacitated Vehicle Routing Problem with Stochastic Customers using Trajectory Data Mining
• Authors: Juan Camilo Fonseca-Galindo, Gabriela de Castro Surita, Jos\'e Maia Neto, Cristiano Leite de Castro and Andr\'e Paim Lemos
• Abstract summary: E-commerce has created new challenges for logistics companies, one of which is being able to deliver products quickly and at low cost. Our work presents a multi-agent system that uses trajectory data mining techniques to extract territorial patterns and use them in the dynamic creation of last-mile routes.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The worldwide growth of e-commerce has created new challenges for logistics companies, one of which is being able to deliver products quickly and at low cost, which reflects directly in the way of sorting packages, needing to eliminate steps such as storage and batch creation. Our work presents a multi-agent system that uses trajectory data mining techniques to extract territorial patterns and use them in the dynamic creation of last-mile routes. The problem can be modeled as a Dynamic Capacitated Vehicle Routing Problem (VRP) with Stochastic Customer, being therefore NP-HARD, what makes its implementation unfeasible for many packages. The work's main contribution is to solve this problem only depending on the Warehouse system configurations and not on the number of packages processed, which is appropriate for Big Data scenarios commonly present in the delivery of e-commerce products. Computational experiments were conducted for single and multi depot instances. Due to its probabilistic nature, the proposed approach presented slightly lower performances when compared to the static VRP algorithm. However, the operational gains that our solution provides making it very attractive for situations in which the routes must be set dynamically.

Related papers

• Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses [1.2810395420131764]
  Multi-Agent Path Finding (MAPF) is an important optimization problem underlying the deployment of robots in automated warehouses and factories. We consider a realistic problem of online order delivery in a warehouse, where a fleet of robots bring the products belonging to each order from shelves to workstations. This creates a stream of inter-dependent pickup and delivery tasks and the associated MAPF problem consists of computing realistic collision-free robot trajectories.
  arXiv  Detail & Related papers  (2024-08-26T15:13:38Z)
• Sparse Diffusion Policy: A Sparse, Reusable, and Flexible Policy for Robot Learning [61.294110816231886]
  We introduce a sparse, reusable, and flexible policy, Sparse Diffusion Policy (SDP) SDP selectively activates experts and skills, enabling efficient and task-specific learning without retraining the entire model. Demos and codes can be found in https://forrest-110.io/sparse_diffusion_policy/.
  arXiv  Detail & Related papers  (2024-07-01T17:59:56Z)
• Exploring Dynamic Transformer for Efficient Object Tracking [58.120191254379854]
  We propose DyTrack, a dynamic transformer framework for efficient tracking. DyTrack automatically learns to configure proper reasoning routes for various inputs, gaining better utilization of the available computational budget. Experiments on multiple benchmarks demonstrate that DyTrack achieves promising speed-precision trade-offs with only a single model.
  arXiv  Detail & Related papers  (2024-03-26T12:31:58Z)
• Multi-Agent Learning of Efficient Fulfilment and Routing Strategies in E-Commerce [11.421159751635667]
  paper presents an integrated algorithmic framework for minimising product delivery costs in e-commerce. One of the major challenges in e-commerce is the large volume of-temporally diverse orders from multiple customers. We propose an approach that combines graph neural networks and reinforcement learning to train the node selection and vehicle agents.
  arXiv  Detail & Related papers  (2023-11-20T10:32:28Z)
• Sparse-DySta: Sparsity-Aware Dynamic and Static Scheduling for Sparse Multi-DNN Workloads [65.47816359465155]
  Running multiple deep neural networks (DNNs) in parallel has become an emerging workload in both edge devices. We propose Dysta, a novel scheduler that utilizes both static sparsity patterns and dynamic sparsity information for the sparse multi-DNN scheduling. Our proposed approach outperforms the state-of-the-art methods with up to 10% decrease in latency constraint violation rate and nearly 4X reduction in average normalized turnaround time.
  arXiv  Detail & Related papers  (2023-10-17T09:25:17Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• A Deep Reinforcement Learning Approach for Constrained Online Logistics Route Assignment [4.367543599338385]
  It is crucial for the logistics industry on how to assign a candidate logistics route for each shipping parcel properly. This online route-assignment problem can be viewed as a constrained online decision-making problem. We develop a model-free DRL approach named PPO-RA, in which Proximal Policy Optimization (PPO) is improved with dedicated techniques to address the challenges for route assignment (RA)
  arXiv  Detail & Related papers  (2021-09-08T07:27:39Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Territory Design for Dynamic Multi-Period Vehicle Routing Problem with Time Windows [0.0]
  Territory Design for Dynamic Multi-Period Vehicle Routing Problem with Time Windows (TD-DMPVRPTW) This problem deals with the design of contiguous and compact territories for delivery of orders from a depot to a set of customers. Customers and their demands vary dynamically over time.
  arXiv  Detail & Related papers  (2020-12-18T20:50:32Z)
• Balanced dynamic multiple travelling salesmen: algorithms and continuous approximations [0.40611352512781856]
  Dynamic routing occurs when customers are not known in advance, e.g. for real-time routing. Twos are proposed that solve the balanced dynamic multiple travelling salesmen problem (BD-mTSP)
  arXiv  Detail & Related papers  (2020-08-27T11:41:20Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

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.