# Route Optimization for Open Vehicle Routing Problem (OVRP): A Mathematical and Solution Approach
## 3 Materials and Methods
### Solution and Analysis of Results
#### 3.4.2 Heuristic Algorithms
4: Initialize counter to 0
5: As long as true  
a. Increment counter by 1  
b. Compute first as the sum of compute_path_distance for all paths. c. For i from 0 to length(routes):  
i. Copy previous_route from routes[i]. ii. Apply Local_Search to routes[i]. iii. Calculate current_distance as calculate_distance_route(previous_route, distance)  
iv. Calculate new_distance as calculate_route_distance(routes[i], distance)  
d. Calculate last as the sum of calculate_route_distance for all routes. e. Calculate interchange as abs(last--first)  
f. If exchange == 0, break loop. 6:Return routes
```

**Algorithm 4** The pseudo-code of Nearest Neighbor + Local Search algorithm

## 4 Results

In this section, we develop a comparison of the results of LKH-3, AMPL, H.1, H.2, H.3, and H.4 to solve 58 sets of instances, varying N and K. A first comparative experience is raised from the Local Search heuristic, which adopts a different approach by considering each node individually, disregarding the distance between them. This approach may seem contradictory, especially in comparison with Greedy and Nearest Neighbor, which can sometimes overlook some nodes in certain cases. Figure 3 shows that algorithms H.2 and H.3 for the case A-n45-k7 (instance A; number of nodes 45; number of vehicles 7), in some cases, fail to completely cover the delivery due to capacity constraints. The coding specified that a list is generated for each vehicle, while each node is added to the list until the capacity of the list is completed, based on the sum of the demand of each client. This tendency is seen more in samples which have a more grouped set of nodes within the scenarios. This can be seen within instances such as E-n76-k. The choice of the number of vehicles should be considered as a function of the number of nodes and their associated demands. For example, in the case of P-n55-k8, although it could be handled with seven vehicles, the application of Local to NN demonstrates that incorporating an eighth vehicle significantly improves the solution. Figure 3: A comparison of H.2 and H.3 algorithms for the A-n45-k7 instance. In instances such as P-n76-k4 and P-n76-k5, where a per-vehicle load of 300 and 280, respectively, is present, it is evident that capacity affects route completeness. While P-n76-k4 leaves nodes uncovered, P-n76-k5 manages to cover the entire route, albeit with a higher associated cost. It is crucial to highlight that the optimal performance of Local Search is favored by the implementation of a function or heuristic that sorts the list at the beginning of the process, which contributes to improve the efficiency and effectiveness of the algorithm. On the other hand, the strategic combination of Nearest Neighbor with the Local Search 2-opt method exhibits remarkable results for the A-n46-k7 instance (see Figure 4), generating solutions close to those obtained by more complex methods such as LKH-3 and AMPL. As for the comparison with the LKH-3 algorithm, the results of each approach highlight the diversity of strategies available to solve the OVRP. The AMPL formulation reveals areas where the mathematical modeling can be improved, as seen in the GAP (%), which indicates how close the solution found is to the known or theoretical global optimum. In mathematical optimization and linear or mixed programming, GAP refers to the \"Absolute Programming Gap\", the difference between the best value obtained and the best theoretically possible value. This underlines the effectiveness of the modeling in approaching the optimum, providing a key measure of the quality and accuracy of the method used. In the modeling proposed in the research, by instances, there were never any drops beyond 50%. The Greedy algorithm and the NN with 2-opt combination, on the other hand, stand out by offering quality solutions in shorter computational times, providing valuable insight for practical logistics applications.