Modify the network model to accommodate multiple vehicles

Question

Given a directed network (or graph) $G = (V,E)$ with each edge $e_{ij}$ having a non-negative cost as the travel time from $i$ to $j$. Each node has an associated demand $d_i$. If the demand is positive, then that node is a pick-up node; if the demand is negative then that node is a delivery node. Furthermore, we have a source and a target node such that the source node always has non-negative demand. The model that I have made is to minimize the total travel time between the source and the target such that it visits all nodes, i.e satisfies all the demands and the truck does not arrive at a node before the earliest allowed time:

\begin{array}{lrclll} \min & \sum\limits_{i \in N} \sum\limits_{j \in N} {x_{i, j}} \cdot T_{i, j} &&&& \\ \mbox{s.t.} & \sum\limits_{j \in N \setminus \{i\}} x_{i, j} & = & 1 & \forall i \in N \setminus \{t\} & \\ & \sum\limits_{i \in N \setminus \{j\}} x_{i, j} & = & 1 & \forall j \in N \setminus \{s\} & \\\\ & \tau_i + T_{i, j} & \leq & \tau_j + (1 - x_{i, j})\cdot M_\text{arrival_time} & \forall (i, j) \in N \times N & \scriptstyle\\ & r_i & \leq & \tau_i & \forall i \in N & \\\\ & \ell_s & = & d_s && \\ & \ell_i + d_j & \leq& \ell_j + (1 - x_{i, j})\cdot M_\text{load} & \forall (i, j) \in N \times N & \\ & \ell_i + d_j & \geq& \ell_j - (1 - x_{i, j})\cdot M_\text{load} & \forall (i, j) \in N \times N & \\\\ & \tau_i & \geq & 0 & \forall i \in N & \\ & \ell_i & \geq & 0 & \forall i \in N & \\ & x_{i, j} & \in & \mathbb{B} & \forall (i, j) \in N \times N & \\ \end{array}

where $T_{i,j}$ is the travel time between $i$ and $j$ node, $x_{i,j} = 1$ if the edge $ij$ is chosen and $0$ otherwise, $\ell_i$ the load of the vehicle at $i$, $d_i$ the demand of a node, $\tau_i$ the arrival time at $i$, and $r_i$ the earliest allowed time for arrival at $i$. My question is how can I expand this model to accommodate for $k \geq 2$ vehicles with $k$ sources and targets?

EDIT: Assume that each node can not be visited by more than 1 vehicle and the source, target nodes are fixed. Also, assume that it does not matter which vehicle ends up in which locations so the $k$-th vehicle does not have to end up at $t_k$.

Answer 1

Let's use $K$ as the index set for sources and sinks (targets). We're assuming that each vehicle leaves a source, visits some nodes and lands at a sink, with each node (including sources and sinks) being visited by exactly one vehicle. I think the following model will work, with the caveat that some of the variable values will be nonsense and will need to be ignored.

We add a superscript $k$ to all the variables, indicating they belong to the $k$-th vehicle. We will denote the sources and sinks $s_k$ and $t_k$ ($k\in K$). Without loss of generality, we can assume that vehicle $k$ leaves $s_k$ and arrives at $t_k,$ since we can reindex the vehicles to match the source nodes and reindex the sink nodes to match the vehicles. Here is the modified model:

\begin{array}{lrclll} \min & \sum_{k\in K}\sum_{i\in N}\sum_{j\in N}x_{i,j}^{k}\cdot T_{i,j} & & & & (1)\\ \mbox{s.t.} & \sum_{j\in N\backslash\left\{ s_{k}\right\} }x_{s_{h},j}^{k} & = & \begin{cases} 1 & h=k\\ 0 & h\neq k \end{cases} & \forall h,k\in K & (2)\\ & \sum_{j\in N\backslash\left\{ t_{k}\right\} }x_{j,t_{h}}^{k} & = & \begin{cases} 1 & h=k\\ 0 & h\neq k \end{cases} & \forall h,k\in K & (3)\\ & \sum_{k\in K}\sum_{j\in N\backslash\left\{ i\right\} }x_{i,j}^{k} & = & 1 & \forall i\in N\setminus\bigcup\{s_{k},t_{k}\} & (4)\\ & \sum_{i\in N\backslash\left\{ j\right\} }x_{i,j}^{k} & = & \sum_{i\in N\backslash\left\{ j\right\} }x_{j,i}^{k} & \forall j\in N\setminus\bigcup\{s_{k},t_{k}\},\forall k\in K & (5)\\ \\ & \tau_{i}^{k}+T_{i,j} & \leq & \tau_{j}^{k}+(1-x_{i,j}^{k})\cdot M_{\text{arrival_time}} & \forall(i,j)\in N\times N,\forall k\in K & (6)\\ & r_{i} & \leq & \tau_{i}^{k} & \forall i\in N,\forall k\in K & (7)\\ \\ & \ell_{s_{h}}^{k} & = & \begin{cases} d_{s_{k}} & h=k\\ 0 & h\neq k \end{cases} & \forall j,k\in K & (8)\\ & \ell_{i}^{k}+d_{j} & \leq & \ell_{j}^{k}+(1-x_{i,j}^{k})\cdot M_{\text{load}} & \forall(i,j)\in N\times N,\forall k\in K & (9)\\ & \ell_{i}^{k}+d_{j}^{k} & \geq & \ell_{j}^{k}-(1-x_{i,j}^{k})\cdot M_{\text{load}} & \forall(i,j)\in N\times N,\forall k\in K & (10)\\ \\ & \tau_{i}^{k} & \geq & 0 & \forall i\in N,\forall k\in K & (11)\\ & \ell_{i}^{k} & \geq & 0 & \forall i\in N,\forall k\in K & (12)\\ & x_{i,j}^{k} & \in & \mathbb{B} & \forall(i,j)\in N\times N,\forall k\in K & (13) \end{array}

Objective (1) minimizes the combined travel time of all vehicles. Constraints (2) and (3) say that vehicle $k$ leaves source $s_k$ once and never leaves any other source, and enters sink $t_k$ once and never enters any other sink. Constraint (4) says that each intermediate node is entered exactly once, by a single vehicle. Constraint (5) says that each vehicle enters each intermediate node the same number of times that it exits that node. Combine that with (4), and you have one vehicle entering and exiting each intermediate node and the other vehicles bypassing the node.

Constraint (6) says that if a vehicle visits two nodes consecutively, the arrival time at the second node is at least the arrival time at the first node plus the transit time. Constraint (7) says that each vehicle's arrival time at each node cannot be earlier than the node's time window opening. Here is where thinks get slightly funky. If a vehicle does not visit a node, the solver is free to assign any "arrival time" greater than or equal to the window time for that vehicle at the node. So the solution will say that each vehicle has an arrival time at a given node, even though all but one of the vehicles bypassed that node. This should prove harmless. For the one vehicle that actually visits the node, the arrival time will respect transit times and time windows.

Similar, we will have "loads" for each vehicle at each node, regardless of whether the vehicle really visits the node. Constraint (8) says that the load of any vehicle at any source node is the actual load there if the source node is the right one for the vehicle and 0 otherwise. Constraints (9) and (10) say that if a vehicle visits two nodes consecutively, the load changes correctly.

If the phantom arrival times and loads are too disconcerting, another approach would be to add binary variables for each combination of vehicle and node, indicating whether that vehicle visits that node, and weave them into the formulation.