This thesis considers the Two-Stage Vehicle Routing Problem (VRP) with Profits and Buffers, which generalizes various optimization problems that are relevant for practical applications, such as the Two-Machine Flow Shop with Buffers and the Orienteering Problem. Two optimization problems are considered for the Two-Stage VRP with Profits and Buffers, namely the minimization of total time while respecting a profit constraint and the maximization of total profit under a budget constraint. The former generalizes the makespan minimization problem for the Two-Machine Flow Shop with Buffers, whereas the latter is comparable to the problem of maximizing score in the Orienteering Problem. For the three problems, a theoretical analysis is performed regarding computational complexity, existence of optimal permutation schedules (where all vehicles traverse the same nodes in the same order) and potential gaps in attainable solution quality between permutation schedules and non-permutation schedules. The obtained theoretical results are visualized in a table that gives an overview of various subproblems belonging to the Two-Stage VRP with Profits and Buffers, their theoretical properties and how they are connected. For the Two-Machine Flow Shop with Buffers and the Orienteering Problem, two metaheuristics 2BF-ILS and VNSOP are presented that obtain favorable results in computational experiments when compared to other state-of-the-art algorithms. For the Two-Stage VRP with Profits and Buffers, an algorithmic framework for Iterative Search Algorithms with Variable Neighborhoods (ISAVaN) is proposed that generalizes aspects from 2BF-ILS as well as VNSOP. Various algorithms derived from that framework are evaluated in an experimental study. The evaluation methodology used for all computational experiments in this thesis takes the performance during the run time into account and demonstrates that algorithms for structurally different problems, which are encompassed by the Two-Stage VRP with Profits and Buffers, can be evaluated with similar methods. The results show that the most suitable choice for the components in these algorithms is dependent on the properties of the problem and the considered evaluation criteria. However, a number of similarities to algorithms that perform well for the Two-Machine Flow Shop with Buffers and the Orienteering Problem can be identified. The framework unifies these characteristics, providing a spectrum of algorithms that can be adapted to the specifics of the considered Vehicle Routing Problem.:1 Introduction 2 Background 2.1 Problem Motivation 2.2 Formal Definition of the Two-Stage VRP with Profits and Buffers 2.3 Review of Literature on Related Vehicle Routing Problems 2.3.1 Two-Stage Vehicle Routing Problems 2.3.2 Vehicle Routing Problems with Profits 2.3.3 Vehicle Routing Problems with Capacity- or Resource-based Restrictions 2.4 Preliminary Remarks on Subsequent Chapters 3 The Two-Machine Flow Shop Problem with Buffers 3.1 Review of Literature on Flow Shop Problems with Buffers 3.1.1 Algorithms and Metaheuristics for Flow Shops with Buffers 3.1.2 Two-Machine Flow Shop Problems with Buffers 3.1.3 Blocking Flow Shops 3.1.4 Non-Permutation Schedules 3.1.5 Other Extensions and Variations of Flow Shop Problems 3.2 Theoretical Properties 3.2.1 Computational Complexity 3.2.2 The Existence of Optimal Permutation Schedules 3.2.3 The Gap Between Permutation Schedules an Non-Permutation 3.3 A Modification of the NEH Heuristic 3.4 An Iterated Local Search for the Two-Machine Flow Shop Problem with Buffers 3.5 Computational Evaluation 3.5.1 Algorithms for Comparison 3.5.2 Generation of Problem Instances 3.5.3 Parameter Values 3.5.4 Comparison of 2BF-ILS with other Metaheuristics 3.5.5 Comparison of 2BF-OPT with NEH 3.6 Summary 4 The Orienteering Problem 4.1 Review of Literature on Orienteering Problems 4.2 Theoretical Properties 4.3 A Variable Neighborhood Search for the Orienteering Problem 4.4 Computational Evaluation 4.4.1 Measurement of Algorithm Performance 4.4.2 Choice of Algorithms for Comparison 4.4.3 Problem Instances 4.4.4 Parameter Values 4.4.5 Experimental Setup 4.4.6 Comparison of VNSOP with other Metaheuristics 4.5 Summary 5 The Two-Stage Vehicle Routing Problem with Profits and Buffers 5.1 Theoretical Properties of the Two-Stage VRP with Profits and Buffers 5.1.1 Computational Complexity of the General Problem 5.1.2 Existence of Permutation Schedules in the Set of Optimal Solutions 5.1.3 The Gap Between Permutation Schedules an Non-Permutation Schedules 5.1.4 Remarks on Restricted Cases 5.1.5 Overview of Theoretical Results 5.2 A Metaheuristic Framework for the Two-Stage VRP with Profits and Buffers 5.3 Experimental Results 5.3.1 Problem Instances 5.3.2 Experimental Results for O_{max R, Cmax≤B} 5.3.3 Experimental Results for O_{min Cmax, R≥Q} 5.4 Summary Bibliography List of Figures List of Tables List of Algorithms

