Route Optimization for Open Vehicle Routing Problem (OVRP): A Mathematical and Solution Approach

Abstract

In the everchanging landscape of human mobility and commerce, efficient route planning has become paramount. This paper addresses the open vehicle routing problem (OVRP), a major logistical challenge in route optimization for a fleet of vehicles serving geographically dispersed customers. Using a heuristic approach, we explore the complexities of OVRP, comparing the results with advanced optimization methods. This study not only highlights the effectiveness of mathematical modeling, but also explores the practicality of heuristic algorithms such as Greedy, Nearest Neighbor and 2-opt to provide quality solutions. The findings highlight the nuanced interplay between solution quality and computational efficiency, providing valuable insights for addressing real-world logistics challenges. Recommendations delve into optimization opportunities and the integration of emerging technologies, ensuring adaptable solutions to the intricate the problem of open vehicle routing.

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.

2. Related Work

The literature frames a series of works related to the vehicle routing problem from the perspective of the number of distribution centers. From the context of single-depot route planning, recent research contributions included those developed by Zhang, Y. et al. (2024) [8]; Yousefikhoshbakht, M. et al. (2024) [9]; Ah-med, Z. and Yousefikhoshbakht, M. (2023a) [10]; Ozcetin, E. and Ozturk, G. (2023) [11]; Ahmed, Z. and Yousefikhoshbakht, M. (2023b) [12]; Zheng, F. et al. (2023) [13]; Dutta, J. et al. (2022) [14]; Dasdemir, E. et al. (2022) [15]; Ruiz E. et al. (2022) [16]; Wu, X. et al. (2022) [17]; and Öztop, H. (2022) [18]. From another approach, with multiple warehouses or distribution centers, planning becomes more complex but also more flexible. In this scenario, the works of Peng, Z. et al. (2024) [19]; Xiao, S. et al. (2024) [20]; Bezerra, S. et al. (2023) [21]; Shao, W. et al. (2023) [22]; Soares, V. and Roboredo, M. (2023) [23]; and Du, M. (2023) [24] stand out.

The optimization challenges is to find the best routes for a set of vehicles to satisfy the demands of a set of customers or locations. Some common problems appear in works developed by Zhang, Y. et al. (2024) [8]; Bezerra, S. et al. (2023) [21]; Ahmed, Z. and Yousefikhoshbakht, M. (2023b) [12]; Soares, V. and Roboredo, M. (2023) [23]; and Du, M. (2023) [24] with the Time Windowed Freight Vehicle Problem. Likewise, problems appear in the studies of Yousefikhoshbakht, M. et al. (2024) [9]; Ahmed, Z. and Yousefikhoshbakht, M. (2023a) [10]; Ahmed, Z. and Yousefikhoshbakht, M. (2023b) [12]; and Öztop, H. (2022) [18] with the heterogenetic fixed fleet of vehicles problem. The works of Ozcetin, E. and Ozturk, G. (2023) [11] and Dutta, J. et al. (2022) [14] exhibit common problems with the third-party logistics services problem; the work of Xiao, S. et al. (2024) [20] with the resource sharing problem; the work of Zheng, F. et al. (2023) [13] with the supply sharing problem, considering demand urgency; the work of Dasdemir, E. et al. (2022) [15] with the problem of excess reserves with limited vehicle capacity; and the works of Ruiz E. et al. (2022) [16] and Wu, X. et al. (2022) [17] with the crowd-shipping problem and split deliveries, respectively. In synthesis, these studies have improved computational efficiency and flexibility in route planning. Implementing these approaches in open vehicle routing optimization (OVRP) provides efficient and adaptable solutions to complex logistics challenges.

