# 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
Taken together, this evaluation provides a comprehensive view of the suitability of different strategies for addressing OVRP, which would be further complemented by visual representations of the results obtained (see Figure 5). The comparison of the evaluated instances with respect to the applied heuristics (H1, H2, H3, H4) and their performance relative to the Best Known Solutions (BKSs) and the mathematical solution languages LKH-3 and AMPL. Overall, the combination of Nearest Neighbor and Local Search (H4) stands out as the most efficient among the heuristics, providing costs close to the Best Known Solutions (BKSs) in most instances. On the other hand, LKH-3 consistently provides solutions very close to BKSs, demonstrating its high efficiency. AMPL, while showing some variability, has the potential to improve with adjustments to the mathematical modeling. Figure 4: A comparison of H2 and H3 algorithms for the A-n46-k7 instance. Best Known Solutions (BKSs) refer to the best known optimal or best-quality solutions. These solutions serve as benchmarks to evaluate and compare the performance of the algorithms and heuristics used in solving the problem. Figure 6 shows detailed results considering N, K and BKS parameters. The C1 instance, with 51 nodes and 5 vehicles, highlights the geographic complexity and specific constraints that influence the formulation of solutions. The smaller E-n23-k3 instance, with 23 nodes and 3 vehicles, presents unique challenges related to carrying capacity and node density. On the other hand, E-n51-k5, with 51 nodes and 5 vehicles, is characterized by variations in vehicle capacity and node layout. In scenario F11 (72 nodes, 4 vehicles), low carrying capacity emerges as a distinguishing factor, while P-n55-k7 (55 nodes, 7 vehicles) stands out for the presence of a larger number of vehicles. In terms of performance, the mathematical solution languages LKH-3 and AMPL are remarkably close to BKSs in most instances, reflecting their high efficiency and accuracy. LKH-3, in particular, shows consistency in obtaining solutions close to BKSs, highlighting its robustness in solving the OVRP. AMPL, although it shows some variability, evidences its potential for improvement through precise adjustments in the mathematical modeling. The heuristics, especially the combination of Nearest Neighbor and Local Search (H4),

Figure 5: A general comparison of results. Figure 6: Best Known Solution (BKS) results. also show competitive performance, approaching BKS values considerably in several instances. This detailed analysis underlines the importance of using a balanced approach combining mathematical and heuristic methods to efficiently address OVRP, highlighting the relevance of the proximity of the results to the BKS as a key indicator of the effectiveness of the applied strategies. The synergy between heuristics highlights their practical utility, especially in logistics contexts where efficiency in route planning plays a crucial role [31; 32]. It is imperative to note that the variation in solution quality between instances can be attributed to the NP-Hard nature of OVRP. Figure 7 provides a detailed comparison of the heuristics applied in the E-n30-k3 and P-n55-k7 instances, highlighting the differences in the costs obtained and the efficiency of each approach. The E-n30-k3 instance, containing 30 nodes and 3 vehicles, and the P-n55-k7 instance, with 55 nodes and 7 vehicles, represent two scenarios with different scales and complexity in terms of node capacity and distribution. In the E-n30-k3 instance, the Nearest Neighbor heuristic combined with Local Search (H4) proves to be particularly effective, achieving costs close to those obtained by the advanced LKH-3 and AMPL algorithms, indicating their ability to provide high-quality solutions in reduced computational time. The Greedy (H1) and Nearest Neighbor (H2) heuristics also show solid performance, albeit with slightly higher costs, reflecting their efficiency on smaller-scale problems.