## 1 Introduction  
The vehicle routing problem with simultaneous pickup and delivery (VRPSPD) [1; 2; 3; 4; 5; 6; 7; 8; 9], in which customers demanding both delivery and pickup operations have to be visited once by a single vehicle, is one of the main classes of the vehicle routing problem (VRP). This class has attracted research attention due to its applicability in numerous reverse logistic systems. For instance, in the bottled drinks industry, full bottles are delivered and empty ones are collected simultaneously from the customers. In fact, companies are increasingly faced with the task of managing the reverse flow of finished goods or raw materials [6]. In this context, one should consider together the logistics of distribution and the management of the reverse flow to minimize pickup and delivery operational efforts. Originally, the VRPSPD assumes a homogeneous fleet of vehicles. However, in many practical situations, companies employ a heterogeneous fleet of vehicles to satisfy customer demands. In this paper, we focus our attention on this variant of the VRPSPD. In fact, the heterogeneous vehicle routing problem with simultaneous pickup and delivery (HVRPSPD) has received research interest only in very recent years [10; 11; 12; 13]. The HVRPSPD can be formally stated as follows: Let \(G=(\mathcal{N},\mathcal{A})\) be a complete directed graph with a set of nodes \(\mathcal{N}=\{0,1,\ldots,n\}\), where the node \(0\) represents the central depot and the remaining nodes denote the customers. Each customer \(i\in\mathcal{N}-\{0\}\) has non-negative delivery \(d_{i}\) and pickup \(p_{i}\) demands. Each arc \(ij\in\mathcal{A}\) is associated with a distance \(c_{ij}\) from node \(i\) to node \(j\). The fleet of vehicles involves \(T\) different vehicle types, and there is no restriction on the number of vehicles of each type. Every vehicle type \(t=1,2,\ldots,T\) is associated with a fixed cost \(f_{t}\), a variable cost per distance unit \(g_{t}\), and a capacity \(q_{t}\). We aim to determine the fleet composition and the set of vehicle routes that minimize the total cost, such that each vehicle travels exactly one route; each route starts and ends at the depot; each customer is visited only once by one of the vehicles; the vehicle completely satisfies the pickup and delivery demands of the customers on its route; the load carried by a vehicle must not exceed its capacity. This problem has mainly been tackled by means of metaheuristics. In [10], a hybrid heuristic based on simulated annealing and local search is proposed to solve medium and large-size instances of the HVRPSPD. In [11], the authors propose a multi-label-based ant colony system algorithm to address the HVRPSPD. An initial solution is obtained by a nearest neighbor strategy, and then the ant colony system algorithm is applied to minimize the total number of vehicles used to attend the customers and the total travel distance performed by the vehicles. To evaluate their algorithm, they use benchmark problem instances adapted from other classes of the VRP. In [12], the authors present a mathematical model for the problem and propose some valid inequalities. In addition, a hybrid matheuristic based on the mathematical formulation in conjunction with a local search is presented. The state-of-the-art approach to tackle the HVRPSPD, to the best of our knowledge, appears in [13]. The authors propose the integration of an adaptive threshold strategy into a tabu search algorithm to avoid getting trapped in local minima. Their approach is based on neighborhood search and defines four different neighborhood structures to explore the solution space. It employs a giant tour representation to encode solutions and a decoding mechanism to partition the giant tour into feasible vehicle routes. For each giant tour, a cost network representation is constructed and a Djikstra algorithm is used to provide an optimal partition of the customers.