# AAGA: A Priori Adaptive Splitting Algorithm for the Split Delivery Vehicle Routing Problem
## 2 Problem Definition and the Proposed Solution
### A Priori Adaptive Splitting Algorithm (AASA)
#### 2.3.1 Motivation  
In this section, we present the motivation behind our proposed splitting algorithm through illustrative examples. We study the impact of the splitting rule granularity on the total travel cost and the solution runtime considering customers' demand values and their distances from the depot. Our investigations reveal the benefits of using coarser/finer splitting rules for different customers depending on their demand and location. By a coarser splitting rule, we mean one that entails larger splitting portions as opposed to a finer splitting rule where the portions are smaller. For instance, for a demand point with \(d=200\), the splitting rule \(200=128+64+8\) is coarser compared to the rule \(200=3\times 64+8\). Impact of coarser rules for customers with higher demands: Using coarser rules for customers with high demands introduces a two-fold benefit: (i) it reduces the runtime due to a smaller number of resulting customers in the resulting CVRP and (ii) it often resultsin a lower total cost of delivery. To capture this effect, we employ an exponential pattern (such as 128/64/32/16/8/4/2) for the AASA rule. We illustrate this effect for the \(P04\_3070\) instance of the third dataset provided in [33], as depicted in Figure 1. In this instance, the vehicle capacity is 200 and the depot is located at the location \((0,0)\) in Figure 1a,b. Each point in the plane corresponds to a customer. The routes of the vehicles in the obtained solution are denoted by different colors. Figure 1a,b show the solution of the SDVRP instance considering the 20/10/5/1 and 128/64/32/16/8/2 splitting rules, respectively. We observe that the splitting rule of 128/64/32/16/8/4/2 reduces the solver runtime by an order of 2.5. The lower runtime is expected since using an exponential pattern in the splitting rule results in splitting the higher demands into a piece with a very high value and most likely fewer pieces in total. This effect can also be observed from the size of the generated CVRP instance. The 20/10/5/1 rule resulted in a new instance with 855 customers (nodes), while the 128/64/32/16/8/4/2 rule generated a network with 572 customers. Moreover, the coarser splitting rule of 128/64/32/16/8/4/2 resulted in a cost of 4424.64 that improves upon the cost of the rule 20/10/5/1 (proposed by the VRPHAS algorithm) by 1.34%. Impact of coarser rules for customers further away from the depot: The second motivation behind our proposed AASA rule is that using coarser rules for the demands with a larger distance from the depot and splitting closer demands into smaller pieces results in lower solver runtime and possibly a better solution. The intuition behind this observation is that as the distance between a customer and the depot increases, each visit to that customer would significantly increase the cost. Therefore, it is desirable to satisfy the demand of further customers within the fewest possible number of visits and that is only possible by applying coarser splitting rules to those nodes. Moreover, by splitting closer-to-depot customer demands into smaller pieces, we provide the opportunity for the vehicles returning to the depot to utilize their remaining capacity to fulfill smaller demands and, therefore, minimize the fraction of their unused capacity. It is important to note that all of these intuitive statements are based on the fact that after splitting demands and generating a new network with a larger number of customers, we use the VRPH solver and basically solve the generated instance by a number of heuristic and metaheuristic methods. Figure 2a-c illustrate the above observation for the \(SD6\) instance from [34]. The best-known solution for this instance is 830.86. In Figure 2a,b, the results of using the 80/40/20/10 and 40/20/10 rules are shown. Although these two rules alone provide acceptable results with the costs of 863.43 and 881.21, respectively, we observe that by using a combination of the two rules as shown in Figure 2c, we can achieve lower cost of 862.38.