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.

![enter image description here

enter image description here


1 Answer 1


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.

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$

$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 $

$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

  • 1
    $\begingroup$ Ok I'd update my response $\endgroup$ Jan 17, 2023 at 13:51
  • $\begingroup$ 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. $\endgroup$
    – mars
    Jan 20, 2023 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.