Flow conservation constraints for an Open Vehicle Routing Problem

Question

I'm currently reviewing literature on the Open Vehicle Routing Problem (Open VRP), which characterizes scenarios where trucks do not return to the depot after serving the last customer. In this context, I've observed that several papers apply conventional flow conservation constraints as part of their formulations. For instance, the constraint $\sum_{i=0}^{n} x_{i j k}-\sum_{i=0}^{n} x_{j i k}=0, \quad j=0,1, \ldots, n, k=1, \ldots, \overline{k}$, which includes the depot as node '0', is used in this paper. Similar formulations can be seen in:

• Li, F., Golden, B., & Wasil, E. (2007). "The open vehicle routing problem: Algorithms, large-scale test problems, and computational results." Computers & Operations Research, 34(10), 2918-2930.
• Repoussis, P. P., Tarantilis, C. D., & Ioannou, G. (2007). "The open vehicle routing problem with time windows." Journal of the Operational Research Society, 58(3), 355-367.

These formulations don't appear to make a distinction for the final node visited by a truck, where logically, flow conservation doesn't apply due to the absence of an outbound trip.

Here is my personal take on formulating this aspect, assuming a set of nodes $N$ excluding the depot, and $N_0$ including the depot, with $x_{i,j,k}=1$ if and only if truck $k$ travels from node $i$ to node $j$:

1. Relax the flow conservation constraint for all nodes, except for the depot, using the $\ge$ inequality:

   $$ \sum_{j \in N_0, j \neq i} x_{j,i,k} \geq \sum_{j \in N, j \neq i} x_{i,j,k} \quad \forall i \in N, \forall k \in K $$

2. Ensure that for each vehicle $k$, exactly one node has a higher number of vehicles entering than leaving, indicating the terminating node. To represent this, I introduce a binary variable $t_{i,k}$, which is 1 if node $i$ is the terminating node for vehicle $k$:

   $$\sum_{i \in N} t_{i,k} = 1 \quad \forall k \in K $$

3. Connect the binary variables $t_{i,k}$ with the relaxed flow conservation constraint:

   $$\sum_{j \in N_0, j \neq i} x_{j,i,k} - \sum_{j \in N, j \neq i} x_{i,j,k} = t_{i,k} \quad \forall i \in N, \forall k \in K$$

Could there be an aspect I'm overlooking in the published models, or is there an explanation for the absence of explicit differentiation for the terminating node in these papers on Open VRP?

Answer 1

I'm not familiar with the published literature, but a simple fix is to create an artificial terminating node to which all vehicles must go, along with zero-length arcs from every node to the terminating node (but no arcs out of the terminating node). You enforce flow conservation everywhere except the origin depot and the terminating node.