The multi-depot split-delivery vehicle routing problem: Model and solution algorithm

Logistics and supply-chain management may generate notable operational cost savings with increased reliance on shared serving of customer demands by multiple agents. However, traditional logistics planning exhibits an intrinsic limitation in modeling and implementing shared commodity delivery from multiple depots using multiple agents. In this paper, we investigate a centralized model and a heuristic algorithm for solving the multi-depot logistics delivery problem including depot selection and shared commodity delivery. The contribution of the paper is threefold. First, we elaborate a new integer linear programming (ILP) model, namely: Multi-Depot Split-Delivery Vehicle Routing Problem (MDSDVRP) which allows establishing depot locations and routes for serving customer demands within the same objective function. Second, we illustrate a fast heuristic algorithm leveraging knowledge gathering in order to find near-optimal solutions. Finally, we provide performance results of the proposed approach by analyzing known problem instances from different VRP problem classes. The experimental results show that the proposed algorithm exhibits very good performance when solving small and medium size problem instances and reasonable performance for larger instances.