On the windy postman problem
The windy postman problem (WPP) is: find a shortest postman route in a connected undirected graph G(V,E), such that for every edge (x,y) the distance from x to y can be different from the distance from y to x. The author proves that WPP is NP-hard. Further, the WPP is restated as follows: let \(G_ 1(V,A)\) be a symmetric directed graph, where for every edge \(e=(x,y)\) in E there are two arcs \(a'=(x,y)\) and \(a=(y,x)\) in A with a non-negative length \(\ell (a')\) and \(\ell(a)\). The problem is to find a shortest directed closed path p in \(G_ 1\), such that for every \(e\in E\) at least a' or a belong to p. A polynomial bounded algorithm is given for solving WPP if the following condition Q is fulfilled: for every cycle C in G the corresponding cycles C' and C obtained from C with the two possible directions have the same length, i.e. \(\ell(C')=\ell(C).\) Theorem 3 makes the procedure proving condition Q simpler. The author considers also the case when condition Q is nearly satisfied. G satisfies condition \(Q_ 1\), if for any cycle C in G and any edge \(e\in C\), \(| \ell(C')-\ell(C)| <\ell(a')+\ell(a).\) Theorem 5. If there exists a real number \(\epsilon\geq 0\) and a spanning tree T of G, such that (a) for every fundamental cycle \(C_ i\), \(| \ell (C'_ i)-\ell (C_ i)| \leq \epsilon /s\) (s is the cyclomatic number of G), (b) for every edge e of G, \(\ell(a')+\ell(a)>\epsilon\), then condition \(Q_ 1\) is satisfied. If G satisfies conditions (a) and (b) of Theorem 5, a polynomial bounded algorithm \((\bar A)\) is given for solving WPP approximately. Theorem 6. Let \(p_ 1\) be the shortest postman route of the WPP on G, and p be the postman route obtained by algorithm \(\bar A.\) Then \(| \ell (p_ 1)\)-\(\ell (p)| <s\epsilon\) (s and \(\epsilon\) are meant as in Theorem 5).
- New results on the windy postman problem
- Algorithms for the windy postman problem
- On the windy postman problem on Eulerian graphs
- The windy rural postman problem with a time-dependent zigzag option
- A cutting plane algorithm for the windy postman problem
- The windy postman problem on series-parallel graphs
- Plowing with precedence: a variant of the windy postman problem
- Lower bounds and heuristics for the windy rural postman problem
- New heuristic algorithms for the windy rural postman problem
- Tight bounds on the spectral radius of asymmetric nonnegative matrices
- On the windy postman problem on Eulerian graphs
- A cutting plane algorithm for the windy postman problem
- Algorithms for the windy postman problem
- Solvable cases of the \(k\)-person Chinese postman problem
- Routing problems: A bibliography
- Postman problems on series-parallel mixed graphs
- New heuristic algorithms for the windy rural postman problem
- New results on the windy postman problem
- Series-parallel graphs are windy postman perfect
- Solution of real-world postman problems
- Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems
- Approximation algorithms for a mixed postman problem with restrictions on the arcs
- The windy postman problem on series-parallel graphs
- scientific article; zbMATH DE number 1305467 (Why is no real title available?)
- scientific article; zbMATH DE number 1833401 (Why is no real title available?)
- scientific article; zbMATH DE number 4185647 (Why is no real title available?)
- Plowing with precedence in polynomial time
- The single robot line coverage problem: Theory, algorithms, and experiments
- On the windy k-traveling salesman problem
- Uncertain multi-objective Chinese postman problem
- Lower bounds and heuristics for the windy rural postman problem
This page was built for publication: On the windy postman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800837)
