# Improved Ant Colony Algorithm for the Split Delivery Vehicle Routing Problem
## 2 Related Work
### Exact Algorithms  
The earliest exact algorithm was proposed by [PERSON] et al. [41]. In their research, they proved an integer linear programming formula including new inequalities, and they designed a constraint relaxation algorithm. [PERSON] et al. [28] proposed two exact branch-and-cut algorithms. [PERSON] et al. [29] studied the two-dimensional constrained vehicle routing problem with split deliveries. They proposed an integer linear programming model for the problem and used a branch-and-cut method to solve it. [PERSON] et al. [30] presented a new arc-based mixed-integer formulation for the pickup and delivery problem with split loads and transshipments. The problem studied by [PERSON] et al. [31]  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Type** & **Algorithm** & **Author(s)** \\ \hline \multirow{8}{*}{Exact algorithm} & \multirow{4}{*}{Branch-and-cut algorithm} & [PERSON] et al. [28] \\  & & [PERSON] et al. [29] \\  & & [PERSON] et al. [30] \\  & & [PERSON] et al. [31] \\ \cline{2-3}  & \multirow{2}{*}{Branch-and-price algorithm} & [PERSON] et al. [32] \\  & & [PERSON] et al. [33] \\ \cline{2-3}  & \multirow{2}{*}{Branch-price-and-cut algorithm} & [PERSON] et al. [34] \\  & & [PERSON] et al. [35] \\ \hline \multirow{8}{*}{Heuristic algorithm} & [PERSON] et al. [8] \\  & [PERSON] et al. [9] \\ \cline{2-3}  & [PERSON] et al. [36] \\ \cline{2-3}  & \multirow{2}{*}{Genetic algorithm} [PERSON] et al. [10] \\  & [PERSON] et al. [11] \\ \cline{2-3}  & [PERSON] et al. [37] \\ \cline{2-3}  & \multirow{2}{*}{Particle swarm algorithm} [PERSON] et al. [12] \\  & [PERSON] et al. [13] \\ \cline{2-3}  & [PERSON] et al. [14] \\ \cline{2-3}  & [PERSON] et al. [15] \\ \cline{2-3}  & [PERSON] [16] \\ \cline{2-3}  & [PERSON] et al. [17] \\ \cline{2-3}  & [PERSON] et al. [38] \\ \hline \multirow{3}{*}{Ant colony algorithm} [PERSON] et al. [18] \\  & [PERSON] et al. [19] \\ \cline{1-1}  & [PERSON] et al. [20] \\ \hline \multirow{2}{*}{Simulated annealing algorithm} [PERSON] et al. [39] \\ \cline{1-1}  & [PERSON] et al. [40] \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of related algorithms.  
is to design a lowest-cost route for a capacitated vehicle to transport goods among a set of customers, considering the possibility of splitting customer demands. They proposed a new branch-and-cut algorithm to find optimal solutions. A master problem was used to solve a relaxed mixed-integer programming model, while a subproblem was used to check the feasibility of the master solutions and generate valid cuts when they were infeasible. [PERSON] et al. [32] addressed the pickup and delivery vehicle routing problem with split demands. They introduced effective inequalities and designed a branch-and-price algorithm that utilized a tailored pricing routine and branching strategy and embedded a rounding heuristic to accelerate pruning. [PERSON] et al. [33] investigated the multi-depot vehicle scheduling problem, considering factors such as time windows and demand split, and proposed two algorithms, a branch-and-price and a branch-and-benders decomposition, to solve this problem. [PERSON] et al. [34] studied the commodity-constrained SDVRP, and a branch-price-and-cut algorithm was proposed. [PERSON] et al. [35] investigated the SDVRP with a multi-time window, transformed the problem into a three-index vehicle-flow model and a set-covering model, and proposed a branch-price-and-cut algorithm to solve the problem.  
Exact algorithms are often used to solve small-scale problems, because when the problem size becomes larger, the computation time of exact algorithms also increases significantly. The time cost of using exact algorithms is too high. Therefore, heuristic algorithms are usually used to solve larger-scale problems.