# Improved Ant Colony Algorithm for the Split Delivery Vehicle Routing Problem
## 3 Modeling the SDVRP  
This paper studies the split delivery vehicle routing problem with a single depot, a single vehicle type, no time window constraints, and loading only. The symbol definitions in the mathematical model are shown in Table 2.  
Model assumptions:  
1. The distance between any two customer points is symmetric, which can be expressed as \(d_{ij}=d_{ji}\).  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Definition** \\ \hline \(N\) & The number of customers. \\ \(M\) & The minimum number of vehicles, the value of which is shown in Equation (1). \\ \(V\) & The set of depot and customer points, including 0 and \(V_{c}\), where 0 represents the depot and \(V_{c}\) = {1, 2,..., \(N\)} represents the customer set. \\ \(d_{ij}\) & The distance between customers \(i\) and \(j\). \\ \(q_{i}\) & The demand of customer \(i\). \\ \(Q\) & The capacity of each vehicle. \\ \(x_{ij}^{m}\) & The indicator of whether edge (\(i\), \(j\)) has been traversed by vehicle \(m\), as shown by \\  & Equation (2). \\ \(y_{i}^{m}\) & Customer \(i\)’s demand supplied by vehicle \(m\). \\ \hline \hline \end{tabular}
\end{table}
Table 2: List of parameters and variables used in the SDVRP.  
2. The distance between the customer points conforms to the triangle inequality and can be expressed as \(d_{ik}+d_{kj}>d_{ij}\).
3. The demand of each customer should be met, and this demand can be met by one or more vehicles.
4. All vehicles start from the depot and return to the depot after completing the task, and the vehicles cannot be overloaded. \[M=\left[\sum_{i=1}^{N}q_{i}/Q\right]\] (1) \[x_{ij}^{m}=\begin{cases}1,&\text{vehicle passing }(i,j)\text{ in route }m\\ 0,&\text{otherwise}\end{cases}\] (2)  
[PERSON] et al. [3] proposed the concept of the k-split cycle, as shown in Definition 1, and proved that there is no k-split cycle in the best solution of the SDVRP, which provides a reference for the model construction in this paper.  
**Definition 1**.: _If there are \(k\) routes (\(r_{1}\), \(r_{2}\), \(\ldots\), \(r_{k}\)) in the SDVRP, for \(k\) customer points (\(v_{1}\), \(v_{2}\), \(\ldots\), \(v_{k}\)), if \(r_{m}\) contains \(v_{m}\), \(v_{m+1}\) (\(m=1\), \(2\), \(\ldots\), \(k-1\)) and \(r_{k}\) contains \(v_{1}\), \(v_{k}\), it is called a k-split cycle._  
_Figure 1 shows a 3-split cycle._  
The goal of SDVRP is to reasonably arrange the vehicle transportation scheme to make the vehicle transportation cost as small as possible by having the shortest total vehicle transportation path and the fewest distribution vehicles. The objective function can be written as follows:  
\[min\sum_{m=1}^{M}\sum_{i=0}^{N}\sum_{j=0}^{N}d_{ij}x_{ij}^{m} \tag{3}\]  
The constraint conditions of the model are:  
\[\sum_{i=0}^{N}x_{ik}^{m}=\sum_{j=0}^{N}x_{kj}^{m};k=0,1,\ldots,N,m=1,2,\ldots,M \tag{4}\]  
\[\sum_{m=1}^{M}y_{i}^{m}=q_{i};i=1,2,\ldots,N \tag{5}\]  
\[\sum_{m=1}^{M}\sum_{i=0}^{N}x_{ij}^{m}\geq 1;j=0,1,\ldots,N \tag{6}\]  
\[\sum_{m=1}^{M}\sum_{i,j\in V_{c}}x_{ij}^{m}\leq|V_{c}|-1 \tag{7}\]  
Figure 1: 3-split cycle.  
\[\sum_{i=1}^{N}y_{i}^{m}\leq Q;m=1,2,\ldots,M \tag{8}\]  
\[q_{i}\geq y_{i}^{m}\geq 0;i=1,2,\ldots,N,m=1,2,\ldots,M \tag{9}\]  
\[x_{ij}^{m}\in\{0,1\};i,j=1,2,\ldots,N,m=1,2,\ldots,M \tag{10}\]  
Equation (3) is the objective function, indicating that the total distance path of the vehicles is the shortest. Equation (4) indicates that the number of vehicles entering a certain customer point is consistent with the number of vehicles leaving the customer point. Equation (5) means that the sum of the customer's demand satisfied by each vehicle is equal to the customer's total demand. Equation (6) ensures that each customer point is visited at least once. Equation (7) is used to eliminate the k-split cycle. Equation (8) indicates that the vehicle capacity cannot be exceeded. Equation (9) means that the demand of a customer satisfied by each vehicle should not exceed the maximum demand of the customer. Equation (10) represents the value range of decision variables.