# A Swarm Intelligence Solution for the Multi-Vehicle Profitable Pickup and Delivery Problem
## 4 Proposed Method
### ABC without Clustering (ABC)
\begin{table}
\begin{tabular}{l c c c c c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**K-Means-GRASP-**} & \multicolumn{3}{c}{**Modified K-Means-**} & \multicolumn{3}{c}{**Modified K-Means-**} & \multicolumn{3}{c}{**ACO-GRASP-**} & \multicolumn{3}{c}{**ACO-GRASP-**} & \multicolumn{3}{c}{**ABSCSD**} & \multicolumn{3}{c}{**ABSCSD**} \\  & **ABSCOS2** & **GRASP-ABICOS1** & **GRASP-ABICOS2** & **ABSCOS1** & **ABSCOS2** & **ABSCOS1** & **ABSCOS2** & & & & & \\  & **Best Profit** & **Gap** & **Best Profit** & **Gap** & **Best Profit** & **Gap** & **Best Profit** & **Gap** & **Best Profit** & **Gap** & **Best Profit** & **Gap** & **Best Profit** & **Gap** \\ \hline
28-500-P-L & 249,792.7 & -24.6 & 225,812.4 & \(-\)31.8 & 247,180.6 & \(-\)25.3 & 152,573.5 & \(-\)53.9 & 196,990.2 & \(-\)40.5 & 201,973.8 & \(-\)39 & 225,040.5 & \(-\)32 \\
29-500-R-S & 172,397.2 & \(-\)38.8 & 108,998.5 & \(-\)61.3 & 175,267.1 & \(-\)37.7 & 141,743.7 & \(-\)49.6 & 128,570.6 & \(-\)54.3 & 178,693.9 & \(-\)36.5 & 173,000.3 & \(-\)38.5 \\
30-S0-R-L & 27,488.2 & \(-\)33.9 & 241,454.2 & \(-\)42.1 & 294,242.4 & \(-\)24.4 & 167,819.5 & \(-\)59.7 & 214,081.3 & \(-\)59.7 & 214,081.3 & \(-\)48.6 & 299,675.7 & \(-\)425 & 261,517.2 & \(-\)37.3 \\ Average & 174,897.1 & \(-\)36.9 & 140,358.2 & \(-\)49.3 & 179,281.9 & \(-\)35.3 & 117,580.3 & \(-\)57.5 & 132,124.8 & \(-\)51.9 & 157,852.2 & \(-\)43 & 170,060.5 & \(-\)38.6 \\
500 & 15,188.2 & \(-\)70.5 & 39,530.2 & \(-\)49.3 & 170,281.9 & \(-\)35.3 & 233,266.5 & \(-\)56.6 & 25,563.9 & \(-\)85.2 & 33,125.19 & \(-\)80.9 & 42,197.08 & \(-\)75.7 \\
32-1000-F-S & 97,035.1 & \(-\)67.7 & 92,142.15 & \(-\)62.7 & 97,772.5 & \(-\)60.4 & 24,110.8 & \(-\)90.2 & 47,620.03 & \(-\)80.7 & 57,137.24 & \(-\)76.9 & 73,126.9 & \(-\)70.4 \\
32-1000-P-S & 293,900.2 & \(-\)36.7 & 26,797.1 & \(-\)49 & 257,774.9 & \(-\)38 & 178,654.3 & \(-\)61.5 & 209,372.1 & \(-\)54.9 & 240,944.9 & \(-\)48.1 & 267,814.2 & \(-\)42.3 \\
34-1000-P-L & 536,199.8 & \(-\)24.7 & 492,533.1 & \(-\)30.8 & 534,899.8 & \(-\)24.9 & 364,249.9 & \(-\)51.4 & 331,116.4 & \(-\)46.5 & 397,930.0 & \(-\)44.1 & 430,894.4 & \(-\)39.5 \\
35-1000-R-S & 264,295.2 & \(-\)46.2 & 192,003.08 & \(-\)60.9 & 249,078.6 & \(-\)49.3 & 124,538.1 & \(-\)74.6 & 181,237.2 & \(-\)63.1 & 212,979.1 & \(-\)56.7 & 223,298.7 & \(-\)52.7 \\
36-1000-R-L- & 481,126.7 & \(-\)35 & 470,703.7 & \(-\)42.1 & 463,915.7 & \(-\)34.2 & 297,218.8 & \(-\)57.8 & 335,935.6 & \(-\)52.3 & 364,643.1 & \(-\)48.2 & 380,286.9 & \(-\)46 \\ Average & 276,004.15 & \(-\)40.7 & 273,492.8 & \(-\)47.7 & 280,802.8 & \(-\)39.7 & 165,671.2 & \(-\)64.4 & 196,807.5 & \(-\)57.7 & 217,793.3 & \(-\)53.2 & 227,766.7 & \(-\)48.9 \\
1000 & 276,004.15 & \(-\)40.7 & 243,492.8 & \(-\)47.7 & 280,802.8 & \(-\)39.7 & 165,6712. & \(-\)64.4 & 196,807.5 & \(-\)57.7 & 217,793.3 & \(-\)53.2 & 227,766.7 & \(-\)48.9 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: _Cont._The best-known profit was computed in [9] by running each instance for 20 h, and then the best profit was saved as the best-known profit. As can be seen from Tables 6 and 7, our proposed algorithms perform well in terms of profit for small-size instances, with the ABC(S1) returning six new best solutions and two other solutions that were equal to the best-known solutions. The ABC(S2) also achieved three new best solutions and three solutions that are equal to the best-known solution. Also, the modified K-means-GRASP(C)-ABC(C)S1 achieved two new best solutions. In addition, the K-means-GRASP(C)-ABC(C)S1, K-means-GRASP(C)-ABC(C)S2, modified K-means-GRASP(C)-ABC(C)S2, and ACO-GRA-SP(C)-ABC(C)S2 each produced one new best solution. Overall, the general performance for all proposed algorithms was acceptable and close to the previous algorithms in terms of average profit on these instances.