# Route Optimization for Open Vehicle Routing Problem (OVRP): A Mathematical and Solution Approach
## 1 Introduction  
The need to move from one point to another has been a constant in human evolution for thousands of years. Although the uses and importance have increased significantly over time, the fundamental goal of facilitating movement persists. This drive for mobility has been crucial in the commercial arena throughout history. From ancient trade routes such as the Silk Road, which connected the East and West through Asia, Europe and Africa, to the present, trade and product delivery have undergone a remarkable evolution, supported by significant advances in route planning. Consequently, route planning has become a priority to reduce travel times and distances in product delivery. One of the first problems posed to address this situation was the Traveling Salesman Problem (TSP), which seeks to find the shortest route for a traveling salesman who must visit a specified group of cities and return to the original starting point [1].  
This problem became generalized, giving rise to the vehicle routing problem (VRP), this involves determining a set of routes to satisfy the transportation requests with the vehicle fleet at the minimum cost and return to the depot while complying with a Hamiltonian cycle (see Figure 1a), optimizing the execution of all routes [2]. Over time, some companies have chosen to outsource logistics and transportation, allowing them to focus on their core competencies and save costs by outsourcing these functions to third-party logistics providers [3, 4].  
However, for route planning performed by these third-party logistics providers, the VRP is not sufficient, as vehicles do not necessarily return to the depot at the end of the route. To solve this complexity, the open vehicle routing problem (OVRP) is used, a variant of the VRP that takes into account the vehicle capacity and does not force a return to the starting point, allowing each route to end at one of the customers [5]. Other factors, such as the number of vehicles and demand per customer, are also considered in this problem (see Figure 1b).  
Given the complexity and relevance of OVRP in real logistics scenarios, addressing its challenges requires advanced heuristic approaches and optimization techniques. This study aims to carry out an in-depth analysis of specific optimization tools for this problem, along with the implementation of two heuristics for its resolution. The comparison of results will result in an increase in heuristic knowledge to cope more effectively with OVRP. The main contributions of this work are as follows:  
(1) This paper addresses the open vehicle routing problem (OVRP) by optimizing routes for a fleet of vehicles serving geographically dispersed customers.  
(2) This paper proposes a heuristic approach, explores the complexities of the open vehicle routing problem (OVRP) and compares the results with state-of-the-art methods such as the Lin-Kernighan algorithm (LKH-3) and the algebraic modeling language AMPL. LKH-3 is an algorithm recognized for its ability to efficiently solve vehicle routing problems using advanced Local Search and combinatorial optimization techniques [6]. On the other hand, AMPL is a widely used algebraic modeling environment that facilitates the formulation and solution of complex mathematical models such as OVRP [7].  
(3) This study not only highlights the effectiveness of mathematical modeling, but also explores and demonstrates the practicality of heuristic algorithms such as Greedy, Nearest Neighbor and 2-opt to provide quality solutions.  
(4) The results and findings show a solid basis for the continuation of future research, which can focus on the optimization of the combination of heuristics and their strategic placement within the model.  
The remainder of this paper is organized as follows. Section 2 discusses related work. Section 3 describes and proposes the methodology. Section 4 presents the comparative results of the methods and heuristics. Section 5 presents conclusions and some possible future studies.