Considering the type of techniques or tools to address the solution of optimization problems in VRP and OVRP environments, which allow for finding high-quality solutions in a reasonable time, heuristic approaches are among them and have been applied in the works of Peng, Z. et al. (2024) [19]; Ruiz E. et al. (2022) [16]; and Öztop, H. (2022) [16]; and those of a metaheuristic nature, have been addressed by the following researchers: Zhang, Y. et al. (2024) [8]; Yousefikhoshbakht, M. et al. (2024) [9]; Xiao, S. et al. (2024) [20]; Bezerra, S. et al. (2023) [21]; Ahmed, Z. and Yousefikhoshbakht, M. (2023a) [10]; Ozcetin, E. and Ozturk, G. (2023) [11]; Ahmed, Z. and Yousefikhoshbakht, M. (2023b) [12]; Zheng, F. et al. (2023) [13]; Shao, W. et al. (2023) [22]; Soares, V. and Roboredo, M. (2023) [23]; Du, M. (2023) [24]; Dutta, J. et al. (2022) [14]; Dasdemir, E. et al. (2022) [15]; and Wu, X. et al. (2022) [17].

In search of developing tasks quickly and efficiently and given the complexity of the problems addressed, in recent years, a series of fundamental algorithms have been proposed for decision making: Authors such as Peng, Z. et al. (2024) [19] with the Harris Hawks Optimization and Particle Swarm Optimization algorithm. Zhang, Y. et al. (2024) [8] with the multi-objective whale learning optimization algorithm. Yousefikhoshbakht, M. et al. (2024) [9]; Ahmed, Z. and Yousefikhoshbakht, M. (2023b) [12]; and Du, M. (2023) [24] with the modified ant colony algorithm. Xiao, S. et al. (2024) [20] with the adaptive hybrid simulated tempering and tempering algorithm. Bezerra, S. et al. (2023) [21] and Ozcetin, E. and Ozturk, G. (2023) [11] with the variable neighborhood search algorithm. Ahmed, Z. and Yousefikhoshbakht, M. (2023a) [10] and Shao, W. et al. (2023) [22] with the improved tabu search algorithm. Zheng, F. et al. (2023) [13]; Dutta, J. et al. (2022) [14]; and Dasdemir, E. et al. (2022) [15] with the evolutionary algorithm. Soares, V. and Roboredo, M. (2023) [23] and Ruiz E. et al. (2022) [16] with the flat cutting algorithm. Wu, X. et al. (2022) [17] with the tangible nested genetic algorithm. And Öztop, H. (2022) [18] with the constraint programming model. In synthesis, the implementation of these approaches or techniques to problem solving provides a spectrum towards optimization by means of heuristic combinations, which becomes an enabling scenario for open vehicle routing problems (OVRPs) using heuristics such as Greedy, Nearest Neighbor and 2-opt, helping to satisfy geographically dispersed customers, balancing costs and delivery times.

3. Materials and Methods

The method to carry out the research is developed in four stages: (I) design of experiment, (II) definition of the problem, (III) formulation of the mathematical model, (IV) solution and analysis of the results (see Figure 2).

3.1. Experiment Design

The study adopts a multidimensional approach to model and solve the OVRP. Initially, AMPL (A Mathematical Programming Language) is used. This tool is ideal for tackling a range of optimization problems, based on linear and integer programming [25]. To ensure consistent and comparable results, all tests were performed on a 2.9 GHz Intel Core i5 10400F processor with 32 GB of DDR4 RAM at 3200 MHz. The use of AMPL and hardware specificity are fundamental to the quality, consistency and efficiency of the research. They ensure that the results are accurate, reproducible and comparable, providing a solid basis for evaluating and improving optimization techniques applied to OVRP.

3.1.1. Experimentation

The purpose of the proposed computational experimentation is to compare the AMPL, LKH-3 and heuristic tools implemented in Python. Their performance is evaluated in terms of solution quality and execution time. The mathematical formulation with AMPL, allows for the solving of variants of the OVRPs [26]. Consequently, a comparison with LKH-3 allows us to relate the performance of the generated instances; this algorithm stands out for its efficiency in solving the Traveler of Trade and VRP [27]. The development of heuristic algorithms in Python 3.12 allow us to implement and evaluate heuristic algorithms, such as Greedy, Nearest Neighbor and 2-opt. These algorithms are designed to provide solutions in a reasonable computational time.

