# A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem
## 3 Hybrid Grasshopper Optimization Algorithm with Local Search
### The Route Decoder  
As mentioned before, the HGOALS requires the implementation of a decoder. Other decoders for similar problems have been previously proposed. The objective of proposing a new decoder is to find  
Figure 1: Flow diagram for the hybrid grasshopper optimization algorithm with local search (HGOALS).  
better results than those obtained by previous decoders and other metaheuristics. In this section, the new decoder is described.  
The route decoder (RD) requires as input the associated cost to every arc \(c_{ij}\), \(|\)\(a\in A\), the random-key vector \(\mathcal{X}\) and the demand vector \(d\). The random-key vector \(\mathcal{X}\) contains \(n+1\) fractional values. \(\mathcal{X}_{0}\), the first value in vector \(\mathcal{X}\), is used to define the total number of vehicles available in the solution. The other \(n\) values are used to assign vertices to different vehicles. The decoder determines the total number of vehicles, by first computing the minimum number of vehicles required to deliver all the clients demand using:  
\[MV=\left\lceil\frac{d(V^{+})}{Q}\right\rceil\]  
where:  
\[d(V^{+})=\sum_{i\in V^{+}}d_{i}\]  
Using the random-key vector value \(\mathcal{X}_{0}\) the number of available vehicles in the solution is given by:  
\[NV=\left\lceil MV(1+\mathcal{X}_{0})\right\rceil\]  
Then the interval \([0,1]\) is divided into \(NV\) subintervals. Each client is assigned to a vehicle using these subintervals and the keys associated with each client. Once all clients have been assigned to a vehicle, they are sorted in ascending order according to their key. The routes are built using the sorted keys. Figure 2 illustrates an example of how the proposed decodification procedure works. In this example, using the demand vector \(d\), the capacity parameter \(Q=20\) and the first key-value \(\mathcal{X}_{0}=0.28\), the minimum and the available number of vehicles are obtained: \(MV=2\) and \(NV=3\) respectively. Therefore, the interval \([0,1]\) is divided into three subintervals which are used to assign clients to vehicles. Clients 4, 6 and 8 are assigned to vehicle number 1; clients 1, 2, 3 and 5 are assigned to vehicle 2; and clients 7, 9 and 10 are assigned to vehicle number 3. For vehicle 1, the assigned vertices are transformed into the route \(0-8-4-6\); for vehicle 2, the resulting route is \(0-5-2-1-3\). Finally, for vehicle 3, the resulting route is \(0-7-10-9\).  
Figure 2: Route decoder example.  
It is relevant to notice that this decodification/codification method can lead to infeasible solutions. In Figure 3, an example of an infeasible solution is presented. The violation is made over the capacity and maximum distance constraints since for \(s\)-route \(R_{8}\), \(d(R_{8})>Q\) and \(l(R_{8})>L\).  
Whenever a solution is infeasible after decoding, it enters the feasibility recovery procedure. The feasibility recovery procedure reassigns subroutes or vertices from the infeasible route to other routes with available capacity and without violating the maximum length constraint. If there are no suitable routes for reassigning a given subroute or vertex, a new route is created by connecting such subroute or vertex directly to the depot. The reassignment is made by replacing arcs on the solution, using the cheapest available that reduces or eliminates the route's infeasibility. Figure 4 shows how the feasibility recovery procedure repairs an infeasible solution. In this example, \(s\)-route \(R_{8}\) violates the capacity and maximum distance constraints (\(d(R_{8})>Q\) and \(l(R_{8})>L\)). For recovering feasibility, subroute \(R_{5}\) is removed from \(R_{8}\). Since annexing \(R_{5}\) to \(s\)-route \(R_{7}\) will violate the maximum length constraint, \(R_{5}\) is directly connected to the depot. At this point, \(R_{8}\) only violates the capacity constraint. Therefore, vertex 10 is removed from \(R_{8}\) and annexed to \(s\)-route \(R_{7}\), leading to a feasible solution.