How to mathematically model this vehicle routing with pickup and deliveries problem?

Question

I have this problem right here

There are N passengers whose are at places 1,2,...,N respectively. The i-th passenger, who is currently at place i, wants to go to place i+N. There are K buses are currently at place 0. Bus k can only contains q(k) number of passengers at the same time. Given the 2-dimensional array distance matrix d, where d[i][j] is the distance of place i to place j. Make an optimal route plan so that the total distance traveled by all buses is the shortest.

Input data:

• number of passengers: N
• number of buses: K
• distance matrix: 2D matrix d, d[i][j] is the distance from i to j
• List of buses' capacity: 1D matrix q, where q[k] is the capacity of bus k

Output data:

• Route plan for K buses
• Total distances traveled

The progress is:

• place 0: depot
• place 1 -> N: pickup places
• place N+1 -> 2N: drop places

I came up with some constraints also, but I think these are not enough:

• The number of passengers <= the capacity of the bus
• Buses start with 0 passengers and end with 0 passengers
• Each bus go through a place ONCE
• ... And some more, for instance: constraint for avoiding subtours

Can anybody help me out with this problem?

Answer 1

The below is what I put in in another answer. It has additional LiFO constreaint- last load pickup, first to be dropped.

Basically it says after the last pickup vehicle $k$ doesn't visit any other node unless the node is a delivery point $\in D$ for the last picked up request.

Hierarchical Objective - minimize travel time and number of unserved customers. Other objectives could be minimize number of vehicles needed and transport cost.

Sets
Nodes:$N_i$
N = $O \cup P \cup D$ where O=$\{0,2n+1\}$:depot; P=$\{1,2,...n\}$ Pickup points and
$D=\{n+1,n+2,...2n\}$ Delivery points: basically pickup and delivery points are paired\

Arcs: $A_{ij}$
Open/Close time for each point $e_i, l_i $
Vehicles: $K = \{1,2,...v\}$: with capacity $Q_k$

Parameters Request: $q_i$: it's the load from pickup $i$ to delivery $n+i$
$q_{n+i}+q_i = 0$
Customers $≡ $Pickup point request, so number of customers = $ \vert P \vert = n$

Variables
$x_{ijk} \in \{0,1\}$ indicates if vehicle $k$ is used on trip $i,j$
$T_{ik}$: Total travel time for vehicle $k$ from node $i$
$L_{ik}$: total load for vehicle $k$ from node $i$

obj = $\min w_1 (\sum_{k\in K}\sum_{i,j\in A}t_{ij}x_{ijk}) + w_2\frac{(n-\sum_k\sum_{i,j \in A}x_{ijk}-v)}2 $
s.t.

$T_{ik}+ t_{ij} - M(1-x_{ijk}) \le T_{jk} \ \ \forall i,j \in A \ \forall k \in K$
$L_{ik}+ q_{j} - M(1-x_{ijk}) \le L_{jk} \ \ \forall i,j \in A \ \forall k \in K$
$e_i \le T_{ik} \le l_i \ \ i \in O$

Pairing & Precedence
$\sum_{j\in N}x_{ijk} = \sum_{j\in N}x_{j,n+i,k} \ \ \forall i \in P \ \ \forall k$
$T_i + t_{i,n+i} \le T_{n+i} \ \ \forall i \in P \ \forall k$

Enure each vehicle leaves & returns to depot: Subtour prevention $\sum_j x_{0,j,k}=\sum_i x_{i,2n+1,k}\ \ \forall k$
$\sum_j x_{0,j,k}=1 \ \ \forall k$
$1 \le \sum_k\sum_j x_{ijk} \ \ \forall i \in N$

$q_i \le L_{i,k} \ \ \forall k \ \forall i \in P$

LIFO Policy-basically after a pickup vehicle cant travel to another unpaired delivery point
$L_{n+i,k} = L_{i,k}-q_i \ \ \forall i \in P \ \forall k$
$\sum_{j\in D-\{n+i\}}x_{ijk} = 0 \ \ \forall i \in P \ \ \forall k$

$0 \le L_{i,k}; 0\le T_{i,k} \ \forall i \in N $

$w_1,w_2$ are objective weights for significance or priority.

References that explain it better
MATEC,
U of Montreal,
IEEE