Universität zu Köln

Semi-Präemptives Transportieren

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

[img]
Preview
PDF
Download (923Kb) | Preview

    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 abstract:
    AbstractLanguage
    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:
    CreatorsEmail
    Räbiger, Dirkdirk@raebiger.net
    URN: urn:nbn:de:hbz:38-15112
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    tourenplanung , umladen , arboreszenz , optimierung , transportproblemGerman
    reload , arborescence , optimization , pickup and deliveryEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: German
    Date: 2005
    Date Type: Completion
    Date of oral exam: 12 July 2005
    Full Text Status: Public
    Date Deposited: 31 Aug 2005 08:26:23
    Referee
    NameAcademic Title
    Schrader, RainerProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/1511

    Actions (login required)

    View Item