3.1.2. Data Analysis

For data analysis, symbols and descriptions of the required elements are specified (see Table 1). Allowing the identification and comparison of the results, as well as the evaluation of the time efficiency of each method in the context of the OVRP.

3.2. Problem Definition

The open vehicle routing problem (OVRP) is classified as NP-Hard due to the exponential increase in computational time and cost as the number of clients or nodes increases. To handle this complexity, heuristic algorithms such as Lin–Kernighan (LKH), known for their effectiveness in generating feasible and good quality solutions in reasonable computational times, are employed [28]. These algorithms not only reduce logistics costs, benefiting transportation companies [29], but also address problem-specific constraints, such as sub-path elimination constraints (MTZ), necessary to identify a Hamiltonian cycle, which involves visiting all nodes in a closed loop. In addition, the continuity of routes is ensured: if a vehicle enters a node, it must leave it. However, it is crucial to introduce constraints that interrupt this continuity to avoid erroneous solutions or excessively long processing times without finding a feasible solution. In summary, the goal is to use efficient heuristic algorithms to solve the OVRP, managing the complexities and constraints of the problem to optimize routes and reduce logistics costs.

3.3. 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:

(1)$MinZ=\sum _{i,jϵARCS}{C}_{ij}{X}_{ij}$

(2)$\sum _{iϵN\backslash \left\{j\right\}}{X}_{ij}+\sum _{jϵN\backslash \left\{i\right\}}{X}_{ij}=1{\forall }_iϵN\backslash \{1\}$

(3)$u_i-u_j+qq*X_{ij}\le qq-d_j{\forall }_{ij}:i\ne 1,j\ne 1$

(4)$\sum _{i,jϵARCS}{d}_j{X}_{ij}\le qq{\forall }_{ij}:i\ne 1$

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 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.

3.4. Solution and Analysis of Results

To validate the significant differences observed between the methods compared, a comprehensive statistical analysis will be performed, including hypothesis testing and other appropriate statistical methods. Specific details of the experimentation will be presented, along with graphical representations and tables that will facilitate the understanding and visualization of the results obtained. We will adopt an iterative approach of continuous review and improvement to evaluate possible adjustments in the implementations and experimental methodology, with the goal of refining the comparison between the tools used. The resources needed for the experiments include suitable hardware and specialized software such as AMPL (3.6.10.), LKH-3 (3.0.9.) and Python (3.11.). The mathematical model is based on the adaptation of the vehicle routing problem (VRP) proposed by Toth and Vigo, modified to address the unique characteristics of the open vehicle routing problem (OVRP) [2]. For the evaluation and comparison of the results, instances of LKH-3 will be used due to its effectiveness in solving the OVRP. In AMPL, a time constraint of one hour will be imposed for obtaining solutions, using the Cplex solver (22.1.1.0).

The results will be presented in a table that will include the solutions provided by LKH-3, the Best Known Solution (BKS), as the main reference, the results of the proposed model in AMPL and those obtained with the heuristic developed in Python. Since the problem is NP-Hard in nature, several heuristic algorithms will be employed, including Greedy, Nearest Neighbor, Local Search, and a combination of Nearest Neighbor and Local Search, as well as the Lin–Kernighan approximation algorithm (LKH-3). These algorithms will be evaluated in terms of solution quality and computational efficiency, providing a solid basis for comparison and analysis of the different methodologies implemented.

3.4.1. Heuristic Algorithms—Greedy (H.1)

Greedy heuristics have a short-term selection approach that does not take into account long-term consequences. It is based on the premise that locally optimal decisions will lead to a globally optimal solution. This approach is notable for its conceptual simplicity and computational efficiency, taking advantage of the optimal substructure present in various problems, where local solutions can be combined to generate a global solution. The general procedure of H.1 is shown in Algorithm 1.

