Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost

This paper addresses a new vehicle routing problem that simultaneously involves time windows, split delivery, and linear weight‐related cost. This problem is a generalization of the split delivery vehicle routing problem with time windows (SDVRPTW), which consists of determining a set of least‐cost vehicle routes to serve all customers while respecting the restrictions of vehicle capacity and time windows. The travel cost per unit distance is a linear function of the vehicle weight and the customer demand can be fulfilled by multiple vehicles. To solve this problem, we propose an exact branch‐and‐price‐and‐cut algorithm, where the pricing subproblem is a variant of the resource‐constrained elementary shortest path problem. We first prove that at least one optimal solution to the pricing subproblem is associated with an extreme delivery pattern, and then we design a tailored and novel label‐setting algorithm to solve the pricing subproblem. Computational results show that our proposed algorithm can handle both the SDVRPTW and our new problem effectively.