1 Introduction

The vehicle routing problem (VRP) is an important problem in the fields of transportation, distribution and logistics, and the open vehicle routing problem (OVRP) is an especial case of this problem. The OVRP includes finding the best route for a set of vehicles that should deliver services to a set of customers. Every route in the OVRP includes a set of customers that start from the initial depot and end in one customer [1]. OVRP usually is limited by the following constraints: all vehicles have the same capacity, every customer should be met with only one vehicle and his/her demand should be delivered, the sum of demands of customers in a route should not exceed the capacity of all the vehicles, and in some problems some constraints are considered for traveling time and distance [2, 3]. The main purpose of solving this problem is to reduce the number of vehicles, travelled time and distance by the vehicle.

The most important difference between OVRP and VRP is the existence of Hamiltonian routes and Hamiltonian cycles in these problems, respectively; Hamiltonian routes start from a point and end in another point, while Hamiltonian cycles return to the starting point finally [3, 4]. Thus, one of the main features of OVRP is that transportation vehicles do not necessarily return to the starting depot after delivering service to the customer, and if they do so, they will meet the same customers in the delivering route [5]. OVRP is an NP-hard problem, and its solution is a scientific challenge. Conventional studies about OVRP have solved this kind of problems by assuming definite respond for the demands of all customers on the route.

Recently, several heuristic and meta-heuristic methods based on tabu Search, GA, PSO, ACO, ICA, memetic algorithm and so on have been proposed by researchers to solve the OVRP. We could cover some of them in the following paragraphs as the literature review.

In [6], a new tabu search algorithm was proposed to solve the vehicle routing problem in which vehicles do not return to the distribution depot after delivering goods to the customers or, if they do so, they must visit the same customers, for the collection of goods, in the reverse order. The authors compared the performance of their algorithm with other heuristic method designed for the same problem in terms of computation time. Erbao et al. [7] described the customer’s demand as specific bounded uncertainty sets with expected demand value and nominal value and investigated the transportation costs and unsatisfied demands in the specific bounded uncertainty sets and proposed four robust strategies to cope with the uncertain demand and proposed an improved differential evolution algorithm (IDE) to solve the optimization problem. Computational experiments indicate that the robust optimization can avoid unmet demand while incurring a small extra cost. The proposed strategy balances the cost with unmet demand among different robust strategies.

In [8], a combination of GA and TS is used to solve the OVRP, in which global optimization and parallel processing features of GA and rapid local search of TS are integrated to solve the problem. A tabu search algorithm based on memory is proposed in [9] for solving OVRP in which customers’ demand is provided with a fixed number of vehicles with different capacities. But this method could only solve the problems with fixed number of customers (includes 50, 75, 100, 150, 200), while our method is able to solve the problems with variable numbers of costumers (for example, 50, 71, 100, 120, 134, 150, 199,…). And also it could solve large-scale problems that contain numerous costumers (like 200, 240, 280, 320, 360, 400, 440, 480), which is one of the superiority of the proposed method. Combinatory tabu search algorithm [10] and improved tabu search [11] were implemented by Huang and Liu in order to reduce the number of transportation vehicles and traveling cost of OVRP. Based on simulation results, the algorithm is able to reduce the number of vehicles and traveling cost.

Shamshirband et al. [12] proposed a solution to solve the multi-objective commodity vehicle routing problem, in which costumers have different demands. So a new model based on integer linear programming hybrid with time windows and various demands was introduced to optimize the traveling cost and also maximize the number of demands. And also two approaches based on the NSGA-II algorithm with different mutation designs were proposed.

Hadji et al. presented a method for solving vehicle routing combinatorial optimization problem. Their method included six heuristic methods and memetic algorithm. Six heuristic algorithms were used to generate the solutions, and memetic algorithm was used to improve the obtained solutions. To increase the quality and efficiency of the method, time windows were added to 144 samples, including 15–255 customers and 15–786 data (presented by Iori et al. [13]).

