# 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.2 AASA Algorithm  
The above observations highlight the significance of applying an adaptive splitting rule for different customers instead of using a fixed splitting rule for all customers, as in VRPHAS. Motivated by these observations, we incorporate the following factors into AASA:  
* Vehicle capacity: As implied by [30], it makes sense to look for the splitting rule as a function of the vehicle capacity. This not only presents a structured representation with vehicle capacity as the kernel allowing for better generalization but also leads the policy towards leaving the lowest portion of the vehicles' capacities unused, and consequently, increases the vehicles' utilization. * Customer location: We believe one potential improvement to the VRPHAS splitting rule is to personalize the rule for each customer considering its distance from the depot. We observe that if the customers that are located further from the depot are visited by one (or very few) vehicle(s), the total travel cost is lower. Otherwise, if a long distance needs to be traversed multiple times, the cost will be negatively impacted. This can be avoided by coarsening the splitting rule for further customers. In AASA, the impact of customers' locations is addressed by partitioning the customers into a number of clusters based on their distance from the depot. We then use a different splitting rule for each cluster. A coarser splitting rule is used for clusters of customers further from the depot while finer rules are applied to the clusters closer to the depot. * Customer demand: Another important factor in the adaptation of the splitting rule is the demand of customers. Depending on how large the demand is, the splitting rule can be applied in full or partially to result in an appropriate number of additional demand points with appropriate demand values. In order to create the exponential pattern in the splitting rule, we propose to decompose the customers' demands based on the different powers of prime numbers. For instance, the demand of a customer with \(d=199\) served by vehicles with capacity \(Q=200\) can be decomposed as \(d=2^{7}+2^{6}+2^{2}+2^{1}+1\) if \(p=2\), and \(d=2\times 3^{4}+3^{3}+3^{2}+1\) if \(p=3\). Leveraging the above factors, the AASA solution framework is shown in Figure 3. First, AASA employs a clustering algorithm to partition the customers into multiple levels. In our experiments, we used a simple distance-based clustering as follows:  
\[label(v)=\ell,\quad\text{if}\quad\frac{\ell-1}{L}dist_{max}<dist(v,0)\leq\frac {\ell}{L}dist_{max},\quad\ell\in\{1,\dots,L\} \tag{5}\]  
Figure 2: Impact of using splitting rules with different granularity according to the customers’ distance to the depot. where \(L\) is the number of levels, and \(dist_{max}\) is the maximum customer-depot distance among all customers, i.e, \(dist_{max}=max_{v}\ dist(v,0)\). As a result of this clustering rule, first, the customers are separated with \(L\) uniformly spaced rings around the depot. Second, for the customers at each level, the same splitting rule is applied. After all the demands are split, a CVRP instance is generated. Finally, the VRPI solver is used to solve the resulting CVRP instance. The pseudo-code for AASA is given in Algorithm 1. The algorithm starts by taking as input the SDVRP instance as a graph \(G=(V,E)\), the vehicle capacity \(Q\), the vector of customer-depot distances denoted by \(\vec{dist}\) where \(\vec{dist}(v)=dist(v,0)\), and the vector of customer demands \(\vec{D}\). Next, it computes \(d\), the greatest common divisor (\(gcd\)) of the demands vector and the vehicle capacity, which will be used as a parameter in the adaptive splitting rule. The vehicles may carry goods only in quantities that are multiples of \(d\) units. This is to control the granularity of the splitting rule. Next, the demand vector is scaled down by \(d\) and averaged over the customers to find \(\mu\) that is used in finding \(s_{max}\) determining the largest quantity of goods that is demanded by the customers in the equivalent CVRP model.