Approximating Split Delivery Path Routing Problems

A fundamental variant of the classical vehicle routing problem (VRP) is known as capacitated path routing problem (CPRP), where a fleet of capacitated vehicles departs from multiple depots to fulfill customer demands without the requirement to return to the depot, i.e., operating along open routes. As with the VRP, the CPRP arises in a wide range of applications in modern logistics. This work focuses on a split-delivery extension of the CPRP (referred to as SDPRP), where each customer’s demand can be served by more than one vehicle. Inspired by practical logistics scenarios, we particularly address two critical modeling considerations: (i) whether to include the travel cost from the depot/terminal to the first/last customer in the objective function, and (ii) whether vehicle-to-depot assignment is required. These modeling choices give rise to a family of SDPRP variants. By extending the approximation framework for the multi-depot split delivery vehicle routing problem (Lai et al. [20]), we develop new parameterized constant-ratio approximation algorithms for several variants of the SDPRP.