## 4 Algorithms
### Path Relinking Procedure
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**Best-Known**} & \multicolumn{3}{c}{**Our Best**} & \multirow{2}{*}{\%Gap**} & \multirow{2}{*}{\%Gap**} & \multirow{2}{*}{\%Gap**} \\ \cline{2-2} \cline{4-7}
**Problem** & \
\begin{tabular}{c} **Number of** \\ **Vehicles** \\ \end{tabular} & **Total Distance** & **Reference** &
\begin{tabular}{c} **Number of** \\ **Vehicles** \\ \end{tabular} & **Total Distance** & **Time (s)** \\ \hline C101 & 5 & 362.4 & [47] & 5 & 362.4 & 0.000 & 104.8 \\ C102 & 5 & 361.4 & [47] & 5 & 361.4 & 0.000 & 104.1 \\ C103 & 5 & 361.4 & [47] & 5 & 382.1 & 5.727 & 104.8 \\ C104 & 5 & 358.0 & [47] & 5 & 361.1 & 0.8659 & 104.7 \\ C105 & 5 & 362.4 & [47] & 5 & 362.4 & 0.000 & 98.30 \\ C106 & 5 & 362.4 & [47] & 5 & 362.4 & 0.000 & 101.1 \\ C107 & 5 & 362.4 & [47] & 5 & 362.4 & 0.000 & 97.12 \\ C108 & 5 & 362.4 & [47] & 5 & 362.4 & 0.000 & 104.8 \\ C109 & 5 & 362.4 & [47] & 5 & 362.4 & 0.000 & 95.53 \\ \hline C201 & 3 & 360.2 & [17] & 3 & 360.2 & 0.000 & 275.6 \\ C202 & 3 & 360.2 & [17] & 3 & 360.2 & 0.000 & 207.4 \\ C203 & 3 & 359.8 & [17] & 3 & 359.8 & 0.000 & 469.5 \\ C204 & 2 & 350.1 & [17] & 2 & 357.6 & 2.142 & 472.4 \\ C205 & 3 & 359.8 & [17] & 3 & 359.8 & 0.000 & 349.7 \\ C206 & 3 & 359.8 & [17] & 3 & 359.8 & 0.000 & 427.4 \\ C207 & 3 & 359.6 & [17] & 3 & 359.6 & 0.000 & 226.2 \\ C208 & 2 & 350.5 & [17] & 2 & 350.5 & 0.000 & 458.7 \\ \hline R101 & 12 & 1044 & [47] & 12 & 1049 & 0.4789 & 124.4 \\ R102 & 11 & 909.0 & [47] & 11 & 909.0 & 0.000 & 116.6 \\ R103 & 9 & 772.9 & [47] & 9 & 772.9 & 0.000 & 128.6 \\ R104 & 6 & 625.4 & [47] & 6 & 636.0 & 1.694 & 95.72 \\ R105 & 9 & 899.3 & [47] & 11 & 922.4 & 2.568 & 105.3 \\ R106 & 5 & 793.0 & [47] & 9 & 795.5 & 0.3153 & 128.5 \\ R107 & 7 & 711.1 & [47] & 7 & 711.1 & 0.000 & 95.11 \\ R108 & 6 & 617.7 & [17] & 6 & 623.7 & 0.9713 & 95.83 \\ R109 & 8 & 786.8 & [47] & 8 & 792.0 & 0.6609 & 118.4 \\ R110 & 7 & 697.0 & [47] & 8 & 718.5 & 3.084 & 127.7 \\ R111 & 7 & 707.2 & [17] & 7 & 719.3 & 1.711 & 87.38 \\ R112 & 6 & 630.2 & [17] & 6 & 650.3 & 3.189 & 97.39 \\ \hline R201 & 6 & 791.9 & [17] & 6 & 812.1 & 2.550 & 143.3 \\ R202 & 5 & 698.5 & [17] & 6 & 715.4 & 2.419 & 140.3 \\ R203 & 5 & 605.3 & [48] & 5 & 613.8 & 1.404 & 160.0 \\ R204 & 2 & 506.4 & [48] & 3 & 512.7 & 1.244 & 153.2 \\ R205 & 4 & 690.1 & [48] & 5 & 700.0 & 1.434 & 117.1 \\ R206 & 4 & 632.4 & [48] & 5 & 643.4 & 1.739 & 153.7 \\ R207 & 2 * & 594.0 * & [50] & 3 & 584.2 & \(-1.649*\) & 133.4 \\ R208 & 2 * & 508.4 * & [50] & 2 & 496.2 & \(-2.399*\) & 189.5 \\ R209 & 4 & 600.6 & [48] & 4 & 600.6 & 0.000 & 109.0 \\ R210 & 4 & 645.6 & [48] & 5 & 655.5 & 1.533 & 167.3 \\ R211 & 3 & 535.5 & [48] & 4 & 552.2 & 3.118 & 133.3 \\ \hline RC101 & 8 & 944.0 & [47] & 8 & 944.8 & 0.08475 & 183.0 \\ RC102 & 7 & 822.5 & [47] & 8 & 838.9 & 1.993 & 215.5 \\ RC103 & 6 & 710.9 & [47] & 7 & 754.5 & 6.133 & 224.9 \\ RC104 & 5 & 545.8 & [47] & 5 & 552.2 & 1.172 & 234.0 \\ RC105 & 8 & 855.3 & [47] & 9 & 889.0 & 3.940 & 211.2 \\ RC106 & 6 & 723.2 & [47] & 7 & 769.0 & 6.333 & 234.9 \\ RC107 & 6 & 642.7 & [47] & 6 & 670.2 & 4.278 & 229.3 \\ RC108 & 6 & 598.1 & [47] & 6 & 598.1 & 0.000 & 210.5 \\ \hline RC201 & 5 & 684.8 & [15] & 5 & 684.8 & 0.000 & 139.1 \\ RC202 & 5 & 613.6 & [48] & 5 & 613.6 & 0.000 & 139.3 \\ RC203 & 4 & 555.3 & [48] & 4 & 566.2 & 1.962 & 154.1 \\ RC204 & 3 & 444.2 & [51] & 3 & 447.2 & 0.6754 & 152.1 \\ RC205 & 5 & 630.2 & [48] & 5 & 633.7 & 0.5554 & 130.9 \\ RC206 & 5 & 610.0 & [48] & 5 & 610.1 & 0.01639 & 195.0 \\ RC207 & 4 & 558.6 & [49] & 5 & 562.5 & 0.6982 & 139.5 \\ RC208 & 2 * & 498.8 * & [50] & 4 & 490.6 & \(-1.643*\) & 122.3 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparisons between the exact solution or best solutions (with ”*”) and the results obtained by our heuristic on 50-customer Solomon instances.