eprintid: 4963
rev_number: 8
eprint_status: archive
userid: 1
dir: disk0/00/00/49/63
datestamp: 2004-10-13 13:50:29
lastmod: 2014-04-03 18:35:49
status_changed: 2012-08-14 15:13:11
type: doctoralThesis
metadata_visibility: show
creators_name: Ahr, Dino
title: Contributions to Multiple Postmen Problems
title_de: Beiträge zu multiplen Postboten Problemen
ispublished: pub
subjects: 510
divisions: 110300
adv_faculty: af-11
keywords: Postboten Probleme , Heuristiken , Untere SchrankenBranch-and-Cut method , Postmen Problems , Heuristics , Lower Bounds
cterms_swd: Branch-and-Cut-Methode
abstract: 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.
abstract_translated_text: In der vorliegenden Arbeit leisten wir Beiträge zur optimalen Lösung von Postboten Problemen. Dabei konzentrieren wir uns auf Postboten Probleme, bei denen für mehrere (k >= 2) Postboten Touren bestimmt werden sollen, wobei alle Touren beim Postamt starten und enden müssen. Wir betrachten das Min-Max k-Chinese Postman Problem (MM k-CPP), bei dem für ein gegebenes Straßennetzwerk k Touren derart bestimmt werden sollen, dass jede Straße mindestens einmal durchlaufen wird und die längste der k Touren von minimaler Länge ist. Weiterhin betrachten wir das Capacitated Arc Routing Problem (CARP), bei dem für jede Straße eine gewisser Bedarf zu decken ist (übertragen auf das Problem von Müllfahrzeugen, würde das z.B. bedeuten, dass eine gewisse Menge von Müll abzutransportieren ist). Hier ist nun die Zielsetzung, die Touren so zu bestimmen, dass die Gesamtlänge minimiert wird und zusätzlich bei keinem der Postboten eine Kapazitätsbeschränkung verletzt wird (bei den Müllfahrzeugen dürfte also kein Fahrzeug mehr Müll abtransportieren, als es Ladekapazität hat). Beide Probleme sind NP-hart. Daher ist die Entwicklung effektiver Methoden zur Bestimmung guter unterer und oberer Schranken von grundlegender Bedeutung, um diese Probleme (bis zu einer gewissen Größenordnung) optimal lösen zu können. Basierend auf einem detaillierten Überblick über existierende Algorithmen zur Bestimmung unterer Schranken für das CARP entwickeln wir einen verbesserten Algorithmus und demonstrieren seine Güte mit Hilfe von Rechenexperimenten. Ferner zeigen wir für zwei existierende Algorithmen, die bisher in der Literatur als gleichwertig betrachtet worden sind, dass der eine Algorithmus den anderen dominiert. Nach einer ausführlichen Besprechung von IP Formulierungen für das CARP und der Vorstellung existierender exakter Verfahren, die auf diesen Formulierungen basieren, stellen wir eine neue Methode vor, mit der eine wichtige Klasse von Ungleichungen, die sogenannten Aggregated Capacity Constraints, erstmals exakt separiert werden kann. Mittels eines Cutting Plane Algorithmus, der diese neue Separierung verwendet, bestimmen wir verbesserte untere Schranken für einige Instanzen aus der Literatur. Für das MM k-CPP präsentieren wir zunächst die einzige existierende Heuristik, die man in der Literatur findet. Dann entwickeln wir zwei neue Heuristiken, verschiedene Verbesserungsverfahren und einen Tabu Search Algorithmus, der alle diese Verfahren kombiniert. Rechenexperimente zeigen, dass der Tabu Search Algorithmus sehr gute Lösungen berechnet, die in vielen Fällen sogar optimal sind. Zur Bestimmung unterer Schranken für das MM k-CPP entwickeln wir zunächst ein analoges Konzept zu den Kapazitätsbeschränkungen beim CARP. Eine Distanzbeschränkung für eine einzelne Postboten Tour beim MM k-CPP ist natürlicherweise durch eine obere Schranke gegeben. Mit Hilfe dieser Distanzbeschränkung entwickeln wir ein Verfahren zur Berechnung der minimalen Anzahl von Postboten, die benötigt wird, um einen Teilbereich des Straßennetzwerkes zu durchlaufen. Dieses Verfahren erlaubt es uns, die für das CARP entwickelten Algorithmen zur Bestimmung unterer Schranken auf das MM k-CPP zu übertragen. Schließlich entwickeln wir, basierend auf einer IP Formulierung für das CARP, einen Branch-and-Cut Algorithmus für das MM k-CPP. Zusätzlich zu den gängigen gültigen Ungleichungen und dazugehörigen Separierungsverfahren erarbeiten wir eine neue Klasse gültiger Ungleichungen für das MM k-CPP, die sogenannten Aggregated L-Tour Constraints, sowie effektive Separierungsalgorithmen. Umfangreiche Rechenexperimente auf einer großen Menge von Testinstanzen sowie Vergleiche mit Ergebnissen kommerzieller Optimierungswerkzeuge bestätigen die Leistungsfähigkeit unseres Verfahrens.
abstract_translated_lang: ger
date: 2004
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00004963
ppn_swb: 1643854690
own_urn: urn:nbn:de:bsz:16-opus-49633
date_accepted: 2004-09-21
advisor: HASH(0x556120df8c08)
language: eng
bibsort: AHRDINOCONTRIBUTI2004
full_text_status: public
citation:   Ahr, Dino  (2004) Contributions to Multiple Postmen Problems.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/4963/1/thesis.pdf