Asymmetric time-constrained capacitated vehicle routing problem

I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (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.

• What is $m$ and $z_{ij}$? Do you want to cap both the travel time and capacity of the packages? In that situation, I think only one set of constraints related either to package capacity or related to travel time will be binding constraints. That's why I cannot see the point of having both sets at the same time. Can you explain more? Commented May 11, 2021 at 17:07
• Oguz, m is the number of vehicles, and z is the time of travel from i to j (as far as I understand from the reference). Though I now consider m a variable, it is fine to assume constant. In the network, there are so many demand locations, and I aggregate them based on some application-specific logic. So, each node represents delivery of several packages. I would like to cap the travel time + an overhead (depending on how many packages the node represents) time for the tour of a vehicle. Meanwhile, I want to make sure the number of points stopped by a vehicle is less than a fixed value. Commented May 11, 2021 at 17:49
• Is it any more clear, Oguz? I can think of addressing these with a three index reformulation (v,i,j) assuming m as fixed, where v would be the vehicle label. But, two-index seems much better. So, pushing the boundaries :) Commented May 11, 2021 at 18:23
• This seems fairly straightforward to implement with or tools with 3 resources: time, load, stops. Commented May 11, 2021 at 21:05
• Fair enough :) its me indeed. And yes, with VRPy, this is also straightforward. Please let me know if you run into any trouble or need any help. The feedback I've had so far is that vrpy is much more user friendly. But as or tools is older and has proven its performances, it may be the safer alternative. I would be interested to see how both compare. If you think it's worth it, I would be happy to post the use case with VRPy as an answer. Commented May 13, 2021 at 11:56

@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.

• Sune, I really like your answer, and accepted is as the answer because it really answers what I asked for, i.e., "how can I incorporate these constraints." I have two follow-up questions though. 1) what is $V$ in your third constraint? 2) Can you please confirm if I added $s_j$ parameters to the right places? Commented May 12, 2021 at 16:01
• 1) it’s a typo. I Will correct this. 2) I would expect you to add $s_j$ in (6) instead of subtracting it. And using the same logic as with the the capacity constraints in my answer, I would expect you to add $s_i$ not $s_j$
– Sune
Commented May 12, 2021 at 16:25
• Minus in (6) was a typo, but I thought I should subtract $s_j$. That is a correction needs to be made to (6) and (9). Do you see it going into any other constraints? Am I missing anything? Commented May 12, 2021 at 18:02

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

• Looks like your descriptions of the 2nd and 3rd constraints are reversed. Also, I suspect the OP wants a linear formulation with (lifted) MTZ constraints instead of your 4th and 5th constraints. Commented May 11, 2021 at 21:35
• @RobPratt edited the answer: linearized constraints 4 and 5. Commented May 11, 2021 at 21:38
• Those changes look good. You could strengthen 4 by lifting with $\alpha_{ji} x_{ji}$ on the RHS and strengthen 5 by lifting with $\beta_{ji} x_{ji}$ on the RHS. Commented May 11, 2021 at 21:44
• Thank you so much for writing a very clear formulation. Though I can understand all the constraints, I am still lost in how these capacity and time constraints are tracked at the vehicle level. Two index formulation seems magical to me! Commented May 12, 2021 at 7:56
• I guess, now, I understand better. Since only one vehicle can stop by a node, the time and capacity are tracked correctly. Commented May 12, 2021 at 8:30