<> "The repository administrator has not yet configured an RDF license."^^ . <> . . "Contributions to Multiple Postmen Problems"^^ . "In this dissertation we contribute to the optimal solution of multiple postmen problems, where the aim is to find a set of postman tours (each starting and ending at a post office) for k >= 2 postmen. We consider the Min-Max k-Chinese Postman Problem (MM k-CPP) where, given a street network, the objective is to cover each street by at least one postman tour while minimizing the length of the longest tour, and the Capacitated Arc Routing Problem (CARP) where the aim is to traverse a set of streets each having a certain service demand such that the total tour length is minimized and the sum of demands serviced by each postman does not exceed a given capacity. The CARP and the MM k-CPP are NP-hard. Therefore, the development of effective methods and algorithms for finding lower and upper bounds of high quality is essential for solving these problems to optimality (up to a certain order of magnitude). Based on a detailed review on existing lower bounding procedures for the CARP we develop an improved algorithm and confirm its effectiveness by computational experiments. We also reveal a new dominance relation between two existing lower bounding procedures formerly claimed to yield the same results. After a comprehensive discussion of IP formulations for the CARP and existing exact solution methods based on these formulations we contribute to these methods by devising an exact separation method for the aggregated capacity constraints, an important class of valid inequalities, which could formerly only be separated heuristically. We achieve new best lower bounds with a cutting plane algorithm incorporating this new separation method. For the MM k-CPP we present the only existing heuristic found in the literature. Then we develop two new heuristics, several new improvement procedures, and a tabu search algorithm incorporating these new methods. Computational experiments show that the tabu search algorithm achieves upper bounds of high quality which in many cases could be proven to be optimal. With respect to lower bounds for the MM k-CPP we develop a counterpart concept for the capacity restriction of the CARP, namely a distance restriction for each single tour imposed by an upper bound value. Using this distance restriction we devise a procedure to determine the minimum number of postmen required to traverse a given node set and the depot, which enables us to adapt the lower bounding procedures of the CARP to the MM k-CPP. Finally, we develop a branch-and-cut algorithm for the MM k-CPP based on an IP formulation for the CARP. In addition to the utilization of standard valid inequalities and corresponding separation routines adapted from the CARP we devise a new class of valid inequalities for the MM k-CPP, called the aggregated L-tour constraints, as well as effective procedures to separate them. Computational experiments on an extensive set of test instances as well as comparisons with results achieved by commercial optimization tools confirm the effectiveness of our approach."^^ . "2004" . . . . . . . . "Dino"^^ . "Ahr"^^ . "Dino Ahr"^^ . . . . . . "Contributions to Multiple Postmen Problems (PDF)"^^ . . . "thesis.pdf"^^ . . . "Contributions to Multiple Postmen Problems (Other)"^^ . . . . . . "lightbox.jpg"^^ . . . "Contributions to Multiple Postmen Problems (Other)"^^ . . . . . . "preview.jpg"^^ . . . "Contributions to Multiple Postmen Problems (Other)"^^ . . . . . . "medium.jpg"^^ . . . "Contributions to Multiple Postmen Problems (Other)"^^ . . . . . . "small.jpg"^^ . . "HTML Summary of #4963 \n\nContributions to Multiple Postmen Problems\n\n" . "text/html" . . . "510 Mathematik"@de . "510 Mathematics"@en . .