On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

We show that any instance of TMO has an optimal solution in which any two trains either travel along the same path (with sufficient temporal distance), or follow disjoint paths (Theorem 2 in Section 2). We call such solutions convoy routings. In particular, convoy routings have a compact representation that is polynomial in the size of the input, even when the number of trains is exponential in the size of the network. A further consequence is that allowing trains to wait at intermediate nodes does not help to improve the optimal solution value. The proof of this result relies on an uncrossing algorithm that takes an arbitrary train routing and modifies it to ensure that any train that is the first to traverse the final arc of its path is also the first to traverse any other arc it uses. Conflicts, i.e., situations where this property is violated, are resolved iteratively, starting with those closest to the sink, with a potential function argument ensuring eventual termination of the procedure.

We further provide a simple flow-based approximation algorithm for TMO that returns a convoy routing whose makespan is bounded by $\mathrm{OPT}+\mathrm{\Delta }$ (Theorem 4 in Section 3). This result is achieved by solving an appropriately defined quickest flow over time problem in the underlying network. Note that in practice, the headway $\mathrm{\Delta }$ is typically much smaller than the total transit time of a train from source to sink, and hence the additive error $\mathrm{\Delta }$ is small compared to $\mathrm{OPT}$.

Building on the previous two results, we establish a strong connection between MinMaxDP and TMO by showing that any $\alpha$-approximation algorithm for MinMaxDP yields a $\max \{1+\epsilon ,\alpha \}$-approximation algorithm for TMO with polynomial runtime in the size of the input and $\frac{1}{\epsilon }$ (Theorem 5 in Section 4). To achieve this result, we devise a gadget that encodes the choices on the number of trains on each path of a convoy routing into the routing decisions in the network. The size of this gadget is polynomial in the size of the original network and $d$. It thus provides an exact reduction of TMO to MinMaxDP when the number of trains $d$ is polynomial in the size of the network. When $d$ is large, on the other hand, there must be an arc traversed by a large number of trains and hence $\mathrm{OPT}$ is much larger than $\mathrm{\Delta }$. In this case, the additive guarantee of $\mathrm{OPT}+\mathrm{\Delta }$ of our flow-based algorithm for TMO mentioned above translates to a $(1+\epsilon )$-approximation. As we mentioned previously, for sufficiently large values of $\mathrm{\Delta }$, TMO coincides with MinMaxDP. Thus, finding good approximation algorithms for MinMaxDP is not only sufficient but also necessary to obtain good approximations for TMO.

In the remainder of this paper, we therefore focus on approximation algorithms for MinMaxDP. We show that a natural greedy approach achieves an approximation which is logarithmic in $k$ on series-parallel (SePa) networks (Theorem 8 in Section 5), where $k$ is the number of paths to be constructed. This constitutes the first non-trivial approximation result for MinMaxDP going beyond the aforementioned PTAS for bundle graphs [9], without assuming that either $k$ or the number of layers of the graph is constant.

We prove the approximation guarantee via induction on a series-parallel decomposition of the graph. The key ingredient is showing that the greedy algorithm maintains a solution fulfilling a strong balance condition on the path lengths. Additionally, we provide an alternative analysis of the same approach that yields an upper bound of $\phi (D)+1$ on the approximation factor, where $\phi (D)$ denotes the number of changes from series to parallel composition on a root-leaf path in the binary tree describing the SePa-graph. To the best of our knowledge, the parameter $\phi (D)$, which we demonstrate to be independent of the choice of the decomposition tree, has not been used in the literature before. We believe that this natural parameter can be of independent interest for designing and analysing algorithms for other problems in SePa-graphs. Our alternative analysis implies the classic greedy $2$-approximation for bundle graphs by Hsu [17] as a special case. By the aforementioned reduction of TMO to MinMaxDP, the approximation results for MinMaxDP on SePa-graphs, translate to our train routing problem.

We prove this using a potential function. To define this function, we extend the definition of $a_y^{tr}$ to arbitrary, i.e., also non-leader trains, $y$. Informally, $a_y^{tr}$ is the last arc on train $y$’s path after which the set (or order) of trains driving before $y$ changes.

