A Multi-Agent System for Solving the Dynamic Capacitated Vehicle Routing Problem with Stochastic Customers using Trajectory Data Mining
This addresses the challenge of efficient last-mile delivery for logistics companies in e-commerce, though it is incremental as it builds on existing VRP methods with a focus on dynamic scenarios.
The paper tackles the dynamic capacitated vehicle routing problem with stochastic customers in e-commerce logistics by developing a multi-agent system using trajectory data mining, which achieves operational gains for dynamic route creation but shows slightly lower performance compared to static algorithms.
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.