# A Swarm Intelligence Solution for the Multi-Vehicle Profitable Pickup and Delivery Problem
## 3 Problem Definition  
The MVPPDP is a predefined static problem having several constituents. It is postulated that a centralised depot is responsible for receiving customer requests. These requests comprise pickup and delivery customers in pairs. To fulfil these demands, we operate a fleet of identical vehicles that convey a variety of identical products from a subset of pickup customers to their respective delivery customers, thereby generating a specific profit. The following limitations of the MVPPDP must be considered:  
* The pairing constraint stipulates that a predefined customer pair is assigned to each request (pickup and delivery). * Precedence constraint: Priority must be given to visiting the pickup customer over the delivery customer. * The time limit for journeys: Every vehicle is subject to a daily travel time restriction that must not be surpassed during the service of customers. One limitation is the capacity of each vehicle, which must not be surpassed during product collection from pickup customers. * Every vehicle should depart from and arrive at the depot with an empty load. * A single visit is permitted per customer. The MVPPDP can be formally defined as follows [10]: Let \(G=(V,A)\) be a graph in which \(V=\{0,\ldots,2n+1\}\) defines the vertex set, where the vertex \((0,2n+1)\) corresponds with a central depot, while the remaining vertices represent the pickup customers \(P=\{1,\ldots,n\}\), and delivery customers \(D=\{n+1,\ldots,2n\}\). \(A=\{(i,j):i,j\in V,i\
eq j\}\) defines the arc set, where each arc is associated with a non-negative routing cost \(c_{ij}\). Each delivery vertex \(i\) has a revenue \(r_{i}\) to be gained when visiting it. Also, each vertex \(i\) has a supply \(q_{i}\) (pickup, \(q_{i}>0\)) or demand (delivery, \(q_{n+i}=-q_{i}\)). At the start, there is no supply or demand in the depot (\(q_{0}=0\)). In addition, each vertex \(i\) has service duration \(d_{i}\). There is a set of vehicles \(K=\{1,\ldots,m\}\), and each vehicle has a load capacity \(C\) and maximum tour time \(T\). The objective function (OF) of the MVPPDP aims to maximise the total profit by subtracting the total travel costs from the total revenues. It can be formulated as follows:  
\[Maximize\sum_{i\in V}\sum_{j\in V}\sum_{k\in K}\big{(}r_{i}-c_{ij}\big{)}x_{ijk}, \tag{1}\]  
The mathematical model of the MVPPDP can be formulated as in [4; 6] as follows:  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]  
\[\sum_{j\in V}\sum_{k\in K}x_{ijk}\leq 1\quad i\in V \tag{3}\]  
\[x_{i0k}=0\quad i\in V,k\in K \tag{4}\]  
\[x_{2n+1,jk}=0\quad j\in V,k\in K \tag{5}\]  
\[\sum_{i\in V}\Big{(}x_{ijk}-x_{ijk}\Big{)}=0\;\;j\in V\;\{0,\;2n+1\},\;k\in K \tag{6}\]  
\[\sum_{j\in V}\Big{(}x_{ijk}-x_{n+i,jk}\Big{)}=0\;\;i\in P,\;k\in K \tag{7}\]  
\[\sum_{j=V}x_{0 jk}=\sum_{i=V}x_{i,2n+1,k}=1\;\;k\in K \tag{8}\]  
\[\Big{(}x_{ijk}=1\Big{)}\Rightarrow\;Q_{jk}=Q_{ik}+q_{j}\;\;\;i\in V,\;j\in V\; \{0\},k\in K \tag{9}\]  
\[Q_{ik}\leq C\;\;\;i\in V,\;k\in K \tag{10}\]  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]0  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]1  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]2  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]3  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]4  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]5  
\[\sum_{i\in V}\sum_{k\in K}x_{ijk}\leq 1\quad j\in V \tag{2}\]6  
Constraints (2) and (3) require that each vertex be visited at most once. Constraints (4) and (5) prevent any vehicle from entering the origin depot (beginning point) or leaving the destination depot (end point). Constraint (6) indicates flow conservation. Constraint (7) states that each client pair (pickup and delivery) must be served by the same vehicle. Constraint (8) requires that all vehicles start and return to the depot. Constraint (9) states that exceeding the vehicle capacity is not permitted. Constraint (10) specifies that the load of a vehicle is limited by \(C\).