How to partition a giant tour into feasible routes?

In vehicle routing problems, the route first cluster second approach starts by computing a "giant" TSP tour (which typically does not satisfy all constraints of the problem), and then transforms this tour into smaller feasible ones (see for example this paper).

I am wondering if it is possible to apply the same strategy for arc routing problems. A trial and error approach is described here for the CPP, but it is not very satisfying.

Could we formulate a MIP to partition a "giant" eulerian tour into $$k$$ subtours (with, for example, a maximum length) ? Or is there another smart way of achieving this?

An example is illustrated below:

2 Answers

Here’s a MILP formulation to partition an Eulerian graph into $$K$$ Eulerian subgraphs, with an objective of minimizing the maximum cost. Let binary decision variable $$x_{ijk}$$ indicate whether edge $$(i,j)$$ appears in subgraph $$k$$, let $$y_{vk}$$ be a nonnegative integer decision variable for each node $$v$$ and subgraph $$k$$, and let decision variable $$z$$ represent $$\max_k \sum_{i,j} c_{ij}x_{ijk}$$. The problem is to minimize $$z$$ subject to contiguity constraints and \begin{align} \sum_k x_{ijk} &= 1 &&\text{for all (i,j)} \tag1\label1 \\ \sum_{(i,j):v \in \{i,j\}} x_{ijk} &= 2y_{vk} &&\text{for all v and k} \tag2\label2 \\ \sum_{i,j} c_{ij}x_{ijk} &\le z &&\text{for all k} \tag3\label3 \end{align} Constraint \eqref{1} assigns each edge to exactly one subgraph. Constraint \eqref{2} forces every node to have even degree in subgraph $$k$$. Constraint \eqref{3} enforces the minimax objective.

Here's a flow-based approach to enforce contiguity of subgraph $$k$$. Let binary decision variable $$w_{ik}$$ indicate whether node $$i$$ appears in subgraph $$k$$. Let binary decision variable $$s_{ik}$$ indicate whether node $$i$$ is the source node for subgraph $$k$$. Let nonnegative variable $$f_{ijk}$$ be the flow of "commodity" $$k$$ from node $$i$$ to node $$j$$. The following constraints select one source for each $$k$$ and send one unit of flow from that source to all other nodes in subgraph $$k$$: \begin{align} \sum_i s_{ik} &= 1 &&\text{for all k} \\ s_{ik} &\le w_{ik} &&\text{for all i and k} \\ w_{ik} \le y_{ik} &\le \frac{\text{degree}_i}{2} w_{ik} &&\text{for all i and k} \\ f_{ijk} + f_{jik} &\le n x_{ijk} &&\text{for all (i,j) and k} \\ \sum_j (f_{ijk} - f_{jik}) &\le n s_{ik} - w_{ik} &&\text{for all i and k} \\ \end{align}

Without the contiguity constraints, the optimal objective value for the example instance with $$K=3$$ is $$1290$$, attained by the following subgraphs with weights $$1290$$, $$1270$$, and $$1240$$:

C D 120
C I 250
D I 300
E F  80
E H 260
F G 100
G H 180

A B 120
A C 150
B D 150
C D 120
D E 150
D J 250
E K 250
J K  80

I J 120
I J 120
K L 150
K L 150
F G 100
F L 250
G M 250
L M 100


With the contiguity constraints also imposed, the example solution in the question is optimal, with objective value $$1320$$.

• Note that this formulation allows empty subgraphs or up to $K$ nonempty subgraphs. If you want exactly $K$ nonempty, impose an additional constraint $\sum_{i,j} x_{ijk} \ge 2$ for all $k$. Commented Jan 21, 2023 at 20:54
• Are you sure that the contiguity constraints are valid? In particular, what prevents the model from creating non contiguous subtours where each node has even degree? For example, in the illustration in the question, we could have the cycle $K-L-K$ assigned to the same subgraph as $A-B-D-I-C-D-C-A$ (so two non contiguous subgraphs with same index $k$)? Commented Jan 21, 2023 at 21:21
• The contiguity constraints are in addition to (1)-(3). Commented Jan 21, 2023 at 21:40
• I see :). For the sake of completeness, may I ask how such constraints can be written explicitely? Commented Jan 21, 2023 at 21:43
• @RobPratt, would you please, give an example of how the first formulation works? Commented Jan 22, 2023 at 19:37

Here is an alternative to RobPratt's precise solution.

First, compute all simple cycles of the graph $$G=(V,A)$$ (the graph can be directed in an arbitrary direction). Then, compute $$2$$-cycles and $$3$$-cycles, by merging cycles together if they share at least one common vertex (hence guaranteeing contiguity constraints). Let $$\Omega$$ be the set of all these cycles. The cost of cycle $$k$$ is denoted by $$C_k$$.

These cycles are now the variables of the problem, let $$x_k \in \{0,1\}$$ be a binary variable that takes value $$1$$ if and only if cycle $$k \in \Omega$$ is used in the solution. Let decision variable $$z$$ represent $$\max_k \; C_k x_k$$. The problem is to minimize $$z$$ subject to:

• Each edge must be covered exactly once by a given cycle: $$\sum_{k \in \Omega, (i,j)\in k}x_k =1\quad \forall (i,j) \in A$$
• $$z$$ is defined as the maximum length of the selected cycles: $$C_k x_k \le z \quad \forall k \in \Omega$$
• In our case, we can only use $$3$$ cycles: $$\sum_{k\in \Omega}x_k = 3$$

Some comments:

1. With the above formulation, I am able to find the optimal solution of the example in the question (in about 2 sec with CBC, and 0.1 sec with CPLEX). A simulation with some (non optimized) code can be found here.
2. The solution is not unique.
3. This is nothing more than a Dantzig-Wolfe decomposition of RobPratt's formulation. The contiguity constraints (and "even degree" constraints) are handled in a pre-processing phase, which makes the model a bit lighter.
4. However, in the general case, computing cycles up to $$3$$-cycles is not sufficient to guarantee that the optimal solution is reached.
5. One could compute the appropriate cycles dynamically with a column generation procedure (which would complicate the approach quite a bit) and either use branch-and-price (optimal), or solve the restricted master problem once all good columns have been found (heuristic).
• your approach is so interesting, and also thanks for sharing the method you used. Commented Jan 24, 2023 at 14:02