# A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem
## 5 A Case Study  
A security and alarm company requires its payment collection routes to be more efficient for two reasons: the first is to reduce the days required to collect payments, and the second is to reduce the fuel consumption used by the company representative. The company provides alarm and security services on a monthly or yearly basis. Customers choose the type of service they require and pay on the same basis. Therefore, at the beginning of each month, the company requires to collect payment from around 100 customers. Payment collection routes were decided by the company representative based on his experience and usually took between three to four weeks to be completed (15 to 20 working days). The company \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Group** & **HGOALS** & **BBMO [37]** & **BLSA [38]** & **HBMO [44]** & **ORTR [35]** \\ \hline C & 69.46 & 69.21 & 122.29 & 73.33 & 112.73 \\ O & 846.16 & 210.75 & 1057.75 & 217.95 & 709.95 \\ K & 889.04 & – & – & – & – \\ \(BKS\) & 20/30 & 5/22 & 12/15 & 1/22 & 7/22 \\ \(Model\) & Core-2 & T9550 & T5550 & T9550 & Athlon 1 Ghz \\ \(Factor\) & 22.1(1) & 18.1(0.82) & 14(0.63) & 18.1(0.82) & 5.75(0.26) \\ \hline
**Group** & **HGOALS** & **MVNS**[34] & **HES [36]** & **TSB [32]** & **ALNS [45]** \\ \hline C & 69.46 & 485.71 & 581.50 & 559.41 & 1255.00 \\ O & 846.16 & – & 1051.50 & – & – \\ K & 889.04 & – & – & – & – \\ \(BKS\) & 20/30 & 6/14 & 6/22 & 2/14 & 4/14 \\ \(Model\) & Core-2 & Pentium M & Pentium 4 & Pentium 3 & Pentium 4 \\ \(Factor\) & 22.1(1) & 9.04(0.41) & 11.05(0.52) & 5.11(0.23) & 11.05(0.52) \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Average CPU times comparison for the different solution approaches (hierarchical objective function). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Group** & **HGOALS** & **BBMO [37]** & **BLSA [38]** & **HBMO [44]** & **BRKGA [43]** \\ \hline C & 50.23 & 59.77 & 110.29 & 61.72 & 326.70 \\ O & 860.10 & – & 1017.50 & – & 6163.79 \\ K & 804.89 & – & – & – & 6496.05 \\ BKS & 18/30 & 5/14 & 11/15 & 3/14 & 10/30 \\ Model & Core-2 & T5550 & T9550 & T9550 \\ Factor & 22.1(1) & 18.1(0.82) & 14(0.63) & 18.1(0.82) & 22.1(1) \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Average CPU times comparison for the different solution approaches (minimizing traveling cost). provided the addressees of customer required to pay in the next two months. They also set a maximum number of customers to be visited per day (15 per day) and a maximum of working hours per day (seven hours). Finally, they provided the routes planned by the company representative in charge of collecting the payments for the next two months. A geographic information system (GIS), customers' addresses, and a web-based tool were used to build cost(distance) and time matrices to feed the algorithm. Such matrices were non-symmetric. The capacity parameter was set to \(Q=15\), the service time was set to 0.25 hours and the maximum route length to \(L=7.0\) hours. The algorithm was run five times using this information and the best solution was chosen. The results are presented in Table 12, where columns _Dist CRP_, _Days CRP_, _Dist HGOALS_ and _Days HGOALS_ show the total distance and required days for the routes planned by the company representative and the routes obtained by the HGOALS respectively. Columns _Dist % red_ and _Days % red_ show the percentaje reduction in total distance and working days obtained with the use of HGOALS proposed routes instead of the planned routes by the company representative. Finally, column _CPU_ denotes the CPU time in seconds required by the algorithm and column %_gap_ the gap with the best solution obtained by using a modified version (directed) of the formulation in [49] on CPLEX. This last column was added to verify the performance of the algorithm on real-life instances. For the exact method, a maximum CPU time was set to \(10,800\) s.  
The results show a significant reduction in terms of total distance and working days.