Check VRP instance is feasibility

Question

Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is feasible.

Now that you are aware of the risks. Let's go!

Before I describe my current problem, I will first detail in what context it will be applied. I am proposing a solution methodology for Team Orienteering Problems (TOPs). In this methodology, I am considering the problem as a knapsack problem variant. Let's define the notations of the TOP to substantiate the next results.

Problem definition:

Let:

• $D(V, A)$ be a digraph;
• $0 \in V$ be the depot node;
• $t_a \in \mathbb{R}$ be the arc $a \in A$ traversing time;
• $p_i \in \mathbb{R}$ be the node $i \in V$ profit, where $p_0 = 0$;
• $M$ be the available vehicles set;
• $T$ be each vehicle's time limit.

A feasible solution $S = \{R: R \text{ is a sequence of nodes in $V$ beginning and ending at the node $0$}\}$ for the TOP is a set of at most $|M|$ routes, such that every route respects the vehicle time limit $T$. An optimal solution $S^{*}$ for the TOP is a set of routes that maximizes the function $\sum_{i \in \bigcup_{R \in S} R} p_i$, i.e., the sum of the profits of all visited nodes where a profit is not counted more than once even if the solution visits a node twice or more. Note that, the routes, not necessarily, will have minimum time consumption, since it is not a problem's requirement.

Knapsack solution methodology:

Knowing that a route, not necessarily, will have minimum time consumption. I was thinking of solving this problem in two steps. First, finding the set of nodes that composes an optimal solution, using the constrained knapsack problem. And second, finding a Distance Constrained Capacitated VRP (DCVRP), a VRP variant where the only capacity is on the vehicle's time limit, feasible solution for the instance composed by the vehicle time limit $T$ and the digraph $D$ induced by the nodes found by the constrained knapsack problem. Specifically, I execute an unconstrained knapsack formulation,

$$K(V) = \text{max}_{y \in \mathbb{B}^{|V|}} \sum_{i \in V} y_i p_i$$

, and then I check whether there is a DCVRP feasible solution for the instance composed by the vehicle time limit $T$, and the digraph $D$ induced by the nodes used in $y^{*}$, where $y^{*}$ is the $K(V)$ optimal solution. Formally, the induced digraph can be defined as:

$$D^{'}(V^{'} = (\{i \in V : y^{*}_i = 1\} \cup \{0\}), \quad A^{'} = \{(i, j) \in A : i \in V^{'} \wedge j \in V^{'}\})$$

If the digraph $D^{'}$ along with $T$ results in a DCVRP feasible instance, then we have found the set of nodes that composes an optimal TOP solution for the TOP instance digraph $D$, otherwise, we add the following constraint to $K(V)$:

$$ \sum_{i \in V^{'}} y_i \leqslant |V^{'}| - 1 $$

And we execute $K(V)$ again, till we get a set of nodes $V^{'}$ that leads to a feasible DCVRP instance. Formally, consider the algorithm KnapDCVRP below:

1. Let $y^{*}$ be a $K(V)$ optimal solution;
2. Let $D^{'}(V^{'}, A^{'})$ be the induced digraph, built over $y^{*}$;
3. If $(T, D^{'})$ is a DCVRP feasible instance, then return $V^{'}$, and exit program;
4. Add to $K(V)$ the constraint $\sum_{i \in V^{'}} y_i \leqslant |V^{'}| - 1$;
5. Go to 1.

DCVRP feasibility checking:

In this methodology, the major problem I am facing concerns the algorithm KnapDCVRP's step 3, i.e. how to determine whether a DCVRP instance is feasible. To do this, I convert the $D^{'}$ digraph into a complete digraph $D^{''}(V^{'}, A^{''} = A^{'} \cup \{(i, j) \in V^{'2}: (i, j) \notin A^{'} \wedge i \neq j\})$, and I consider the time weights as

$$ t^{''}_{(i, j)} = \begin{cases} t_{(i, j)}, \quad \text{if } (i, j) \in A^{'}\\ \text{the shortest path time between nodes $i$ and $j$ in $D^{'}$}, \quad \text{otherwise} \end{cases} $$

for all $(i, j) \in A^{''}$. And then I execute the following MILP program:

$$ \sum_{a \in \delta^{+}(i)} x_a = \sum_{a \in \delta^{-}(i)} x_a = 1 \quad \forall i \in V^{'} \backslash \{0\} \quad (1) \\ \sum_{a \in \delta^{+}(0)} x_a = \sum_{a \in \delta^{-}(0)} x_a = |M| \quad (2) \\ \sum_{i \in V^{'} : i\neq j} u_{(j, i)} - u_{(i, j)} + x_{(i, j)} t^{''}_{(i, j)} = 0 \quad \forall j \in V^{'} \backslash \{0\} \quad (3) \\ u_{(0, i)} = 0 \quad \forall i \in V^{'} \backslash\{0\} \quad (4) \\ u_{(j, 0)} \geqslant x_{(j, 0)} t^{''}_{(0, j)} \quad \forall j \in V^{'} \backslash \{0\} \quad (5) \\ u_{(j, 0)} \leqslant x_{(j, 0)} (T - t^{''}_{(j, 0)}) \quad \forall j \in V^{'} \backslash \{0\} \quad (6) \\ u_{(i, j)} \geqslant x_{(i, j)} max\{t^{''}_{(depot, j)} - t^{''}_{(i, j)}, t^{''}_{(0, i)}\} \quad \forall (i, j) \in A^{''} : i, j \neq 0 \quad (7) \\ u_{(i, j)} \leqslant x_{(i, j)} min\{T - t^{''}_{(j, 0)} - t^{''}_{(i, j)}, T - t^{''}_{(i, depot)}\} \quad \forall (i, j) \in A^{''} : i, j \neq 0 \quad (8) \\ x \in \mathbb{B}^{|V^{'}|} \quad (9) \\ u \in \mathbb{R}^{A^{''}}_{+} \quad (10) $$

The constraints (1) and (2) are VRP's well known. Regarding the remaining ones, (3-10), are arc flow constraints to avoid subcycles disconnected from the depot, even in fractional solutions, and, at the same time, impose the vehicle's time limit constraint. I know they seem to be a little bit unusual since there's no big $M$ on it, but they were already used in another routing problem and had proven to be very efficient (look here at subsection 3.4 on page 10, and here at subsection 6.3 on page 50).

I have executed the MILP formulation (1-10) in the CPLEX solver using the following parameters configuration:

• CPX_PARAM_INTSOLLIM = 1 (Just find a feasible solution, if it exists);
• CPX_PARAM_MIPEMPHASIS = 1 (Emphasize feasibility over optimality);
• CPX_PARAM_VARSEL = -1 (Branch on variable with minimum infeasibility)

Note that the formulation (1-10) has no objective function and that the CPLEX chosen parameters are tuned to find integer feasible solutions, rather than optimizing. These choices were made since I just want to determine whether the DCVRP instance is feasible.

The problem regarding this procedure is that it is taking, relatively speaking, too long, about ~1 minute for 100 nodes, to check whether an instance is feasible. In this solution methodology, the algorithm KnapDCVRP's step 3 may be executed many times, even hundreds, thus, having a fast procedure to check the feasibility of a DCVRP instance can make a huge difference, depending on the instance size.

Therefore, I would like to know if there is any way of determining whether a DCVRP instance is feasible in a very fast time. I already tried to use the Google OR-Tools and Dynamic Programming approaches, but they are taking too much time, indeed they are slower than the (1-10) MILP formulation.

I know this is a very long thread, and the reader now may be thinking "well he could just have stated he needed some fast procedure to check a VRP instance feasibility", but I think it is important to make the context clear. If anyone has any questions or found any errors, please let me know.