Algorithm 1. The pseudo-code of Greedy (H.1) algorithm
1:	Input: List of vehicles (vehicles), List of customers (customers), Vehicle capacities (Q), Demand per customer (q), Distance matrix (distance)
2:	Output: Dictionary of routes (routes)
3:	Initialize an empty route dictionary.
4:	Initialize a list of available vehicles (available_vehicles) from vehicles.
5:	As long as customers are not empty and vehicles are available:
	a. Select the first available vehicle (vehicle_available)
	b. Initialize the current vehicle capacity (current_capacity) with Q[vehicle].
	c. Start a new route with the vehicle in the depot (current_route = [0]).
	d. Initialize the distance traveled (distance_traveled) to 0.
	e. As long as current_capacity > 0 and customers are not empty
	i. Find the nearest customer (nearest_closest_customer) to the last stop in current_route.
	ii. If the demand of the nearest_closest_customer (q[nearest_customer]) is less than or equal to the current_capacity: q[nearest_customer].
	equal to the current_capacity:
	1. Deduct demand from current_capacity 2.
	2. Add the distance to distance_traveled
	3. Add nearest_closest_customer to current_route
	4. Remove nearest_customer from customers
	iii. Otherwise, break loop
	f. Store completed route (routes[vehicle] = current_route)
	g. Delete vehicle from available_vehicles
6:	Return routes

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.

Algorithm 2. The pseudo-code of Nearest Neighbor (H.2) algorithm
1:	Inputs: 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.
	2. Add new[0,1] to visited_nodes 2. 2. Add new[0,1] to visited_nodes
	ii. 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.

Algorithm 3. The pseudo-code of Local Search (H.3) algorithm
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.
	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.

3.4.4. Heuristic Algorithms—Nearest Neighbor + Local Search

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.

Algorithm 4. The pseudo-code of Nearest Neighbor + Local Search algorithm
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.
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

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.

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. 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.

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), 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.

In the P-n55-k7 instance, complexity increases due to the larger number of nodes and vehicles, resulting in greater challenges for route optimization. In this scenario, H4 again stands out for its ability to approach the costs obtained by LKH-3 and AMPL, highlighting its robustness and adaptability to more complex instances. However, the differences in costs are more pronounced compared to E-n30-k3, highlighting the importance of using more advanced methods for larger scale scenarios.

In synthesis, it highlights the effectiveness of the H4 heuristic in providing competitive solutions, especially for instances of higher complexity, and emphasizes the need to balance between computational efficiency and solution quality when selecting the appropriate heuristic for different instance sizes in the OVRP.

5. Conclusions

This research takes a comprehensive dive into the open vehicle routing problem (OVRP), a fundamental logistics challenge in today’s mobility and trade landscape. By adopting a multidimensional approach, we have formulated and solved the OVRP using advanced tools such as AMPL and compared results with state of the art algorithms such as LKH-3. Detailed experimentation and comparison with the Best Known Solution (BKS) have revealed the complexity of the OVRP. Despite the implemented mathematical methods up to heuristics, such as Greedy and Nearest Neighbor, the OVRP has offered remarkable solutions. The synergy between Nearest Neighbor and 2-opt stands out especially for its efficiency.

Experimentation supported by the AMPL formulation and the LKH-3 algorithm provided solutions very close to the optimum, with a difference of less than 5% with respect to the Best Known Solution (BKS). The heuristics, especially H4 (Nearest Neighbor + Local Search), were shown to be highly competitive, reducing costs by approximately 10% compared to other heuristics such as H1 (Greedy) and H2 (Nearest Neighbor) in several instances.

Similarly, the diversity of instances and their impact on the efficiency of the algorithms is highlighted, where instance C1, with 51 nodes and 5 vehicles, and instance E-n23-k3, with 23 nodes and 3 vehicles, showed how complexity and geographical distribution affect the formulation of solutions. In these problems, AMPL and LKH-3 managed to approach BKS with less than 3% deviation, while the heuristics varied more significantly, with H4 again standing out for its performance.

