Improved Ant Colony Algorithm for Split Delivery Vehicle Routing Problem with Capacity Constraint

The traditional vehicle routing problem (VRP) is a typical NP-hard problem in combinatorial optimization, based on the premise that customer demands are indivisible. However, in practical logistics operations, sometimes splitting demands can lead to better cost reduction in transportation. In this paper, we establish an integer programming model for split delivery vehicle routing problem (SDVRP) with capacity constraint and design an improved Ant Colony Algorithm tailored to the characteristics of the model, with the main design idea being the innovation of a mechanism for selecting splitting points. Through computational experiments, we compare the solution results with the traditional VRP, demonstrating the superiority of demand splitting. Additionally, we compare the results with those obtained in other studies using the same instances, confirming that the algorithm proposed in this paper has certain advantages in solving the split delivery vehicle routing problem.