# AAGA: A Priori Adaptive Splitting Algorithm for the Split Delivery Vehicle Routing Problem
###### Abstract  
The split delivery vehicle routing problem (SDVRP) is a relaxed variant of the capacitated vehicle routing problem (CVRP) where the restriction that each customer is visited precisely once is removed. Compared with CVRP, the SDVRP allows a reduction in the total cost of the routes traveled by vehicles. The exact methods to solve the SDVRP are computationally expensive. Moreover, the complexity and difficult implementation of the state-of-the-art heuristic approaches hinder their application in real-life scenarios of the SDVRP. In this paper, we propose an easily understandable and effective approach to solve the SDVPR based on an a priori adaptive splitting algorithm (AASA) that improves the existing state of the art on a priori split strategy in terms of both solution accuracy and time complexity. In this approach, the demand of the customers is split into smaller demand values using a splitting rule in advance. Consequently, the original SDVRP instance is converted to a CVRP instance which is solved using an existing CVRP solver. While the proposed a priori splitting rule in the literature is fixed for all customers regardless of their demand and location, we suggest an adaptive splitting rule that takes into account the distance of the customers to the depot and their demand values. Our experiments show that AASA can generate solutions comparable to the state of the art, but much faster. split delivery vehicle routing problem; capacitated vehicle routing problem; splitting rule +
Footnote †: journal:  
00 000-0002-4000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-00000-0000-00  
costs as efficient routing reduces the time drivers spend on the road, which translates to lower labor costs. Reduced travel time also minimizes overtime and improves overall productivity. Moreover, split deliveries enable better alignment with demand patterns. By avoiding the need to stockpile large quantities of inventory, businesses can reduce warehousing costs and minimize the risk of overstocking or obsolescence. These findings justify the essence of formulating and solving the SDVRP. State-of-the-art research has applied the SDVRP to various practical scenarios. For instance, [PERSON] et al. [3] addressed the problem of distributing feed to cattle on a large ranch in Arizona, where inaccuracies in feed loading necessitate split deliveries. Their approach, modeled as a capacitated rural postman problem with time windows, demonstrated that allowing split deliveries significantly reduced the total distance traveled by the fleet in most cases. [PERSON] and [PERSON] [4] studied the crew exchange process between offshore gas platforms in the North Sea. They formulated this as a discrete split delivery routing problem and employed integer programming with column generation and a cluster-and-route procedure. Their experiments showed that while their column generation approach (CGRP) was more accurate, the cluster-and-route (CR) method offered faster computation times. [PERSON] et al. [5] explored the distribution of newspapers from printing plants to agents in South Korea. They implemented a two-phase solution procedure, including agent allocation and split delivery scheduling, which improved the overall delivery efficiency and reduced costs by 15% compared to manual methods. More recently, within the context of waste management, ref. [6] utilized the SDVRP framework to model and solve complex waste collection and transportation challenges, incorporating realistic collection policies and offering insights into optimizing operational costs and fleet management, where they showed how an appropriate collection policy can significantly reduce fleet operating costs by 40-60% and fleet size by approximately 50% without causing overflow. The SDVRP is known to be an NP-hard problem [7]. Therefore, exact solutions are only applicable to the SDVRP instances of smaller scale.