New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization (Q1602710)

The following minimum cost connected multi-digraph problem with node-deficiency requirements ({MCNDP}) is considered: The input is a digraph~\(D=(V,E\uplus F)\) (with \(E\cap F=\varnothing\)) a cost function \(c : E\cup F\rightarrow\mathbb{Q}\) with \(c(f)=0\) for all \(f\in F\), and a {\text{node-deficiency function}} \(d : V\rightarrow\mathbb{Z}\) with \(\sum_{i\in V} d(v)=0\) and \(d(s)=0\) for all \(s\in S\), where~\(S\) is the set of those nodes that are not incident to any arc from~\(F\). The goal is to find a minimum cost multi-digraph~\(D^{\star}\) on a node set \(V^{\star}\subseteq V\) with arcs in \(E\cup F\) such that \(D^{\star}\) is connected, each arc from~\(F\) is contained in~\(D^{\star}\) with multiplicity one, and for each node~\(v\in V^{\star}\) the difference between the out-degree and the in-degree of~\(v\) in~\(D^{\star}\) equals~\(d(v)\). The special case with \(d(v)=0\) for all \(v\in V\) is well-known as the Rural Postman Problem (RPP), which is polynomially equivalent to the Traveling Salesman Problem (TSP). Motivated by a special case of the TSP treated by \textit{P. Gilmore} and \textit{R. Gomory} [Oper. Res. 12, 655-679 (1964; Zbl 0126.36006)], the authors consider the special case of the MCNDP, where \(D\) is a bi-directed path. For this special case, they describe a polynomial time algorithm that is an adaption of an algorithm for Gilmore and Gomory's special case of the TSP due to \textit{M.-O. Ball} and \textit{M. J. Magazine} [Sequencing of insertions in printed circuit board assembly, Oper. Res. 36, 192-201 (1988)]. Generalizing this special case of the MCNDP and modifying the original algorithm the authors obtain polynomial time algorithms for several other special cases of the MCNDP, including the wallpaper cutting problem and the warehouse order-picking problem.