# 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  
Nearest Neighbor (H.2)  
The Nearest Neighbor heuristic is based on the premise that nearby solutions in the search space tend to be similar to each other. It iteratively selects the Nearest Neighbor to the current solution, based on some distance or similarity criterion defined by the specific problem. The current solution is updated with this selected neighbor, and the process is repeated until some termination criteria are reached. The general procedure of H.2 is shown in Algorithm 2. ```
1:Input: Initial node (initial_node), List of customers (customers), Distance matrix (distance), Maximum capacity (maximum_capacity), Initial set of visited nodes (visited_nodes). 2:Output: List of nodes representing the route (NN) with starting_node
3: If nodes_visited is None, then it is initialized as an empty set. 4: Initialize the nearest neighbor (NN) path with initial_node. 5: Initialize the current capacity (current_capacity) to 0 4. 6: Initialize the number of clients (n) with the length of clients 5. 7: Add initial_node to visited_nodes
8: As long as the length of NN is less than n.  a. Set k in the last node of NN. b. Initialize a dictionary (nn) with the distances from k to each client not in NN and  not in visited_nodes  c. If nn is empty, break the loop  d. Find the nearest neighbor (new) from nn by selecting the key with the minimum value. e. Check if adding this client stays within max_capacity:  i. If yes, add the second node from new to NN. 1. Add demand from new[0,1] to current_capacity 2. 2. Add new[0,1] to visited_nodes 2. 2. Add new[0,1] to visited_nodes 2. 2. Add new[0,1] to visited_nodes  2. Otherwise, break loop
9:Return NN

#### 3.4.3 Heuristic Algorithms

Local Search (H.3)

The Local Search heuristic searches within a search space for a solution, moving from one node to another, through local changes. This method is based on the notion of neighborhood, where solutions are related to each other through small local modifications, improving the quality of the solution found. The general procedure of H.3 is shown in Algorithm 3. ```
1:Input: Initial Route (NN), Distance Matrix (distance)
2:Output: Improved route after local search (NN)
3: Initialize min_change to 0
4:For i from 0 to length(NN)--2:  a. For j from i + 2 to length(NN)--1:  i. Calculate current_cost as distance[(NN[i], NN[i + 1])] + distance[(NN[j],  NN[j + 1])]  ii. Calculate new_cost as distance[(NN[i], NN[j])] + distance[(NN[i + 1],  NN[j + 1])]  iii. Calculate change as new_cost--current_cost iv. If change < min_change: 1. Set min_change to change 2. Set min_i to i 3. Set min_j to j
5:If min_change < 0:  a. Invert the segment NN[min_i + 1 : min_j + 1]. 6:Returns NN
Local initialization counter = 0 # Execution of the Algorithm with Local Search while True a. Increment counter by 1 b. Compute first as the sum of distances for all paths in routes c. For each route in routes i. Copy previous_route from current route ii. Apply Local_Search to the current route iii. Calculate dist_current as the distance from previous_route iv. Calculate dist_new as the distance from the current_route d. Calculate ultima as the sum of distances of all routes in routes. e. Calculate interchange as the absolute difference between last and first f. If interchange == 0, break the loop. ```
**Algorithm 3** The pseudo-code of Local Search (H.3) algorithm

#### 3.4.4 Heuristic Algorithms

The combination of these two approaches can be very effective. First, Nearest Neighbor provides an initial solution that is fast and generally good, but may not be optimal. Then, Local Search is used to refine that solution, exploring the space of nearby solutions to find a locally or even globally optimal solution. The general procedure of H.4 is shown in Algorithm 4. ```
1:Inputs: List of routes (routes), Distance matrix (distance), Function for calculating the route distance (calculate_route_distance)
2:Output: Improved routes after local search (routes)
3: Initialize the solution as a copy of the initial routes. 2.