Das Konzept von aktiven Brownschen Teilchen kann benutzt werden, um das Verhalten einfacher biologischer Organismen oder künstlicher Objekte, welche die Möglichkeit besitzen sich von selbst fortzubewegen zu beschreiben. Als Bewegungsgleichungen für aktive Brownsche Teilchen kommen Langevin Gleichungen zum Einsatz. In dieser Arbeit werden aktive Teilchen mit konstanter Geschwindigkeit diskutiert. Im ersten Teil der Arbeit wirkt auf die Bewegungsrichtung des Teilchen weißes alpha-stabiles Rauschen. Es werden die mittlere quadratische Verschiebung und der effektive Diffusionskoeffizient bestimmt. Eine überdampfte Beschreibung, gültig für Zeiten groß gegenüber der Relaxationszeit wird hergleitet. Als experimentell zugängliche Meßgröße, welche als Unterscheidungsmerkmal für die unterschiedlichen Rauscharten herangezogen werden kann, wird die Kurtose berechnet. Neben weißem Rauschen wird noch der Fall eines Ornstein-Uhlenbeck Prozesses angetrieben von Cauchy verteiltem Rauschen diskutiert. Während eine normale Diffusion mit zu weißem Rauschen identischem Diffusionskoeffizienten bestimmt wird, kann die beobachtete Verteilung der Verschiebungen Nicht-Gaußförmig sein. Die Zeit für den Übergang zur Gaußverteilung kann deutlich größer als die Zeitskale Relaxationszeit und die Zeitskale des Ornstein-Uhlenbeck Prozesses sein. Eine Grenze der benötigten Zeit wird durch eine Näherung der Kurtosis ermittelt. Weiterhin werden die Grundlagen eines stochastischen Modells für lokale Suche gelegt. Lokale Suche ist die Suche in der näheren Umgebung eines bestimmten Punktes, welcher Haus genannt wird. Abermals diskutieren wir ein aktives Teilchen mit unveränderlichem Absolutbetrag der Geschwindigkeit und weißen alpha-stabilem Rauschen in der Bewegungsrichtungsdynamik. Die deterministische Bewegung des Teilchens wird analysiert bevor die Situation mit Rauschen betrachtet wird. Die stationäre Aufenthaltswahrscheinlichkeitsdichtefunktion wird bestimmt. Es wird eine optimale Rauschstärke für die lokale Suche, das heißt für das Auffinden eines neuen Ortes in kleinstmöglicher Zeit festgestellt. Die kleinstmögliche Zeit wird kaum von der Rauschart abhängen. Wir werden jedoch feststellen, dass die Rauschart deutlichen Einfluß auf die Rückkehrwahrscheinlichkeit zum Haus hat, wenn die Richtung des zu Hauses fehlerbehaftet ist. Weiterhin wird das Model durch eine an das Haus abstandsabhängige Kopplung erweitert werden. Zum Abschluß betrachten wir eine Gruppe von Suchern. / Active Brownian particles described by Langevin equations are used to model the behavior of simple biological organisms or artificial objects that are able to perform self propulsion. In this thesis we discuss active particles with constant speed. In the first part, we consider angular driving by white Levy-stable noise and we discuss the mean squared displacement and diffusion coefficients. We derive an overdamped description for those particles that is valid at time scales larger the relaxation time. In order to provide an experimentally accessible property that distinguishes between the considered noise types, we derive an analytical expression for the kurtosis. Afterwards, we consider an Ornstein-Uhlenbeck process driven by Cauchy noise in the angular dynamics of the particle. While, we find normal diffusion with the diffusion coefficient identical to the white noise case we observe a Non-Gaussian displacement at time scales that can be considerable larger than the relaxation time and the time scale provided by the Ornstein-Uhlenbeck process. In order to provide a limit for the time needed for the transition to a Gaussian displacement, we approximate the kurtosis. Afterwards, we lay the foundation for a stochastic model for local search. Local search is concerned with the neighborhood of a given spot called home. We consider an active particle with constant speed and alpha-stable noise in the dynamics of the direction of motion. The deterministic motion will be discussed before considering the noise to be present. An analytical result for the steady state spatial density will be given. We will find an optimal noise strength for the local search and only a weak dependence on the considered noise types. Several extensions to the introduced model will then be considered. One extension includes a distance dependent coupling towards the home and thus the model becomes more general. Another extension concerned with an erroneous understanding by the particle of the direction of the home leads to the result that the return probability to the home depends on the noise type. Finally we consider a group of searchers.