The potential of a train $y$ is the number of arcs of $P_y$ from $s$ to $a_y^{tr}$. We prove the following two statements: (i) When resolving a conflict for some leader $x$, we decrease its potential, (ii) The potential of all other trains does not increase when resolving a conflict of $x$. Together, (i) and (ii) imply that the sum of all potentials decreases in every iteration of the uncrossing phase, implying finite termination of this phase and thus of the entire algorithm. The proof of (i) and (ii) involves a careful analysis, which reveals that the transition node of a train is always on its path in the original routing, and a case distinction of possible configurations arising in the uncrossing steps. The details of this analysis can be found in the full version of this article [1, Appendix B]. $◀$

Let $D^{\prime }$ and $D^{\prime \prime }$ be two SePa-graphs, and let ${𝑷}^{\prime }$ and ${𝑷}^{\prime \prime }$ be path profiles of $D^{\prime }$ and $D^{\prime \prime }$ consisting of $k^{\prime }$ and $k^{\prime \prime }$ arc-disjoint paths, respectively. For a series composition $D=D^{\prime }{\odot }_s{D}^{\prime \prime }$, if $k^{\prime }=k^{\prime \prime }$, the greedy composition of $𝑷$ and ${𝑷}^{\prime }$ is the path profile $𝑷={𝑷}^{\prime }{\odot }_s{𝑷}^{\prime \prime }$ of $D$ that is derived by combining the longest path in ${𝑷}^{\prime }$ with the shortest path in ${𝑷}^{\prime \prime }$, the second-longest path in ${𝑷}^{\prime }$ with the second-shortest path in ${𝑷}^{\prime \prime }$, and so on. Note that this construction is only defined for $k^{\prime }=k^{\prime \prime }.$ For a parallel composition $D=D^{\prime }{\odot }_p{D}^{\prime \prime }$, the greedy composition is given by $𝑷={𝑷}^{\prime }{\odot }_p{𝑷}^{\prime \prime }$ of $D$, where $𝑷$ simply consists of the union of the $k^{\prime }+k^{\prime \prime }$ paths in ${𝑷}^{\prime }$ and ${𝑷}^{\prime \prime }$.

We now discuss three properties that are maintained by the greedy composition procedure described above if they are fulfilled by the path profiles that are being combined. To define these properties, we fix an arbitrary optimal path profile ${𝑷}^{\ast }$ in the graph $D$ that defines our MinMaxDP instance. The first property we consider is consistency.

We call a path-profile $𝑷$ consistent with ${𝑷}^{\ast }$ in $D^{\prime }⊑D$ if $𝑷$ and ${𝑷}^{\ast }$ use the same number of paths in $D^{\prime }$ and if

Note that consistency is maintained by greedy composition, as the arcs used by the disjoint paths in the composed profile are exactly the union of the paths in the two profiles that are being combined. We now define the second property, balancedness, and show that together with consistency it implies the first of our two approximation bounds.

Let $𝑷$ be a path profile, and let $D^{\prime }⊑D$ be traversed by $k^{\prime }\le k$ paths from $𝑷$. Let $p_1\ge \mathrm{\dots }\ge p_{k^{\prime }}$ be the lengths of those paths in $D^{\prime }$. Then $𝑷$ is balanced in $D^{\prime }$ if

We first establish that balancedness – when combined with consistency – is indeed maintained by greedy composition. While this is straightforward for parallel composition, the proof for series composition requires a more involved analysis that carefully combines (1) and (2). The details of this analysis are given in the full version of this article [1, Appendix F.1].

Crucially, the following lemma reveals that if the final solution is balanced and consistent with ${𝑷}^{\ast }$, it is a logarithmic approximation for the latter. The lemma follows from an averaging argument over (2) for $i\in [k-1]$, which can be found in the full version of this article [1, Appendix F.2].

We now introduce the third property, $\phi$-boundedness, which is likewise maintained by greedy composition and implies the second bound on the approximation guarantee when fulfilled by the final solution.

We call a path profile $𝑷$ $\phi$-bounded in $D^{\prime }⊑D$ if

Note that in this definition, the left-hand side refers to the length of the longest path of $𝑷$ in the subgraph $D^{\prime }⊑D$, whereas the right-hand side refers to the optimal objective value for MinMaxDP on the entire graph $D$. The following lemma establishes that consistency and $\phi$-boundedness are maintained by the greedy composition when executing all compositions that correspond to one component of the decomposition tree.

The proof of this lemma involves an induction over the components of the decomposition tree of $D$ and can be found in the full version of this article [1, Appendix F.3].

