# A Swarm Intelligence Solution for the Multi-Vehicle Profitable Pickup and Delivery Problem
## 4 Proposed Method
### ABC without Clustering (ABC)
For the medium- and large-sized instances, though, our proposed algorithms did not do well compared to previous methods, as evident by the large average gap percentage compared to the best-known results shown in Table 6. There are many possible reasons for this:

* Again, the methods used in the scout phase of the ABC seem to have an effect on the performance of the proposed algorithms. The first is the greedy randomised strategy, which selects a random customer pair, meaning the worst pair (either with low revenue or separated by a great distance) may be selected, resulting in poor solution quality. Moreover, in some cases, the neighbourhood operators cannot sufficiently enhance the quality of the solution because of time violations or load constraints. The second method uses the GRASP, which constructs solutions by randomly selecting from the Restricted Candidate List (RCL), which is half the size of the Candidate Solution Set (CSS). Thus, selecting unvisited customers is not a problem for small-sized instances because the number of customer pairs is small, which means the chance of selecting the best customer pair (i.e., that with the highest IR2 value) is high. In contrast, in medium- and large-sized instances, where the size of the RCL is large, the chance of selecting the best customer pair decreases, which affects the quality of the solutions. * The number of solutions in a population, the number of iterations, and the limit value play important roles in the algorithmS' performance. In our algorithms, we rely on small numbers of both solutions and iterations because a fast processing time is a critical demand for daily m-commerce apps. These decreased iteration numbers and population sizes, however, reduce the chances of achieving satisfactory solution quality. * All previous algorithms were based on VNS, which has the ability to change the size of the neighbourhood search each time the solution quality is not enhanced. Thus, expanding the neighbourhood structure in a systematic way helps the VNS fully explore the neighbourhood and obtain good solutions. In contrast, the diversification feature in our approach is based either on the greedy feature (inserting the customer pair with the highest IR into the best position) or on a combination of greedy and randomised features (inserting a random customer pair into the best position or inserting a random customer pair from RCL into the best position). However, these strategies seem less successful at diversification than the VNS, which relies on an organised neighbourhood exploration mechanism. Figure 3 compares our proposed algorithms based on the average of the best solutions for each category of instances (highlighted rows in Table 6). It is clear that the ABC in both versions (S1 and S2) still has the preference over all the other algorithms for the instances comprising 20, 50, 100, 250, and 500 customers. In contrast, both versions of K-means-GRASP(C)-ABC(C) and modified K-means-GRASP(C)-ABC(C) outperform the GRASP(V2)-ABC in both versions (S1 and S2) for the 1000-customer instances. The main reasons for the poor performance of clustering algorithms in small- and medium-sized instances is the distribution of customer pairs in K-means and modified K-means, where the clustering process may result in putting a small number of customers within a cluster, which means that the vehicle still has remaining time to serve, but no more customers exist

within that cluster. Thus, we conclude that the clustering algorithms (except ACO) do well in large-sized instances only. Regarding the ACO-GRASP(C)-ABC(C)(S1 and S2), it is clear that it has the worst performance among all algorithms. Again, the clustering method of ACO has a significant effect on results. Specifically, the randomness feature of ACO contributes to an inaccurate clustering of customer pairs.