# AAGA: A Priori Adaptive Splitting Algorithm for the Split Delivery Vehicle Routing Problem
###### Abstract
Such methods typically formulate the SDVRP as a mixed integer linear program (MILP) [8] and propose different variants of branching algorithms such as branch-and-cut [9; 10], branch-and-price [11; 12], and branch-and-price-and-cut [13; 14] for various versions of the SDVRP. However, with increasing the size of the problem, the corresponding MILP models will soon become intractable for exact solutions. To tackle this issue, various traditional approximation techniques, heuristics and metaheuristics have been proposed to deal with the high time-complexity of the large SDVRP models. For instance, a max-min clustering before solving the optimization problem is proposed in [15]. Tabu search has been used in several papers [16; 17; 18]. In [16], the authors proposed an approach relying on simulated annealing to solve the SDVRP. Other lines of research propose methods utilizing ant colony optimization [19; 20], genetic algorithms [21; 22], and particle swarm optimization [23; 24], to solve the SDVRP. Using column generation is another optimization technique that has been applied to the SDVRP by [8; 25]. The authors in [26] applied the cutting plane method to tackle the time complexity of the SDVRP. Recently, the authors in [27] introduced a metaheuristic approach incorporating several mathematical programming components within an iterative local search framework. We refer to this method as ILS-MIP in the rest of the paper. ILS-MIP starts from an initial set of solutions obtained using the I1 Solomon heuristic followed by a perturbation step (to escape local optima), a local search step using classical neighborhood search heuristics, and several steps based on hybrid components. The hybrid components are called only if the incumbent solution of the search is not improved after a number of steps. The hybrid components encompass a mixed integer program (MIP)-based improvement heuristic performing two operations of inserting splits or removing potential unnecessary splits. Another used hybrid component is based on converting the current SDVRP solution to a CVRP instance and using a hybrid genetic search (HGS) framework [28] specialized to solve a CVRP. An MIP model is also used in the third component of the hybrid step where a residual problem is constructed by removing the edges that are not used in any solution of the current set of solutions. The residual problem is then solved using an MIP solver. Finally, the fourth component uses the branch-and-cut (BC) framework proposed in [29]. While ILS-MIP is a powerful and effective methodology, its complexity and significant runtime for larger instances makes it challenging for addressing real-world problems. Although the state-of-the-art algorithms for the SDVRP are known for their ability to produce high-quality solutions, they often pose challenges in terms of complexity and practical implementation. In response to these challenges, the authors in [30] introduced an efficient algorithm that decomposes the SDVRP into two sub-problems. First, a demand-splitting rule is applied to all customers. The idea of splitting the customer demands was introduced in [31]; the authors propose a heuristic solution for SDVRP with time windows based on the column generation approach. In this paper, it is assumed that the demand of each customer is served by a number of orders selected from a set of feasible orders where each order is a pre-determined discrete split of the customer demand. The authors in [30] proposed applying the a priori splitting strategy in which the demand of each customer is split into smaller demands, each representing a new customer located in the same position as the original customer. As a result, a new problem instance is generated with an increased number of customers. Second, the new problem is assumed to be an instance of the CVRP which is solved using existing powerful CVRP solvers. The transformation of the SDVRP to a CVRP not only facilitates the implementation of SDVRP but also enables leveraging the rich literature on the CVRP.