Another more detailed analysis, taking as reference the most prominent instances E-n30-k3 and P-n55-k7, highlights the effectiveness of H4, which achieved with respect to costs just 7% higher than those obtained by AMPL and LKH-3, in contrast to H1 and H2, which presented differences of up to 15%. This quantitative analysis shows that the applied heuristics provide fast and acceptable solutions, where the combination of Nearest Neighbor and Local Search is especially powerful, reducing the gap with the most advanced methods.

The main innovation of this research lies in the implementation of a comprehensive and comparative approach to solving the open vehicle routing problem (OVRP) using both advanced mathematical and heuristic methods. Unlike previous studies that focus on specific routing and vehicle problems, this research covers 58 instances, including up to 200 nodes and 17 vehicles, addressing a diversity of problems from multiple depots to heterogeneous fleets and time constraints. The combination of the AMPL formulation and the LKH-3 algorithm, along with the synergy of heuristics such as Greedy and Nearest Neighbor with 2-opt, has demonstrated remarkable efficiency, whereby this integration of advanced methods outperforms previous solutions such as ant colony algorithms, tabu search methods, and constrained programming models, demonstrating superiority in both efficiency and versatility.

Finally, it is recommended to explore the integration of emerging technologies, such as machine learning or artificial intelligence-based optimization, to address OVRP. These technologies offer innovative and adaptive approaches that could provide more flexible and efficient solutions in dynamic logistics environments. Taken together, these recommendations seek to drive the continued evolution of the strategies used, ensuring increasingly efficient and adaptive solutions to highly complex logistics challenges.

Author Contributions

Conceptualization, D.G., F.P. and S.P.; methodology, G.G., G.H.-V. and J.R.C.-H.; validation, D.G., F.P. and S.P.; formal analysis, D.G., F.P. and S.P.; investigation, G.G., G.H.-V. and J.R.C.-H.; resources, J.R.C.-H.; writing—original draft preparation, G.H.-V.; writing—review and editing, G.H.-V.; visualization, G.H.-V.; supervision, G.H.-V. and J.R.C.-H.; project administration, G.H.-V. and J.R.C.-H.; funding acquisition, R.L. and J.R.C.-H. All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding authors.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. A sample of vehicle routing networks.

Figure 2. Methodological proposal.

Figure 3. A comparison of H.2 and H.3 algorithms for the A-n45-k7 instance.

Figure 4. A comparison of H.2 and H.3 algorithms for the A-n46-k7 instance.

Figure 5. A general comparison of results.

Figure 6. Best Known Solution (BKS) results.

Figure 7. Comparative results between heuristics.

Table 1

The definition of symbols.

Symbol	Description
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

Table 2

The definition of symbols.

Type	Symbol	Definition
Sets	N	Set of nodes, includes clients and the repository.
	ARC	Set of arcs, represents the connection between node i and j.
Parameters	d n	Demand of each client.
	q q	Vehicle capacity.
	c ij	Cost of traveling from one node to another.
Variables	xij	Binary variable equal to 1 if the arc is used and 0 otherwise.
	un	Continuous variable for subtour elimination.

References

