# A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem
###### Abstract  
This paper presents a hybrid grasshopper optimization algorithm using a novel decoder and local search to solve instances of the open vehicle routing problem with capacity and distance constraints. The algorithm's decoder first defines the number of vehicles to be used and then it partitions the clients, assigning them to the available routes. The algorithm performs a local search in three neighborhoods after decoding. When a new best solution is found, every route is locally optimized by solving a traveling salesman problem, considering the depot and clients in the route. Three sets containing a total of 30 benchmark problems from the literature were used to test the algorithm. The experiments considered two cases of the problem. In the first, the primary objective is to minimize the total number of vehicles and then the total distance to be traveled. In the second case, the total distance traveled by the vehicles is minimized. The obtained results showed the algorithm's proficient performance. For the first case, the algorithm was able to improve or match the best-known solutions for 21 of the 30 benchmark problems. For the second case, the best-known solutions for 18 of the 30 benchmark problems were found or improved by the algorithm. Finally, a case study from a real-life problem is included. optimization; combinatorial optimization; open vehicle routing problem; grasshopper optimization algorithm +
Footnote †: journal: _Algorithms_  
0000-0001-5000-5000-5000-5000-5000-5000-5000-5000-5000-5000-5000-5000-5000-5000-5000-50000-5000-50000-50000-50000-50000-50000-50000-50000-  
attraction and acceleration and (2) the behavior of certain groups of animals. There are many applications in which GOA has been used. Among such applications the most recent and relevant are [14; 15; 16; 17; 18]. The open vehicle routing problem (OVRP) is a variant of the classic vehicle routing problem (VRP) first introduced in [19]. Many variants of the VRP have been studied in the literature, and recent research focuses on modeling very specialized real-world variants of the VRP. Some of these recent specialized real-world variants can be found in [20; 21; 22; 23; 24; 25; 26; 27; 28; 29]. Although new routing problems arise everyday, classic problems such as the OVRP are still studied thanks to their potential applications. The research presented in this paper was motivated by the case study presented in Section 5, which required the solution of OVRP instances. The OVRP was formally introduced in [30], although the first work related to the problem was first presented in [31] for an air express courier problem. The OVRP is an NP-Hard combinatorial optimization problem (as mentioned in [32]), which makes it difficult to solve by exact methods. Therefore, many heuristic approaches have been developed to solve the problem. Among the most important heuristic algorithms used to solve the OVRP are those in [32; 33; 34; 35; 36; 37; 38; 39]. The applications of the OVRP are not limited to the context of vehicle route design. In [31], the OVRP is used to solve an air express courier problem, and in [40], the train services planning at the Channel tunnel is made by solving an OVRP. In this work, a novel hybrid grasshopper optimization algorithm with local search (HGOALS) method is used to solve instances of the open vehicle routing problem. To our knowledge, GOA has not been previously used for solving the OVRP. In fact, there is not much literature on GOA in the context of vehicle routing problems. The proposed solution method is based on the grasshopper optimization algorithm (GOA) and uses local search to improve solutions and accelerate the optimization process. The GOA is a swarm optimization algorithm that mimics the behavior of a grasshopper swarm to solve optimization problems. The HGOALS combines the GOA framework with a decodification procedure and local search to obtain solutions for the OVRP instances. The decodification procedure incorporates a feasibility recovery phase in case the decoded solutions are infeasible.