# How to construct LIFO constraints in Pickup and Delivery Problem

I am reading the following paper on the pick-up delivery problem with LIFO but ultimately failing to understand the LIFO constraint that the authors used. Here is the paper:

• Cherkesly, M., Desaulniers, G., & Laporte, G. (2015). Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Science, 49(4), 752-766.

The authors define a subset $$S$$ of all node $$N$$ and then defines a constraint (7) on this subset. If you are familiar with LIFO invoved VRP would you be able to explain how this subset be can be visulaized? Is there a better way to construct the LIFO constraints?

Below is the section where they proposed the model.

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

• Ok I'd update my response Jan 17, 2023 at 13:51
• thanks for writing an answer, I get what the MATEC paper is doing, but I do not get how the set $S$ is constructed in the screenshot (highlighted) I uploaded.
– mars
Jan 20, 2023 at 0:35