# A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems
## 4 Computational Experiments  
The iteration curve of depot A is shown in Figure 9. Compared with the initial solution, after 30 iterations, the objective function of the final solution is reduced by 29.5 and has converged at the 8 th iteration. The iteration curve of depot B is shown in Figure 10. After 18 iterations, the final solution reduces the distance of 27.44 compared with the initial solution. The curve has converged at the 6 th iteration. It can be seen that the merge-head and drop-tail strategy improves the initial solution quickly, and the number of iterations is small so that a better solution can be obtained quickly. Figure 8: The road map of the final solution. Figure 9: The iteration curve of the depot A. Considering 23 benchmark instances proposed for the MDVRP, the performance of the sector combination optimization algorithm and the merge-head and drop-tail optimization strategy are shown in Table 1. The experiment was implemented in Python, on Intel(R) Core(TM) i5-4260(U) CPU @ 1.40 GHz (manufacturer: Apple Inc., Cupertino, California, USA). In Table 1, for each instance, the meaning of the notation is provided at the end of this paper. In Table 1, for each instance, the parameters in Table 2 are used. Taking the instance 1 as an example, it has 50 customers and four depots, and each depot has four vehicles with a capacity of 80. We adopt the SCO algorithm to get 30 initial solutions and improve these 30 solutions by the MHDT algorithm until the ending criterion, namely 20 iterations, is met. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multicolumn{6}{c}{**Characteristics of Instances**} & \multicolumn{2}{c}{**BKS**} & \multicolumn{2}{c}{**SCO**} & \multicolumn{2}{c}{**MHDT**} \\ \hline
**Inst** & **N** & **M** & **K** & **P** & & **Distance** & **Time1** & **Distance** & **Gap** & **Time2** \\ \hline
1 & 50 & 4 & 4 & 80 & 576.87 & 641.89–897.21 & 1.21 & 602.05 & 4.36 & 2.38 \\
2 & 50 & 4 & 2 & 160 & 473.53 & 51  
The sector combination optimization algorithm makes the initial solutions more abundant and better, compared with other iterative algorithms only using one initial solution such as the genetic algorithm adopted by [PERSON] et al. [8] and granular Tabu search algorithm adopted by [PERSON] et al. [21]. [PERSON] et al. adopted the CWS method to get a solution for initialization. For the small problem with 13 customers, the objective function value of the solution obtained by CWS is 221.66, and the objective function values of 50 initial solutions obtained by the sector combination optimization algorithm fluctuate between 150 and 250, of which 82% is below 221.66, as shown in Figure 11. For the two depots with 249 customers of the instance 8, as shown in Table 1, the objective function value of the solution obtained by CWS is 4671.2, and the objective function values of 50 initial solutions obtained by the sector combination optimization algorithm fluctuate between 2500 and 3500, of which 100% are below 4671.2. It can be seen that the initial solution obtained by the sector combination optimization algorithm is better. With these solutions as the initial population of the genetic algorithm and ant colony algorithm, the number of iterations can be reduced to achieve fast convergence. Additionally, because of the abundant initial solutions, the algorithm can avoid trapping in a local optimum. [PERSON] et al. proposed a hybrid granular Tabu search (GTS) algorithm for the MDVRP based on a cluster approach like our algorithm while they aimed to find the best solutions. The initial MDVRP solution is obtained by using a hybrid initial procedure (GTS1) and improved by the granular Tabu search procedure (GTS2). We illustrate the performance of the two algorithms in terms of CPU time and distance for comparisons. Combing Figure 12 with Figure 13, we conclude that the CPU time consumed by our algorithm is obviously lower than theirs while the distance Gap of our results is less than seven in all instances.