# Route Optimization for Open Vehicle Routing Problem (OVRP): A Mathematical and Solution Approach
## 3 Materials and Methods
### Formulation of the Mathematical Model  
The analysis and formulation of the open vehicle routing problem (OVRP) is based on the modification of the mathematical model previously proposed by the authors of [30] for the vehicle routing problem with pickup and delivery (VRPD). The adaptation of this model involves substantial adjustments to the constraints, with the objective of providing greater flexibility in vehicle routing. Initially, the constraint that dictates that each route must start and end at the depot is removed, so vehicles start and end their routes at any customer.  
In addition, a modification is made to the restriction associated with loading and unloading to adapt it to the OVRP context. In this sense, the total load linked to customers can be adjusted so as not to exceed the vehicle capacity, without the need to return to the depot. The precedence constraint, which previously specified a certain order of visitation for loading and unloading customers, is excluded. This adjustment translates into greater flexibility in logistics operations by eliminating the imposition of a predefined order for customer visits. These adjustments aim to optimize efficiency in route planning, with the objective of minimizing the total distance traveled by vehicles, according to the specific requirements of the adapted problem. This approach seeks to meet the demands of the OVRP, improving logistics management and maximizing the utilization of vehicle resources. Table 2 presents the sets, parameters and variables of the model.  
The goal is to minimize the total cost traveled. The mathematical model of the OVRP is as follows:  
\[Min\ Z=\sum_{i,j\in ARCS}C_{ij}X_{ij} \tag{1}\]  
\[\sum_{i\in N\backslash\{j\}}X_{ij}+\sum_{j\in N\backslash\{i\}}X_{ij}=1\ \forall_{i}\varepsilon N \backslash\{1\} \tag{2}\]  
\[u_{i}-u_{j}+qq*X_{ij}\leq qq-d_{j}\forall_{ij}:i\
eq 1,j\
eq 1 \tag{3}\]  
\[\sum_{i,j\in ARCS}d_{j}X_{ij}\leq qq\forall_{ij}:i\
eq 1 \tag{4}\]  
In the proposed model, the objective function (1) seeks to minimize the total cost of driving. The constraints of the problem are structured to ensure the feasibility and efficiency of the solutions: constraint (2) combines the unique visit to each customer and the unique departure of each vehicle. For each customer j other than the initial depot, the sum  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Description** \\ \hline E & Instance \\ N & Number of nodes within the instance \\ K & Number of vehicles used in the instance \\ LKH-3 & Lin–Kernighan–Helsgaun \\ AMPL & A Mathematical Programming Language \\ H.1 & Heuristic algorithm—Greedy \\ H.2 & Heuristic algorithm—Nearest Neighbor \\ H.3 & Heuristic algorithm—Local Search \\ H.4 & Heuristic algorithm—Nearest Neighbor + Local Search \\ \hline \hline \end{tabular}
\end{table}
Table 1: The definition of symbols.  
of Xij over all nodes i (2) ensures that each customer is visited exactly once. Simultaneously, for each node i, the constraint ensures that each vehicle leaves a customer exactly once, excluding the end of its route. In addition, the constraints address subtour elimination and condition the final route, where the subtour elimination variable, combined with the per-route vehicle capacity, must be less than or equal to the vehicle capacity minus customer demand for all arcs, excluding those connecting the initial depot to itself (3). Finally, a capacity constraint (4) is imposed, where the sum of the demand for Xij for all nodes j must not exceed the maximum vehicle capacity, for each node i other than the initial depot. These constraints are crucial for the effective formulation and resolution of the open vehicle routing problem (OVRP), ensuring efficient and practical route optimization.