# The Vehicle Routing Problem: State-of-the-Art Classification and Review
## 3 VRP and Its Variants  
### Vrp  
In addition to the classical VRP, several variants have also been studied. Capacitated VRP (CVRP), VRTW, VRP with heterogeneous fleets (HFVRP), time-dependent VRP (TD-VRP), and multi-depot VRP (MDVRP) are some of these variants. The classical VRP can be described as follows. Let \(\text{G}=(V,\,A)\) be a graph, where \(V=\{v_{0},v_{1},\,v_{2},\,\ldots,\,v_{N}\}\), where \(\{v_{1},\,v_{2},\,\ldots,\,v_{N}\}\) is the node set representing customers to be served and \(v_{0}\) is the depot. Each customer is characterized by a demand \(D_{i}\). \(A=\big{\{}(v_{i},\,v_{j}):\,v_{i},\,v_{j}\in V\big{\}}\) is the arc set (subscript indicates sequence) linking nodes \(i\) and \(j\) with a distance \(d_{ij}\). Let \(\text{M}_{m}=\{m_{1},m_{2},m_{3},\ldots,m_{m}\}\) denote the vehicle set, where each vehicle has a maximum load capacity \(cap_{m}\), meaning the total load of vehicle \(m\) cannot exceed the maximum load capacity \(cap_{m}\). To reflect a real distribution scenario accurately, different features are considered according to the settings of heterogeneous models. The goal of the VRP is to derive optimal vehicle routes such that each customer is visited exactly once by one vehicle and each vehicle starts and ends its route at the depot. The following assumptions are adopted:  
1. The depot has a demand equal to zero. 2. Each customer location is serviced by only one vehicle. 3. Each customer's demand is indivisible. 4. Each vehicle shall not exceed its maximum load capacity \(cap_{m}\). 5. Each vehicle starts and ends its route at the depot. 6. Customer demand, distribution distances between customers, and delivery costs are known. The notations used for problem definition are summarized as Tables 1-3. Traditional logistics models focus on minimizing the total cost of a network. This is where the concept of the VRP is best applied. We follow this concept and add the fixed cost \(fc_{m}\) of a vehicle, which represents rent cost or operating costs, to the total cost to minimize the total number of vehicles. We also include the variable cost \(vc_{m}\) of delivery using each type of vehicle to optimize vehicle scheduling. Additional constraints appear in the target calculation in the form of penalty functions to enforce vehicle limit constraints. The objective of minimizing the total cost is defined as follows:  
\[\text{Minimize}\ \sum_{m=1}^{M}\sum_{i=0}^{N}\sum_{j=0}^{N}X_{ij,m}fc_{m}+\sum_ {m=1}^{M}\sum_{i=0}^{N}\sum_{j=0}^{N}d_{ij}Dm_{ij,m}vc_{m} \tag{1}\]  
subject to the following constraints:  
Routing:  
\[\sum_{i=1}^{N}X_{i0,m}=1\ \forall\ m\ \in\text{M}_{m} \tag{2}\] \begin{table}
\begin{tabular}{c c} \hline \(V\) & Node set, where \(v_{0}\) is the depot and \(\{v_{1},v_{2},\ldots,v_{N}\}\) are customers \\ \hline \(i\),\(j\) & Subscripts of the customer nodes, \(i,j=1,2,\ldots N\) \\ \hline \(A\) & \(A=\left\{\left(p_{i},\ v_{j}\right):\ v_{i},\ v_{j}\in V\right\}\) is arcs set linking nodes \(i\) and \(j\) \\ \hline \(\text{M}_{m}\) & The set of vehicles with \(m\) types \\ \hline \end{tabular}
\end{table} 
Table 1: Sets and indices of VRP. \begin{table}
\begin{tabular}{c c} \hline \(D_{i}\) & Demand of customer \(i\) \\ \hline \(d_{ij}\) & Distance between nodes \(i\) and \(j\) \\ \hline \(veh_{m}\) & Maximum available number of each vehicle type \\ \hline \(cap_{m}\) & Maximum load capacity of vehicle type \(m\) \\ \hline \(fc_{m}\) & Fixed cost of vehicle type \(m\) \\ \hline \(vc_{m}\) & Variable cost of vehicle type \(m\) \\ \hline \(Dm_{ij,m}\) & Amount carried using vehicle type \(m\) from \(i\) to \(j\) \\ \hline \end{tabular}
\end{table} 
Table 2: Parameters of VRP. \begin{table}
\begin{tabular}{c c} \hline \(X_{ij,m}\) & Value of one if vehicle type m travels from node \(i\) to \(j\). Otherwise, value of zero \\ \hline \end{tabular}
\end{table} 
Table 3: Decision variable of VRP.