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

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
• Each bus go through a place ONCE
• ... And some more, for instance: constraint for avoiding subtours

Can anybody help me out with this problem?

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