Universität zu Köln

Räbiger, Dirk (2005). Semi-Präemptives Transportieren. PhD thesis, Universität zu Köln.

Preview

PDF diss_raebiger.pdf Download (945kB)

Abstract

Das Problem, einen Roboter (oder ein Fahrzeug) so zwischen n Stationen zu steuern, daß m Objekte von ihrem Ausgangspunkt zu ihrem Ziel transportiert werden können und dabei die zurückgelegte Fahrstrecke minimiert wird, bezeichnet man als Pickup--And--Delivery--Problem. Diese Aufgabenstellung ist in der Vergangenheit gut untersucht worden, sogar wenn die Stationen auf eine besondere Weise angeordnet sind, z.B. in einer Reihe oder im Kreis. Üblicherweise darf der Roboter entweder jede oder keine Station als Umladestation benutzen. Man spricht in diesen Fällen von einem präemptiven bzw. nicht--präemptiven Transport. Wir werden diese Konzepte verallgemeinern, indem nur ein Teil der Stationen für das Umladen benutzt werden darf. In Anlehnung an die beiden anderen Versionen soll diese Fragestellung semi--präemptiv heißen. Dabei differenzieren wir zwischen einer exogenen und einer endogenen Variante. In der ersten darf der Roboter nur an gekennzeichneten Stationen umladen. In der zweiten teilen wir ihm eine Zahl k mit, und es ist Teil der Aufgabenstellung zu entscheiden, an welchen k Stationen umgeladen wird. Wir zeigen, daß sowohl die exogene als auch die endogene Version auf einem Pfad und auf einem Kreis effizient lösbar ist und geben jeweils dynamische Lösungverfahren an. Beide Varianten sind auf Bäumen NP--vollständig. Für den exogenen Fall geben wir einen Approximationsalgorithmus mit einer Güte von 4/3 an. Für die endogene Aufgabenstellung präsentieren wir eine (4/3+c)--Approximation für beliebiges c > 0. Schließlich nutzen ein bekanntes Resultat, um eine Approximation für das exogene und endogene Transportproblem auf metrisch gewichteten Graphen angeben zu können. Aus der angewandten Problemstellung ergibt sich ein graphentheoretisches Teilproblem, das wir näher untersuchen. In einem gerichteten Graphen G=(V,E^r\dot\cup E^b) mit einer rot/blau--partitionierten Kantenmenge soll zu gegebener Kostenfunktion eine kostenminimale und aufspannende Arboreszenz bestimmt werden, die höchstens d blaue Kanten benutzt. Wir geben ein voll polynomielles Approximationsschema an. Dieses nutzen wir, um das endogene Transportproblem auf Bäumen zu approximieren.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Semi-Preemptive Transportation English
Translated abstract:	Abstract Language We consider the problem of routing a robot (or vehicle) between n stations in order to transport m objects from their source node to their destination node such that the total travel distance is minimized. This problem is known as Pickup and Delivery Problem and well studied in literature, even if the stations are specially arranged, e.g. on a linear track or circle. The robot may use either all or none of the stations for reloading. These cases are said to be preemptive resp. non--preemptive. We will generalize these concepts by restricting the nodes that can be used for reloading. According to the previous versions we will call this variation semi--preemptive. We will distinguish between an exogenous and an endogenous case. Problems of the first type will allow the robot to use only a subset of stations that can be used as reload nodes. The latter case consists of a number k and it will be part of the problem to decide at which stations the robot reloads, but no more than k times. We will show that both the exogenous and the endogenous problem are efficiently solvable by dynamic programming on paths and circles. Both variants are NP--complete on trees. For the exogenous case we will give an approximation algorithm with ratio 4/3. The endogenous case can be solved with ratio (4/3+c), for arbitrary c > 0. In conclusion we use a known result in order to approximately solve the exogenous resp. endogenous routing problem on graphs weighted by a metric. We will study a graph theoretical problem which arises from the mentioned transportation problem. Given a directed graph G=(V,E^r\dot\cup E^b) with the arc set partitioned into red and blue subsets and a cost function on the arc set, find a minimal cost arborescence spanning G and using at most d blue arcs. Within this work a fully polynomial time approximation scheme (FPTAS) will be presented for this problem. The FPTAS will be used to approximately solve the endogenous transportation problem on a tree. English
Creators:	Creators Email ORCID ORCID Put Code Räbiger, Dirk UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-15112
Date:	2005
Language:	German
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language tourenplanung , umladen , arboreszenz , optimierung , transportproblem German reload , arborescence , optimization , pickup and delivery English
Date of oral exam:	12 July 2005
Referee:	Name Academic Title Schrader, Rainer Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/1511