In the following, we show how to resolve this issue by means of two dynamic programs. In both cases, our dynamic programming table will have the following attributes per cell:

• $\mathrm{■}$

  a subgraph $D^{\prime }⊑D$,

• $\mathrm{■}$

  the number of paths $k^{\prime }\in [k]$ used in $D^{\prime }$,

• $\mathrm{■}$

  the total length ${\theta }^{\prime }\in \mathrm{\Theta }$ of the path profile in $D^{\prime }$.

Recall that the total length of a path profile $𝑷$ in subgraph $D^{\prime }$ was defined as the sum of the lengths of the paths in $D^{\prime }$, i.e., $\theta (𝑷,D^{\prime })≔{\sum }_{P\in 𝑷}{\sum }_{a\in A[D^{\prime }]\cap P}{\tau }_a$. We let $\mathrm{\Theta }$ denote the set containing all possible values that might appear as total costs.

To fill the cells of the dynamic programming table, we start with the subgraphs consisting of single arcs, i.e., $D^{\prime }=(\{v,w\},\{a=(v,w)\})$. Here, the non-empty entries of the table corresponding to $D^{\prime }$ are $(D^{\prime },1,{\tau }_a)=\{(a)\}$ and $(D^{\prime },0,0)=\{\mathrm{\varnothing }\}$, while all remaining entries corresponding to $D^{\prime }$ are empty (which is different from containing an empty path profile).

Given a cell $(D^{\prime }\odot D^{\prime \prime },\tilde{k},\tilde{\theta })$, we combine all path profiles ${𝑷}^{\prime }$ and ${𝑷}^{\prime \prime }$ of $D^{\prime }$ and $D^{\prime \prime }$ consisting of $k^{\prime }$ and $k^{\prime \prime }$ paths of total length ${\theta }^{\prime }$ and ${\theta }^{\prime \prime }$, respectively, if and only if $\tilde{\theta }={\theta }^{\prime }+{\theta }^{\prime \prime }$ and $\tilde{k}=k^{\prime }+k^{\prime \prime }$ (in case of a parallel composition), or $\tilde{k}=k^{\prime }=k^{\prime \prime }$ (in case of a series composition). We build path profiles for $D^{\prime }\odot D^{\prime \prime }$ according to the greedy composition of the path profiles for $D^{\prime }$ and $D^{\prime \prime }$ as described above.

With this procedure, we obtain multiple candidates for a path profile in table entry $(D^{\prime }\odot D^{\prime \prime },\tilde{k},\tilde{\theta })$. Below, we analyse two different strategies to pick a good candidate that lead to different approximation guarantees. After filling the complete table of the dynamic program, there is a path profile ${𝑷}_{\theta }$ with $k$ paths in $D$ for each possible total-cost value $\theta \in \mathrm{\Theta }$. In the last step, the algorithm will choose the path profile for which the longest path is as short as possible, i.e. the algorithm chooses $\arg {\min }_{\theta \in \mathrm{\Theta }}{C}_{\max }({𝑷}_{\theta },D)$.

Our first strategy for selecting the candidates for the intermediate steps aims for balancedness of the solutions and is formalised in the following lemma, that reveals that the strategy yields an $H_k$-approximation.

The proof of this lemma is by induction on the table entries of the optimal solution and by using Lemma 9 to show that we always have a balanced candidate. Together with the choice (4), the lemma follows. A formal proof can be found in the full version of this article [1, Appendix F.4].

Our second candidate selection strategy aims at $\phi$-boundedness of the intermediate solutions. This is formalised in the following lemma, which shows that this strategy yields a $(\phi (D)+1)$-approximation.

Similarly to the proof of Lemma 13 we follow the table entries of an optimal solution. However, here we need to consider a component of the decomposition tree of $D$ at once and show that the entries for the subgraphs corresponding to segment roots are $\phi$-bounded. The formal proof of this lemma can be found in the full version of this article [1, Appendix F.5].

From the size of the dynamic programming table, we can obtain the bound on its running time formalised in the lemma below. By a standard rounding approach, we can further ensure that the number of possible total-cost values $|\mathrm{\Theta }|$ is polynomial in the size of the graph at a loss of a $(1+\epsilon )$-factor in the approximation ratio, obtaining the desired polynomial running time; see the full version of this article [1, Appendix F.6] for details.