1. Dantzig, G.; Fulkerson, R.; Johnson, S. Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am.; 1954; 2, pp. 393-410. [DOI: https://dx.doi.org/10.1287/opre.2.4.393]

2. Toth, P.; Vigo, D. Vehicle Routing: Problems, Methods, and Applications; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 2014.

3. Morillo, D.; Gatica, G. Learn by Modeling: Integer-Mixed Linear Programming: Learning Guide, from Problem to Solution with AMPL; Sello Editorial Javeriano-Pontificia Universidad Javeriana: Cali, Colombia, 2022.

4. Ge, H.; Zhen, T.; Jiang, Y.; Che, Y. An intelligent solution for open vehicle routing problem in grain logistics. Advances in Wireless Networks and Information Systems; Springer: Berlin/Heidelberg, Germany, 2010; pp. 389-396.

5. Brandão, J. A deterministic iterated local search algorithm for the vehicle routing problem with backhauls. Top; 2016; 24, pp. 445-465. [DOI: https://dx.doi.org/10.1007/s11750-015-0404-x]

6. Applegate, D.L.; Bixby, R.E.; Chvátal, V.; Cook, W.J. The Traveling Salesman Problem: A Computational Study; Princeton University Press: Princeton, NJ, USA, 2007.

7. Kallrath, J. Modeling Languages in Mathematical Optimization; Springer Science & Business Media: Luxembourg, 2004.

8. Zhang, Y.; Li, H.; Wang, Z.; Wang, H. A Multi-Objective Learning Whale Optimization Algorithm for Open Vehicle Routing Problem with Two-Dimensional Loading Constraints. Mathematics; 2024; 12, 731. [DOI: https://dx.doi.org/10.3390/math12050731]

9. Yousefikhoshbakht, M.; Didehvar, F.; Rahmati, F.; Ahmed, Z.H. Fixed fleet open vehicle routing problem: Mathematical model and a modified ant colony optimization. Bulletin of the Polish Academy of Sciences. Tech. Sci.; 2024; 72, e148253.

10. Ahmed, Z.H.; Yousefikhoshbakht, M. An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows. Alex. Eng. J.; 2023; 64, pp. 349-363. [DOI: https://dx.doi.org/10.1016/j.aej.2022.09.008]

11. Ozcetin, E.; Ozturk, G. A variable neighborhood search for Open Vehicle Routing Problem. Concurr. Comput. Pract. Exp.; 2023; 35, e7598. [DOI: https://dx.doi.org/10.1002/cpe.7598]

12. Ahmed, Z.H.; Yousefikhoshbakht, M. A Hybrid Algorithm for the Heterogeneous Fixed Fleet Open Vehicle Routing Problem with Time Windows. Symmetry; 2023; 15, 486. [DOI: https://dx.doi.org/10.3390/sym15020486]

13. Zheng, F.; Du, L.; Li, X.; Zhang, J.; Tian, B.; Jallad, R.F. Multi-objective medical supplies distribution open vehicle routing problem with fairness and timeliness under major public health emergencies. Manag. Syst. Eng.; 2023; 2, 5. [DOI: https://dx.doi.org/10.1007/s44176-023-00015-6]

14. Dutta, J.; Barma, P.S.; Mukherjee, A.; Kar, S.; De, T. A hybrid multi-objective evolutionary algorithm for open vehicle routing problem through cluster primary-route secondary approach. Int. J. Manag. Sci. Eng. Manag.; 2022; 17, pp. 132-146. [DOI: https://dx.doi.org/10.1080/17509653.2021.2000901]

15. Dasdemir, E.; Testik, M.C.; Öztürk, D.T.; Şakar, C.T.; Güleryüz, G.; Testik, Ö.M. A multi-objective open vehicle routing problem with overbooking: Exact and heuristic solution approaches for an employee transportation problem. Omega; 2022; 108, 102587. [DOI: https://dx.doi.org/10.1016/j.omega.2021.102587]

16. Ruiz y Ruiz, E.; García-Calvillo, I.; Nucamendi-Guillén, S. Open vehicle routing problem with split deliveries: Mathematical formulations and a cutting-plane method. Oper. Res.; 2022; 22, pp. 1017-1037. [DOI: https://dx.doi.org/10.1007/s12351-020-00580-8]

17. Wu, X.; Hu, D.; Ma, B.; Jiang, R. The Two Echelon Open Vehicle Routing Problem: Optimization of Crowdshipping Based Parcel Delivery. KSCE J. Civ. Eng.; 2022; 26, pp. 4073-4085. [DOI: https://dx.doi.org/10.1007/s12205-022-1948-6]

18. Öztop, H. A constraint programming model for the open vehicle routing problem with heterogeneous vehicle fleet. The International Symposium for Production Research; Springer International Publishing: Cham, Switzerland, 2022; pp. 345-356.

19. Peng, Z.; Pirozmand, P.; Xiong, Y. Improved Harris Hawks Optimizer algorithm to solve the multi-depot open vehicle routing problem. Evol. Intell.; 2024; 17, pp. 2495-2513. [DOI: https://dx.doi.org/10.1007/s12065-023-00898-0]

20. Xiao, S.; Peng, P.; Zheng, P.; Wu, Z. A Hybrid Adaptive Simulated Annealing and Tempering Algorithm for Solving the Half-Open Multi-Depot Vehicle Routing Problem. Mathematics; 2024; 12, 947. [DOI: https://dx.doi.org/10.3390/math12070947]

21. Bezerra, S.N.; de Souza, S.R.; Souza, M.J.F. A general VNS for the multi-depot open vehicle routing problem with time windows. Optim. Lett.; 2023; 17, pp. 2033-2063. [DOI: https://dx.doi.org/10.1007/s11590-023-01990-1]

22. Shao, W.; Xiao, T.; Su, Z.; Ding, J.; Lü, Z. A hybridization of granular adaptive tabu search with path relinking for the multi-depot open vehicle routing problem. Egypt. Inform. J.; 2023; 24, 100420. [DOI: https://dx.doi.org/10.1016/j.eij.2023.100420]

23. Soares, V.C.; Roboredo, M. On the exact solution of the multi-depot open vehicle routing problem. Optim. Lett.; 2023; 18, pp. 1053-1069. [DOI: https://dx.doi.org/10.1007/s11590-023-02072-y]

24. Du, M. Improved Ant Colony Algorithm for Solving multi-deport Open Vehicle Routing Problem with Fuzzy Time Window. Proceedings of the 2023 3rd International Conference on Digital Society and Intelligent Systems (DSInS); Chengdu, China, 10–12 November 2023; pp. 410-414.

25. Boyd, S.P.; Vandenberghe, L. Convex Optimization; Cambridge University Press: Cambridge, UK, 2004.

26. Fourer, R.; Gay, D.M.; Kernighan, B.W. AMPL: A Modeling Language for Mathematical Programming; Thomson/Brooks Cole: Pacific Grove, CA, USA, 2003.

27. Sumbal, M.S.; Ahmed, W.; Shahzeb, H.; Chan, F. Sustainable Technology Strategies for Transportation and Logistics Challenges: An Implementation Feasibility Study. Sustainability; 2023; 15, 5224. [DOI: https://dx.doi.org/10.3390/su152115224]

28. Lin, S. Computer Solutions of the Traveling Salesman Problem. Bell Syst. Tech. J.; 1965; 44, pp. 2245-2269. [DOI: https://dx.doi.org/10.1002/j.1538-7305.1965.tb04146.x]

29. Mardones, B.; Gatica, G.; Contreras-Bolton, C. A metaheuristic for the double traveling salesman problem with partial last-in-first-out loading constraints. Int. Trans. Oper. Res.; 2023; 30, pp. 3904-3929. [DOI: https://dx.doi.org/10.1111/itor.13189]

30. Ren, C. Research on Single and Mixed Fleet Strategy for Open Vehicle Routing Problem. J. Softw.; 2011; 6, pp. 2076-2081. [DOI: https://dx.doi.org/10.4304/jsw.6.10.2076-2081]

31. Uddin, F.; Riaz, N.; Manan, A.; Mahmood, I.; Song, O.Y.; Malik, A.J.; Abbasi, A.A. An improvement to the 2-opt heuristic algorithm for approximation of optimal TSP tour. Appl. Sci.; 2023; 13, 7339. [DOI: https://dx.doi.org/10.3390/app13127339]

32. Masson, A.; Paravie, D.I.; Rohvein, C.; Villalba, L. Review of vehicle routing problems solving software. Inge CuC; 2021; 17, pp. 315-328. [DOI: https://dx.doi.org/10.17981/ingecuc.17.1.2021.23]