The Multi-Depot Split-Delivery Vehicle Routing Problem – Model and Solution Algorithm


  1. Ray, S.
  2. Soeanu, A.
  3. Berger, J.
  4. Debbabi, M.
Corporate Authors
Defence Research and Development Canada, Valcartier Research Centre, Quebec QC (CAN);Concordia Univ, Montreal QUE (CAN)
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.
multi-depot vehicle routing problem;integer linear programming;heuristic algorithm;supply chain management;operations research
Report Number
DRDC-RDDC-2014-P126 — External Literature
Date of publication
07 Apr 2015
Number of Pages
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: