Asymmetric time-constrained capacitated vehicle routing problem

Question

I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)¹ (pp.4).

The mentioned model caps the travel distance, while I cap the travel time. Let $U$ represent the maximum travel time each vehicle can make. Additionally, there is a node-dependent time spent at each delivery node. For example, if 5 packages are delivered to location $j$, the truck will spend 25 minutes (assuming 5 min per package). I think, I can address this by embedding, $s_j:=\text{time spent at delivery node } j$, into (6) and (9). I don't add this into the objective because I only want to minimize the travel time without including the package drop time. Firstly, is the following formulation correct based on the assumptions? Consider the following set definitions: $I$ set of nodes, where $0$ represents the depot, and the parameter: $T_{ij}$ is the asymmetric travel time from node $i$ to $j$, and $T_{ii}=0$.

\begin{align} \min&\quad\sum_{i,j\in I, i\neq j}T_{ij} x_{ij}\tag1 \\\text{s.t.}&\quad\sum_{i\in I, i\neq j}x_{ij} = 1 \quad \forall j\in I\setminus\{0\}\tag2 \\&\quad\sum_{j\in I, i\neq j}x_{ij} = 1 \quad \forall i\in I\setminus\{0\}\tag3 \\&\quad\sum_{i\in I\setminus\{0\}}x_{0i} = m\tag4 \\&\quad\sum_{i\in I\setminus\{0\}}x_{i0} = m\tag5 \\&\quad\sum_{j\in I,i\neq j}z_{ij}-\sum_{j\in I,i\neq j}z_{ji}-\sum_{j\in I,i\neq j}\left(T_{ij}-s_j\right)x_{ij} = 0 \quad \forall i \in I\setminus\{0\}\tag6 \\&\quad z_{ij} \leq (U-T_{j0})x_{ij} \quad \forall i\in I,j\in I\setminus{\{0\}}, i\neq j\tag7 \\&\quad z_{i0} \leq U x_{i0} \quad \forall i\in I \setminus{\{0\}}\tag8 \\&\quad z_{ij} \geq (T_{ij}+T_{0i}+s_j)x_{ij} \quad \forall i\in I\setminus{\{0\}},j\in I, i\neq j\tag9 \\&\quad z_{0i} = T_{0i}x_{0i} \quad \forall i\in I\setminus{\{0\}}\tag{10} \\&\quad x_{ij} \in \{0,1\}, z_{ij} \in \mathbb{R}_{\geq 0}, m\in \mathbb{Z}_{\geq 0} \end{align}

Next, I want to constrain the number of packages each truck can deliver. Say, we have a capacity of $K$ packages for each truck, and $P_j$ is the number of packages to deliver at each node. How can I incorporate these constraints?

---

_Reference

_{[1] Almoustafa, S., Hanafi, S., Mladenović, N. (2013). New exact method for large asymmetric distance-constrained vehicle routing problem. European Journal of Operational Research. 226(3):386-394.}

Answer 1

@JorisKinable uses the MTZ-like constraints to ensure the capacities on the vehicles are respected. Unfortunately, this formulation is known to be (very) weak, and you will probably not be able to solve any large instances.

I would suggest to use a network flow based formulation, akin to the formulation you already have to keep track of the time consumption. To that end, introduce a new variable, $f_{ij}$ for each arc $(i,j)$ in the graph. This variable is defined as follows: if $x_{ij}=1$ then $f_{ij}$ denotes the amount of goods (number of packages) delivered on the route to customer $i$ when the vehicle leaves customer $i$. Otherwise, $f_{ij}=0$.

To ensure that the $f_{ij}$ variables follow this definition, you should introduce the following sets of constraints \begin{align} &f_{ij} \leq Kx_{ij}&&\forall i,j\in I:i\neq j\\ &f_{ij}\geq 0,&& \forall i,j\in I:i\neq j\\ &\sum_{j \in I}f_{ij}=\sum_{j\in I}f_{ji}+P_i,&&\forall i\in I\setminus\{0\} \end{align} The first set of constraints ensure that $f_{ij}=0$ when $x_{ij}=0$ and that the number of packages delivered on a tour does not exceed the capacity of the vehicle when $x_{ij}=1$ ($f_{ij}\leq K$). The second set enforces the non-negativity and finally the last set of constraints say that the number of packages delivered when leaving node $i$ must equal the number of packages delivered when entering node $i$ plus those packages delivered at $i$. This must hold for all customer nodes.

It is fairly easy to show, that this formulations is stronger than the MTZ formulation. The formulation can be strengthened by tightening the first and second set of constraints as follows \begin{align} &f_{ij} \leq (K-P_j)x_{ij}&&\forall i,j\in I:i\neq j\\ &f_{ij}\geq P_ix_{ij},&& \forall i,j\in I:i\neq j\\ \end{align} With this strengtening, the formulation produces the same bound as when you exactly separate all Generalize Large Multi-star inequalities, meaning this formulation, although not the strongest, actually performs OK bound-wise.

Answer 2

Define a directed graph $G(V,A)$, where $V=\{0,1,2,\dots,n,n+1\}$, where $0$ and $n+1$ are the starting and ending depot of the vehicles (these depots are typically the same physical depots, but duplicating the depot makes modelling easier). Let $V'=\{1,2,\dots,n\}$ be the set of customers. Then arc set $A$ is defined as $A\subseteq \{0\}\times V'\ \cup V'\times V' \cup V'\times \{n+1\}$. Note that the starting depot $0$ has only outgoing arcs, and the ending depot $n+1$ has only incoming arcs.

Parameters:

• $t_{ij}$: parameter defining the travel time from $i$ to $j$
• $s_j$: service time of node $j$, with $s_0=s_{n+1}=0$
• $m$: number of allowed vehicles
• $\overline{Q}$: truck capacity
• $q_i$: demand of node $i$, with $q_0=q_{n+1}=0$
• $\overline{T}$: maximum travel time

Decision variables:

• $x_{ij}$: Binary variable determining whether arc $(i,j)$ is used by some vehicle
• $Q_i$: Residual capacity of the vehicle serving node $j$
• $T_i$: Departure time of the vehicle servicing node $j$

Model: \begin{align} \mbox{minimize}~& \;\sum_{(i,j)\in A}t_{ij}x_{ij}& \\ \mbox{s.t. } &\sum_{(0,j)\in A}x_{0j}=m & \\ % use m vehicles &\sum_{(j,i)\in A}x_{ji}=1 & \forall i\in V'\\ %every customer must be visited by exactly 1 vehicle &\sum_{(i,j)\in A}x_{ij}=1 & \forall i\in V'\\ % leave every visited node &T_j\geq(T_i+t_{ij}+s_j)-\overline{T}(1-x_{ij}) & \forall (i,j)\in A\\ &Q_j\geq(Q_i+q_j)-\overline{Q}(1-x_{ij}) & \forall (i,j)\in A\\ & x_{ij} \in \{0,1\} & \forall (i,j)\in A\\ & T_0=0 & \\ & 0\leq T_i\leq \overline{T} & \forall i\in V\\ & Q_0=0 & \\ & 0\leq Q_i\leq \overline{Q} & \forall i\in V \end{align}

The first 3 constraints resp. ensure that (1) $m$ vehicles leave the starting depot, (2) every customer is visited by exactly 1 vehicle, (3) exactly one vehicle leaves the customer. The 4th and 5th constraint take care of the vehicle departure times and vehicle capacities. As per example, for the vehicle capacity constraints: If a vehicle travels arc $(i,j)$, then its capacity at node $j$ equals its capacity at node $i$, plus the quantity it picked up at $j$. Similarly, for the departure times: if a vehicle traverses arc $(i,j)$, then its departure time at $j$ equals its departure time at $i$ plus the travel time from $i$ to $j$, plus the service time at $j$.