0
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ You are essentially doing combinatorial Benders decomposition with "no-good" feasibility cuts, and the resulting DCVRP subproblem is difficult. You might be better off changing the master problem to determine not just which nodes are visited but which nodes are visited by which vehicles. The subproblem then decomposes into identical subproblems (one per vehicle), each of which is easier and yields stronger feasibility cuts (that can also be shared by all vehicles in the master problem). $\endgroup$
    – RobPratt
    Jul 26 at 1:07
  • $\begingroup$ @RobPratt Thanks for the answer. Yes, you are right. I was thinking of considering a variable w_{ij}, to express whether the node i is placed in the route j, in the K(V) program, like a bin packing fashion. Thence, the subproblem now becomes to determine whether there exist a tour of length at most T that visits all the nodes allocated to the route (bin) j, that is, find a tour that services all the nodes in {i \in V: w_{ij} = 1} and has time consumption at most T. Is that what do you mean? Thank you and regards. $\endgroup$ Jul 26 at 1:35
  • 1
    $\begingroup$ Yes, and for that one-vehicle subproblem, you need "only" solve a TSP. I did something similar in this paper. $\endgroup$
    – RobPratt
    Jul 26 at 1:39
  • 1
    $\begingroup$ Two implementation details that should reduce the run time: 1. If a TSP subproblem yields an optimal value $>T$, that yields a feasibility cut, but you can look for a minimal such cut by removing one node at a time until the TSP value is $\le T$. This idea often appears in "no-good" feasibility cuts. You want to identify a source of infeasibility that cuts off a set of solutions rather than just one solution. 2. The second idea is to apply any feasibility cuts to all bins in the master. Without doing this, the master is likely to return essentially the same solution many times. $\endgroup$
    – RobPratt
    Jul 26 at 3:32
  • 1
    $\begingroup$ I don't have any suggestions for GA, but neither master problem discussed so far (with $y_i$ or $w_{ij}$) determines the sequence of nodes. $\endgroup$
    – RobPratt
    Jul 26 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.