Norouzi et al. [14] used multi-objective PSO for solving OVRPC (the same OVRP but in competitive locations) with two objectives: to reduce the traveling cost and increase the sales in competitive locations. The proposed method was compared with similar methods to solve the problem. In [15], PSO algorithm with other algorithms like “nearest insertion algorithm” and “GENA” has been used to solve the OVRP and improve the obtained solution; these algorithms are able to optimize the inside and outside routes. Hu and Wu [16] presented an algorithm for solving the OVRP that is based on Genetic algorithm laws and was applied to improve the performance of PSO and differential evolution algorithms. In this algorithm, the dominant and non-dominant character includes every person. In [17], a specific decoding method for implementing PSO algorithm was proposed to solve OVRP, in which a vector based on customer locations was generated in descending order and then every customer was assigned to one path based on its location. Finally, a one-step jump was applied to the generated routes and the feasibility of routes and the solution quality were checked; it is a more effective method to solve the problem. But, the feasibility of this method was not investigated for large-scale problems and it was applied only to small problems. Both of the methods [16, 17] are used for solving the vehicle routing problem with time window and multiple service workers. They were implemented based on local deterministic search.

In [18], various meta-heuristic techniques such as evolutionary approaches, ant colony optimization, simulated annealing, tabu search and other recent approaches and their applications to solve the group technology/cell formation problems have been investigated. In the studied experiments, it was shown that ACO has better performance in producing the best solutions in comparison with GRASP.

In [19], a new meta-heuristic algorithm named OVRP_ICA based on the imperialist competition algorithm was proposed to solve the OVRP. It was a hybrid optimization method and can service the costumers by a homogeneous fleet of vehicles that do not return to the original depot necessarily. The algorithm was compared with other algorithms, and results indicated the high performance of the proposed algorithm to solve the open vehicle routing problem.

In [20], a clonal selection algorithm is proposed by Pan and Fu to solve open vehicle routing problem (OVRP) in which a new definition for continuity of antibodies and antibody variety conservation algorithm is presented.

In summary, the some of the reviewed methods could solve the OVRP for small problems [16, 17]. Some other solved OVRP with extra vehicles [18, 20] and left the OVRP as open issue. Based on our knowledge, none of the reviewed methods could solve the OVRP in optimum time with minimum number of vehicle and travel distance. In this paper, a new optimization algorithm called “OVRP_GELS” is proposed to solve OVRP with optimum number of vehicles travelled distance and travel run time for large problems.

The paper is organized as follows: in Sect. 2, gravitational emulation local search algorithm and record-to-record algorithm are explained. In Sect. 3, the proposed algorithm is explained, Sect. 4 describes the simulation results of the proposed algorithm in detail, and the conclusion is presented in Sect. 5.

2 Review of combined algorithms

Because we combined two different optimization algorithms, namely GELS and Record-to-Record, in the following subsections we try to introduce them in brief.

2.1 Gravitational emulation local search algorithm

In 1997, guided local search (GLS) algorithm was proposed by Voudouris and Tesang [21] to search and solve complex problems for the first time. In 2004, Webster [22] called this method gravitational emulation local search (GELS) and was used as a powerful local search algorithm for solving complex problems. The main idea of GELS is based on gravitational force, which causes to attract objects with each other, such a way that heavy object has the higher gravitational force and attract low weigh objects. The attraction force between two objects depends on the distance between them.

In GELS algorithm, possible solutions in the search space are divided into several categories according to their fitness’s. Each of these categories named a dimension of the solution, and there is initial velocity for them. Equation (2.1) computes the gravitational force between current solution (CU) and candidate solution (CA). This force (F) is added to the velocity vector in the path of current motion.

If velocity exceeds the maximum value (threshold), maximum velocity becomes the current velocity, and if the velocity becomes negative due to this force, the velocity is considered zero [23–29].

$$\begin{aligned} F=\frac{G(\hbox {CU}-\hbox {CA})}{R^{2}} \end{aligned}$$
(2.1)

The available parameters in GELS are as follows:

Maximum velocity The maximum value that can be assigned to each entry of the initial velocity vector, which prevents the further expansion of these entries.

