# A Swarm Intelligence Solution for the Multi-Vehicle Profitable Pickup and Delivery Problem
## 4 Proposed Method
### ABC without Clustering (ABC)  
In this part of the research, we aimed to improve the initial solutions that have been achieved using the improved GRASP in [7]. The ABC metaheuristic consists of three phases: the employed bee phase, the onlooker bee phase, and the scout bee phase. The main goal of the first two phases is to increase the intensification of the search space to obtain good solutions, while the last phase aims to increase the diversification and prevent getting stuck in local optima. The details of our proposed algorithm are illustrated below. 1. Employed bee phase: After assigning the initial solutions to the employed bees, they start a neighbourhood search to find better solutions nearby by randomly selecting one of a set of neighbourhood operators. The neighbourhood operators aim to make a small change to the solution to improve it. Thus, for each solution, one route is selected randomly to apply one operator that is also selected randomly. The set of neighbourhood operators is described below: * Relocate a pickup customer only: Choose one pickup customer randomly and relocate its position, such that the new pickup position must not come after its delivery customer. * Relocate a delivery customer only: Choose one delivery customer randomly and relocate its position, such that the new delivery position must not come before its pickup customer. * Relocate a customer pair: Choose a customer pair randomly and relocate their positions, preserving the precedence constraint (i.e., pickup before delivery). * Swap two customer pairs: Select two customer pairs randomly and swap their positions. * Two-Opt operator: Select two consecutive pairs of customers (a consecutive pair is one in which a pickup customer is followed directly by its delivery customer) and reorder the edges between pairs while considering the precedence constraint. * Remove one customer pair randomly and insert an unvisited one: Remove a customer pair randomly, select an unvisited customer pair that has a high insertion ratio (IR) using Equation (18), and insert it into the best position in the route. \[IR_{customerpair}=\frac{r_{customerpair}}{c_{(depot,PC)}},\] (18) where \(r\) is the revenue of the customer pair and \(c_{(depot,PC)}\) is the distance between the depot and the pickup customer of that pair. * Remove a customer pair with a low IR and insert an unvisited pair with a high IR: Compute the IR for all visited pairs using Equation (18), and remove a customer pair with the lowest IR value. Then, recompute the IR for all unvisited customer pairs, select one with the highest IR value, and insert it into the best position in the route. * Insert a customer pair with a high IR: Compute the IR for all unvisited customer pairs, select one with the highest IR value, and insert it into the best position in the route. After applying the selected neighbourhood operator, if the new solution S' is feasible, the fitness of S' is computed using Equation (1) and compared with the fitness of the old solution S. To escape from local optima, we decided to use the demon algorithm (DA) rather than a simple local search algorithm, since the DA has the ability to accept a feasible non-improved new solution. The DA is a variant of the SA that was presented by [PERSON] [19]. The acceptance function of the DA is based on the value of the demon (credit) that is initialised at the beginning with a given value \(D\). In the case where the new solution \(S^{\prime}\) is not an improvement, the difference (\(\Delta E\)) between the fitness of \(S\) and \(S^{\prime}\) is compared with the demon value, and \(S^{\prime}\) is accepted if this difference is less than or equal to \(D\). Then, if \(S^{\prime}\) is accepted, it is memorised, and the value of \(D\) is decreased; otherwise, the old solution \(S\) is memorised, the \(D\) value is increased, and a non-improvement counter for this solution is increased by one. The DA is simpler and faster than the SA because the latter requires more computational time for generating a random number and an exponential function.