# A Swarm Intelligence Solution for the Multi-Vehicle Profitable Pickup and Delivery Problem
## 2 Related Studies  
The MVPPDP is classified as a type of SPDP and its objective is to maximise profits while minimising travel expenses by visiting only profitable customer pairs. Achieving a favourable route that maximises the difference between the total revenue earned and the total ravelling cost is the objective of both the MVPPDP and the profitable tour problem (PTP). The primary distinction is that in the PTP, the vehicle route is not subject to any constraints, including but not limited to the maximum trip time, vehicle capacity limits, or precedence constraints [8]. Research focusing on the PTP is in short supply in the scientific literature [9]. Hence, we commence by presenting research pertaining to the MVPPDP. [PERSON] et al. [4] introduced the initial four algorithms. The variable neighbourhood search (VNS) metaheuristic was implemented in [10]. The greedy construction heuristic (C1) and the two-stage cheapest insertion heuristic (C2) were employed during the construction phase of the VNS. During the improvement phase, the subsequent neighbourhood operators were implemented: the pairwise backward exchange, the pairwise forward exchange, forward insertion, relocate pairs, backward insertion, inter-tour exchange, inter-tour insert, inter-dummy insert, inter-dummy exchange and the gravity centre exchange. The authors implemented two approaches for applying the neighbourhood operators: a sequential (Seq) method, which employs a predetermined sequence of neighbourhoods, and a self-adaptive (Sea) method, which adjusts itself based on the search status to determine the sequence of neighbourhoods. In order to compare the proposed method with an alternative algorithm, a guided local search (GLS) metaheuristic-based algorithm was ultimately implemented. An evaluation of the proposed algorithm was conducted on 36 randomised instances of varying sizes. In terms of solution quality, the experimental results demonstrated that both variants of the VNS outperformed the GLS. [PERSON] [11] introduced a new algorithm to solve the MVPPDP. Pending a solution to the profitable pickup and delivery problem, they proposed an algorithm known as IPPD, which was derived from a combination of an iterated local search and random variable neighbourhood descent. During the search, the IPPD algorithm was not restricted to accepting only viable solutions. For the construction of the initial solution, the C1 heuristic utilised by [PERSON] et al. [4] was implemented. To enhance the solution, several neighbourhood moves were implemented: pair swap or pair shift, block swap or block shift, pickup or delivery shift, inter-block swap or inter-block shift, gravity centre exchange, insert operator and remove operator, and inter-pair swap or inter-pair shift. On the benchmark instances suggested by [PERSON] et al. [4], the proposed algorithm was evaluated. It demonstrated its effectiveness in handling small- and medium-sized cases by identifying new optimal solutions for six cases. However, for large instances, the performance of the proposed algorithm was inadequate. In [PERSON] and [PERSON] [6], the construction phase of the widely recognised greedy randomised adaptive search procedure (GRASP) was employed to develop preliminary solutions for the MVPPDP. They used the same dataset that was created by [4]. They conducted a performance comparison between the method and two construction heuristics that had been previously documented in the literature for constructing initial solutions to the MVPPDP. The experimental results demonstrated that the proposed method outperformedalternative construction heuristics, particularly in instances of a small size, where eight new best initial solutions to the problem were obtained. In [7], [PERSON] and [PERSON] presented new heuristics to construct initial solutions for the MVPPDP. The heuristics are based on first clustering the search space of the MVPPDP using three clustering methods: K-means, adaptive K-means, and ant colony optimisation (ACO).