Radius The radius (R) employed in the gravity calculation formula.

Iteration The maximum number of algorithm iterations, which ensures that the algorithm will terminate [23–29].

The pseudo-code of the GELS algorithm is described in Algorithm 1. This algorithm shows that an initial response to a problem is created, and each mass is evaluated. Next, the problem is updated as G, or Best, and/or Worst, and parameters m and a are calculated for each mass. Then velocity and the location of each mass are also updated. Finally, the algorithm ends, if the maximum number of iterations meets or all the initial velocity vector elements become zero. Otherwise, the algorithm goes back to step 2 and continues until an optimal answer is reached.

figure a

2.2 Record-to-record algorithm

Record-to-record algorithm (RTR) was developed by Duke in 1993 as a deterministic simulated annealing algorithm [30]. Assume that S is a current solution and N (S) is a neighborhood of S including the proposed solutions that are in the neighborhood of S and a proposed solution \(S \wedge '\mathrm {\in } \,N (S)\) is selected and the corresponding objective function \(f (S\wedge ')\) is also calculated.

In record-to-record algorithm, record is the total distance which is observed so far as the best solution. Deviation is defined by \(K\,\% \times \hbox {Record}\) and if \(f\left( S\wedge '\right) < \hbox {Record}+\hbox {Deviation}\) then \(S\wedge '\) is selected as a new solution and upward movements that are related to the total distance of the route, which are admissible in order to avoid trapping in a local minimum [31]. In open record-to-record (ORTR), a fixed neighborhood list with 20 customers is used, because the idea of the algorithm is that when improvement movements are carried out, a fixed number of neighborhoods is considered for every customer. In this algorithm, an initial feasible solution and also the least number of required vehicles for delivering service to the customers \(K_{\min }\) are obtained by sweeping algorithm. If none of the answers used \(K_{\min }\) number of vehicles, then a solution is selected that uses the least number of vehicles for delivering service to the customers. If the coordinates of the customers are not determined, the sweep algorithm cannot be used to generate an initial solution, because we cannot calculate the radius and angle and in this case we can employ another heuristic algorithm to generate the initial solution.

Finally, in open record-to-record (ORTR), we try to combine the paths by joining two paths together. For example, paths A and B can be combined if the demand of the combined path does not exceed the vehicle capacity and the sum of traveling distance does not exceed maximum path length. Usually finding the best path for combining two paths quickly and effectively is not possible, and in this algorithm we try to combine path A between two alternate ties with path B.

3 The proposed algorithm

We use the gravitational emulation local search algorithm (GELS) as a strategy to solve the OVRP. The objective is to find the shortest path between customers, reducing the number of vehicles and traveling time of all vehicles.

3.1 Defining the solution dimensions

In the proposed method, every dimension of solution can be considered as a customer; in fact, number of solution dimensions is equal to the number of customers. The neighbor of the current solution (CU) in the considered dimension is the customer who has the least distance, time and most velocity with the customer of the current solution (CU) for every vehicle, and the vehicle has not met the customer so far [28].

3.2 Definition of neighborhood

In GELS algorithm unlike other algorithms, searching the neighborhood solution is not carried out randomly but every current solution (CU) has different neighbors and each of them is based on a particular change which is named moving direction toward the neighboring solution [28]. All the neighbors that are obtained based on this method are only based on this neighbor. The following procedure is used to find the neighboring solution, the customer with the least distance, time and most velocity with respect to the current solution (CU) is selected as a neighbor and candidate solution (CA) for every vehicle.

3.3 Solution method

In the proposed method, gravitational emulation local search algorithm (GELS) is applied to solve the open vehicle routing problem (OVRP). As mentioned earlier, the objective is to reduce the traveling time and distance and also reduce the number of employed vehicles. Because of the complexity of the problem, achieving to the solution is difficult even if there are a few vehicles and customers. Therefore, by considering the characteristics of GELS algorithm and its global feature, we used this algorithm to solve the OVRP.

A one-dimensional array is used to present the solution; its length is equal to the number of costumers plus the number of vehicles minus 1. To initialize each solution, we put zero in the randomly selected cells of array (for the number of vehicles minus 1), and then we put the consumers randomly in remind cells.

Example 1

It is considered a particular example with three vehicles and ten customers, (3, 10). In Fig. 1, it is a solution, an array with the length 12, including the 10 customers in the order of vehicles separated by zeros. So, the vehicle 1 meets the costumers with the numbers 4, 7 and 3, the second vehicle meets the next forth costumers 5, 1, 2 and 6, and the third vehicle meets the last three costumers 9, 8 and 10. So, for short (vehicle, [list of customers]): (1, [4, 7, 3]), (2, [5, 1, 2, 6]) and (3, [9, 8, 10]).

Fig. 1
figure 1

The solution structure of a particular case of the open vehicle routing problem (OVRP) solved with the gravitational emulation local search algorithm (GELS). There are considered three vehicles, separated by number 0, each cell of the solution array includes the customer’s number for each of the three considered vehicles, (vehicle, [list of customers]): (1, [4, 7, 3]), (2, [5, 1, 2, 6]) and (3, [9, 8, 10])

Full size image

Considering the objective of the problem which is reducing the traveling distance and number of vehicles, this paper introduces the gravitational emulation local search algorithm (GELS) as a suitable strategy for solving the OVRP. Contrary to other algorithms, the GELS algorithm does not proceed with random solutions, but it proceeds by examining the current solutions (CU) and provides distinct final conditions that can complete the previous direction for a specific iteration to continue counting. Thus, although the GELS algorithm has a number of random operators-based elements, it does not proceed purely based on random operators. Although it employs the local neighborhood search method for solving the problem, it does not move in the same way between them at all. And although it includes a particular behavior of greedy algorithms, it does not find the best path for searching. The GELS algorithm uses the same law that guides the motion of objects in physical space in order to control their motion in a complex search space.

Unlike other algorithms that start from an initial population and then generate the next populations, the GELS algorithm starts from an initial or current solution (CU) and, in the next step, the secondary or candidate solution (CA) is generated based on the neighbors, customers and vehicles that can satisfy the problem constraints. In this step, the gravitational force between these two masses is calculated and it is considered as a solution and then velocity and gravitational mass are updated.

One of the advantages of this algorithm against other algorithms is the presence of velocity factor which makes this algorithm to search only for the best and optimum solutions and attract them. This process leads to growth of object’s mass, and as we know, in the gravitational law, as the object mass increases, the gravitational force increases as well and thus the object attracts more optimum solutions toward itself. This procedure is repeated in each iteration until the object’s weight gets rise by attracting the optimum solutions, so the algorithm returns the best solution.

The initial solutions of OVRP can be obtained using algorithms such as sweep algorithm or in a random way. The proposed method integrates the GELS algorithm and initial solution obtained from the sweep algorithm in order to solve the OVRP. The solution procedure works as follows:

The GELS algorithm generates the conditions for OVRP by defining three parameters.

At first, sweep algorithm produces an initial solution. And then system environment and initialization to customers which are considered as masses are determined. Solutions obtained by customers are sorted based on their weight, and the first solution is considered as the best solution. In the next step, the weight of customers is evaluated. And in the next step G(t), gravitational force on each costumer, acceleration, time and velocity are calculated and parameters V, T would be updated. It means that if the candidate solution (CA) obtained in each step is better than current solutions (CU), previous solution is replaced by candidate solution (CA) and then gravitational force between them is calculated using Eq. (2.1), and then parameter V is updated by Eq. (3.1).

$$\begin{aligned} V=V+F \end{aligned}$$
(3.1)

In this updating formula, parameter V is increased, after that parameter T would be updated in Eq. (3.1), and it is decreased, which means that the problem is being optimized. After these steps, solutions are moved in different dimensions based on their forces and then GELS algorithm will end. Then, the algorithm performs record-to-record algorithm on produced solutions and finally the best solution obtained by the proposed algorithm would be displayed

The GELS algorithm improves distance and reduces the number of vehicles by applying the following procedure.

First, we consider three matrices: distance, initial velocity and time. The distance matrix is taken from standard problems in [32] and is calculated for every sample separately. Based on GELS algorithm, the initial velocity has an initial constant velocity at first. In this problem, the initial velocity of all masses is considered equal to 100. The initial velocity is updated in every step. As it was explained, in the initial velocity matrix, an initial velocity of 100 is assigned to each customer, which is considered as a mass, and then in the next step, velocity will change and also the time (mass) matrix based on distance. Velocity matrix is obtained from Eq. (3.2):

$$\begin{aligned} T=\ \frac{\sqrt{{(Y_B-Y_A)}^2+\ {(X_B-X_A)}^2\ }}{V_{{\mathrm{in}}_{A,B}}}\ \end{aligned}$$
(3.2)

In Equation, T indicates mass of the customer, \({(Y_B-Y_A)}^2+\ {(X_B-X_A)}^2\) is the distance between two customers and \(V_{{\mathrm{in}}_{A,B}}\) shows the velocity between two customers.

Using GELS algorithm in these conditions, an appropriate reserve factor should be defined. The reserve factor is equal to the number of reserved customers for cars in the future. The set of assigned customers to the cars is a solution. This method can be used to represent a solution in the form of two (n*n) matrices which are equal to the number of cars and customers. Every row and column indicates one of the customers in the group, and the number in each row and column indicates the number of cars that belong to customers. When algorithm is completed, the reserved cars for the customers with the reservation factors are presented.

In order to improve the results of GELS, we run record-to-record algorithm in the form of one-point and two-point and then obtained solutions are saved. In the next step, the GELS algorithm would run on the obtained solution and therefore the obtained results are as an initial solution of the GELS algorithm. By applying GELS algorithm, one-point and two-point operations are carried out on the obtained solution again, which is different from the ordinary displacements. Every time after running the algorithm, the velocity and time matrices are updated if they are improved. In each step, for every row and column of velocity matrix, the maximum value of matrix is selected and then if the assigned machine to that customer is changed, we exchange those machines. Then by considering the changes, the cost of the current solution (CU) must be calculated again. If the cost of current solution (CU) is better than the cost of candidate solution (CA), it would be replaced; otherwise, it would not be updated in the table and a new GELS algorithm run again on the candidate solution (CA), and a new solution is tested on the other candidate masses, and then mass and velocity values are updated. The previous solution is called the current solution (CU) and the newly obtained solution which is compared to the current Solution (CU) named candidate solution (CA).

The algorithm ends when the assigned speed is zero or the number of iterations reaches the maximum value determined by the problem [28]. In the following tables, we simply explain the steps of our algorithm (Table 1) and the pseudo-code of OVRP_GELS in detail (Table 2).

Table 1 OVRP_GELS steps
Full size table
Table 2 OVRP_GELS algorithm
Full size table

3.4 An overview of the main contributions

We propose GELS algorithm to solve the OVRP with minimum number of vehicles, traveling distance and travel time of the vehicle that has the following contributions:

  1. 1.

    The main difference between the proposed algorithm and the previous works like GA and PSO algorithms that start from an initial population and then generate the next populations is that the GELS algorithm starts from an initial or current solution (CU) and, in the next step, the secondary or candidate solution (CA) is generated based on the neighbors, customers and vehicles that can satisfy the problem constraints.

  2. 2.

    The GELS algorithm has high rate to reach the final solution and is a strong local and also efficient algorithm for the problem and is comparable with other algorithms.

  3. 3.

    To improve results, we combine the GELS and record-to-record algorithms.

4 Computational experiments

4.1 Benchmark data sets

We test the proposed on a set of well-known benchmarks by Christofide et al. [33], Fisher [34], Li et al. [1]. In the Fisher model, there are 14 problems C1–C14 [33]. The customers of both sets are in the interval of 50–199, in the Cartesian coordination and Euclidean distance. Among them, for C6–C10, C13 and C14 the constraint on path length (L) and service time (e) is considered for all customers. Table 3 displays characteristics of 16 problems in the works of Christofide et al. [33] and Fisher [34]. Compared to VRP model, the maximum path length is a multiple of 0.9.

In addition, the set of large-scale data proposed by Li et al. [1] are also considered. The second case includes eight problems O1–O8 with 200–480 customers, and there is no constraint for path length. Every problem is geometrically symmetry, and the customers are placed in a circular manner around depot. Table 4 shows the characteristics of these eight problems.

Table 3 Benchmark data sets of Christofides et al. [33] and Fisher [34]
Full size table
Table 4 Benchmark data sets of Li et al. [1]
Full size table

4.2 Computational results

The results of simulation for solving the OVRP are presented in this section. C#.NET programming language is used to implement the programs, and also programs ran on a computer with 2.06 GHz Pentium-IV CPU and 6GB RAM. The proposed algorithm (OVRP_GELS) is compared to 11 different algorithms including: clonal selection algorithm [20], improved tabu search (ITS) [10], improved tabu search (ITS) [11], diploid hybrid PSO with DE (DHPD) [16], hybrid combination out of a stochastic combined variable neighborhood search and a simple (1 + 1)-evolutionary strategy ((hybrid (1 + 1) ES) [35], record-to-record travel solution (ORTR) [1], hybrid evolution strategy (HES) [36], broad local search algorithm (BLSA) [37], bumble bees mating optimization for the open vehicle routing problem (BBMOOVRP) [38], integrates a variable neighborhood descent (IVND) [39], particle swarm optimization (PSO) [17]).

Considering the mentioned steps in the previous section, results are shown in Tables 5, 6 and 7. It is worthy to mention that solving the vehicle routing problem using the gravitational emulation local search (GELS) algorithm is completely novel and has no similar case on internet. Also the preformed simulation using the GELS algorithm is the first simulations performed so far. The performed comparisons demonstrate the advantages of the proposed algorithm (OVRP_GELS) in terms of time, minimum number of vehicles and minimum travelled distance.

Tables 5, 6 and 7 demonstrate the results of the proposed algorithm (OVRP_GELS) compared to other well-known algorithms that solved the OVRP in different kinds from easy to difficult problems. As highlighted in Table 5, the proposed algorithm (OVRP_GELS) could obtain more optimum and more acceptable solutions. OVRP_GELS has also been able to reduce the number of vehicles in difficult problems in an efficiently manner. One of the great and exclusive advantages of the proposed algorithm (OVRP_GELS) is the time factor. As it is clear from the time column in Tables 6 and 7, proposed algorithm could be able to achieve the final solution in a shorter time compared to other algorithms.

Table 5 Comparison of the proposed method with ten other methods of solving OVRP based on the solutions that minimize the number of vehicles with least distance traveled in sixteen different problems
Full size table
Table 6 Comparison of the proposed method with PSO based on the number of vehicles used in the best found solution
Full size table

Run times by the OVRP_GELS and those of other algorithms are compared in Table 7. As it seen, the proposed algorithm could solve the problems in a reasonable time and also compete with other algorithms. OVRP_GELS has acceptable computational time for large-scale test problems which is 1.342 s for 200 customers and 6.119 seconds for 480 customers that approved the superiority of the proposed algorithm. No time value is calculated for two algorithms DHPD [16], hybrid (1 + 1) ES [35], so we did not compare them in Table 7.

Table 7 Comparison of proposed method with eight state-of-the-art methods in this domain based on time used to solve the problem
Full size table

Figure 2 shows the solving seven OVRPs from small to medium sizes. As you can see, the proposed algorithm (OVRP_GELS) is able to obtain desire outputs compared to other algorithms. It also can reach final answer in least time that is one of superiorities of the proposed algorithm (OVRP_GELS) than compared ones.

Fig. 2
figure 2

The routes generated for seven problems by OVRP_GELS. With the aim of reducing the number of vehicles, the algorithm generates the best response. a Problem C1 (\(n = 50\), solution value \(=\) 406.994), b problem C2 (n \(=\) 75, solution value \(=\) 543.676), c problem C3 (n \(=\) 100, solution value \(=\) 630.099), problem C4 (n \(=\) 150, solution value \(=\) 729.864), problem C14 (n \(=\) 100, solution value \(=\) 549.372), problem F11 (n \(=\) 71, solution value \(=\) 159.725), problem F12 (n \(=\) 134, solution value \(=\) 694.419)

Full size image

4.3 Large-scale test problems and computational results

In OVRP, there are eight large-scale problems that do not have any traveling distance constraint; therefore, their solution is difficult and time consuming. In this paper, we considered large-scale vehicle routing problem which is solved by Li et al. [1]. We selected eight problems with 200–480 customers and without traveling distance constraint. Every problem is geometrically symmetry, and customers are arranged in a circular way around depot. Every problem shows a geometrical symmetry that allows us to provide one solution. The obtained solutions by OVRP_GELS and solutions of other algorithms are provided in Table 8. In every problem, OVRP_GELS uses less number of vehicles (\({{K}}_{\mathrm {min}}\)). In Table 8, BLSA [37] has no value for \({{K}}_{\mathrm {min}}\).

Table 8 Comparison of proposed method with four state-of-the-art methods in this domain based on their \({{K}}_{\mathrm {min\ }}\) and fitness
Full size table

Figure 3 shows solving of eight large-scale OVRPs. As it is seen, the proposed algorithm (OVRP_GELS) is able to obtain desire outputs, reduce the number of vehicle in each problem and reach the final response in a shorter time.

Fig. 3
figure 3

The routes generated by OVRP_GELS for eight problems. With the aim of reducing the number of vehicles, the algorithm generates the best response. a Problem O1 (n \(=\) 200, solution value \(=\) 6038.585), b problem O2 (n \(=\) 240, solution value \(=\) 4421.855), c problem O3 (n \(=\) 280, solution value \(=\) 7206.972), d problem O4 (n \(=\) 320, solution value \(=\) 7244.135), e problem O5 (n \(=\) 360, solution value \(=\) 9267.282), f problem O6 (n \(=\) 400, solution value \(=\) 9796.370), g problem O7 (n \(=\) 440, solution value \(=\) 9929.649), h problem O8 (n \(=\) 480, solution value \(=\) 12004.09)

Full size image

4.4 Statistical analysis: advantages and disadvantages of GELS

As mentioned earlier, the proposed algorithm (OVRP_GELS) could obtain more optimum and more acceptable solutions compare to other methods. Moreover it has been able to reduce the number of vehicles with less time consumption efficiently. As shown in Sect. 4.3, the proposed method could perform better in large-scale problems (in six out of eight problems).

Because of the nature of GELS algorithm which is a local search algorithm, this method will stock in local minima in few cases that would be the limitation of this method. We try to reduce this side effect by using record-to-record algorithm combined with GELS.

5 Conclusion

In this paper, an optimization algorithm based on gravitational emulation local search algorithm named OVRP_GELS is proposed to solve the OVRP. The advantages of this algorithm are as follows: high speed and very low run time and objective values. The objective of the OVRP_GELS algorithm is to reduce the run time and number of vehicles and to find the shortest path between customers and vehicles. The results of GELS on several instances are compared with existing results of other eleven algorithms including the clonal selection algorithm and particle swarm optimization. The results show that OVRP_GELS algorithm is potentially more efficient when compared to other algorithms, at least on the tested benchmarks.

The running time of GELS is proposed algorithm is much lower, and it requires much less computational time to solve the problem. Since the required time for achieving the final solution, finding the shortest time and reducing the number of vehicles is an important factor in solving OVRP; therefore, less computational time is an obvious advantage of the proposed algorithm.

The main improvement of the GELS is for small and average results: the lowest value of 159.725 for problem F11, the maximum value of 873.691 for problem C10, for large-scale O2 instance the lowest value of 4421.855 and the maximum value of 12,004.09 for problem O8.