Zugl.: Erlangen, Nürnberg, Universiẗat, Diss., 2008.

Durch steigende Rohölpreise werden alternative Antriebsmöglichkeiten zu Verbrennungsmotoren gesucht, ein aussichtsreiches Konzept ist die Elektromobilität. Elektromotoren werden nicht nur bei Automobilen eingesetzt sondern auch bei Fahrrädern, zum Beispiel bei Pedelecs. In der vorliegenden Arbeit werden verschiedene Möglichkeiten für die Optimierung der Reichweite dieser Fahrräder untersucht. Dafür wird zuerst ein vereinfachtes Modell für ein Pedelec hergeleitet, mit dem die benötigte Energiemenge für eine vorgegebene Strecke errechnet wird. Auf Grundlage dieser Berechnung werden im zweiten Teil verschiedene Optimierungsmethoden untersucht. Anschließend wird die Implementierung einer Optimierungsmethode vorgestellt. Zum Abschluss erfolgt eine Diskussion der Ergebnisse, eine kurze Zusammenfassung und ein Ausblick auf zukünftige Aufgaben.

University, Diss.--Karlsruhe, 2000.

Bei verkehrspolitischen und infrastrukturellen Massnahmen folgen als wesentliche Nachfrageveränderungen vor allem Routen- und Verkehrsmittelwahleffekte. Mit der Anwendung der sequentiellen Routen- und Verkehrsmittelwahlmodelle, ist bei solchen Massnahmen aus verschiedenen Gründen eine konsistente und gesamthafte Gleichgewichtslösung nicht möglich. Das Ziel dieser Untersuchung war, ein konsistentes und verfeinertes Verfahren zu entwickeln, mit dem die Routen- und Verkehrsmittelwahl simultan bzw. in einem Schritt als eine Entscheidung berechnet werden kann. Neben dem Gleichgewicht bei der Verteilung der Verkehrsnachfrage auf die Alternativen, war die konsistente Schätzung der Modellparameter für die Bewertung von Einflussfaktoren bei den Entscheidungen hier eine weitere wichtige Anforderung. Das Modell ist in der Lage, ein realitätsentsprechendes Verhalten der Verkehrsteilnehmer, sowohl bei schwach, als auch bei stark belasteten Strassennetzen, zu beschreiben. Die unterschiedliche Wahrnehmung der Reisekosten der Verkehrsteilnehmer und die Netzüberbelastungen werden durch ein stochastisches Nutzergleichgewicht abgebildet. Das entwickelte Verfahren ermöglicht es: - die Nachfrageaufteilung mit einem konsistenten Gleichgewicht zwischen Verkehrsangebot und Verkehrsnachfrage zu berechnen. Dabei wird ein Gleichgewicht nicht nur innerhalb des Strassen- oder Schienennetzes, sondern zwischen allen verfügbaren Alternativen (unabhängig vom Verkehrsmittel) gesucht. - durch die iterative Kalibration der Modellparameter und die Nachfrageaufteilung ein konsistentes Gleichgewicht zwischen den geschätzten Modellparametern für die Nutzenfunktion und der Nachfrageaufteilung auf die vorhandenen Alternativen (Routen) zu berechnen. - mit einem stochastischen Nutzergleichgwicht die unterschiedliche Wahrnehmung der Nutzen bzw. der generalisierten Kosten der Verkehrsteilnehmer bei der Nachfrageaufteilung zu berücksichtigen. - die Auswirkungen von Angebotsveränderungen auf die Verkehrsmittelwahl und Routenwahl durch simultane Modellierung der Entscheidungen konsistent und ohne Rückkoppelungschritte zu berechnen.

Univ., FB Wirtschaftswiss., Diss.--Hamburg, 2001. / Literaturverz. S. [193] - 208.

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

Durch steigende Rohölpreise werden alternative Antriebsmöglichkeiten zu Verbrennungsmotoren gesucht, ein aussichtsreiches Konzept ist die Elektromobilität. Elektromotoren werden nicht nur bei Automobilen eingesetzt sondern auch bei Fahrrädern, zum Beispiel bei Pedelecs. In der vorliegenden Arbeit werden verschiedene Möglichkeiten für die Optimierung der Reichweite dieser Fahrräder untersucht. Dafür wird zuerst ein vereinfachtes Modell für ein Pedelec hergeleitet, mit dem die benötigte Energiemenge für eine vorgegebene Strecke errechnet wird. Auf Grundlage dieser Berechnung werden im zweiten Teil verschiedene Optimierungsmethoden untersucht. Anschließend wird die Implementierung einer Optimierungsmethode vorgestellt. Zum Abschluss erfolgt eine Diskussion der Ergebnisse, eine kurze Zusammenfassung und ein Ausblick auf zukünftige Aufgaben.:Abbildungsverzeichnis iii Tabellenverzeichnis iv Codeverzeichniss v Bibliographische Angaben vi 1. Einleitung 1 1.1. Motivation 1 1.2. Diskussion der Aufgabenstellung 1 1.3. Gliederung 2 2. Modellierungsbetrachtung 3 2.1. Arten von Elektrofahrrädern 3 2.2. Modellierung von Elektrofahrzeugen 3 2.3. Spezielles Modell am Beispiel des Pedelecs 5 2.3.1. Beschreibung des Test-Pedelecs 5 2.3.2. Modifizierung des allgemeinen Modells 6 2.3.3. Zusammensetzung der physikalischen Leistung 7 3. Routendatenaufbereitung 11 3.1. Dateiformat 11 3.2. Kartentools 12 3.2.1. Routenplanung 12 3.2.2. Auswertung gefahrener Routen 12 3.3. Umrechnung von geographischer Breite und Länge 13 3.4. überarbeitung der Höhendaten 15 4. Optimierung der Fahrerunterstützung 17 4.1. Vorbetrachtungen 17 4.2. GewählteOptimierungsmethode 21 4.2.1. Sortierte Rückwärtsmethode 22 4.2.2. Binäre Suche 24 5. Implementierung in Python 27 5.1. Vorbereitung der Daten 27 5.2. Berechnung der Leistung 27 5.3. Optimierung 28 5.4. Auswertung 28 6. Diskussion der Ergebnisse 29 6.1. Diskussion und Ansätze für Weiterentwicklungen 29 6.2. Zusammenfassung 30 6.3. Ausblick 31 Literaturverzeichnis 33 A. Quellcode 36 A.1. Modul optimizetrack 39 A.1.1. Optionen für den Aufruf 39 A.2. Modul optimize 39 A.2.1. Klasse Optimizer 39 A.3. Modul simplegpx 42 A.3.1. Klasse SimpleGPXPoint 42 A.4. Module trackwrapper 43 A.4.1. Globale Konstanten 43 A.4.2. Klasse TrackSegment 43 A.4.3. Klasse TrackData 44 B. Verzeichnisstruktur der Begleit-CD 54

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

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

Bei verkehrspolitischen und infrastrukturellen Massnahmen folgen als wesentliche Nachfrageveränderungen vor allem Routen- und Verkehrsmittelwahleffekte. Mit der Anwendung der sequentiellen Routen- und Verkehrsmittelwahlmodelle, ist bei solchen Massnahmen aus verschiedenen Gründen eine konsistente und gesamthafte Gleichgewichtslösung nicht möglich. Das Ziel dieser Untersuchung war, ein konsistentes und verfeinertes Verfahren zu entwickeln, mit dem die Routen- und Verkehrsmittelwahl simultan bzw. in einem Schritt als eine Entscheidung berechnet werden kann. Neben dem Gleichgewicht bei der Verteilung der Verkehrsnachfrage auf die Alternativen, war die konsistente Schätzung der Modellparameter für die Bewertung von Einflussfaktoren bei den Entscheidungen hier eine weitere wichtige Anforderung. Das Modell ist in der Lage, ein realitätsentsprechendes Verhalten der Verkehrsteilnehmer, sowohl bei schwach, als auch bei stark belasteten Strassennetzen, zu beschreiben. Die unterschiedliche Wahrnehmung der Reisekosten der Verkehrsteilnehmer und die Netzüberbelastungen werden durch ein stochastisches Nutzergleichgewicht abgebildet. Das entwickelte Verfahren ermöglicht es: - die Nachfrageaufteilung mit einem konsistenten Gleichgewicht zwischen Verkehrsangebot und Verkehrsnachfrage zu berechnen. Dabei wird ein Gleichgewicht nicht nur innerhalb des Strassen- oder Schienennetzes, sondern zwischen allen verfügbaren Alternativen (unabhängig vom Verkehrsmittel) gesucht. - durch die iterative Kalibration der Modellparameter und die Nachfrageaufteilung ein konsistentes Gleichgewicht zwischen den geschätzten Modellparametern für die Nutzenfunktion und der Nachfrageaufteilung auf die vorhandenen Alternativen (Routen) zu berechnen. - mit einem stochastischen Nutzergleichgwicht die unterschiedliche Wahrnehmung der Nutzen bzw. der generalisierten Kosten der Verkehrsteilnehmer bei der Nachfrageaufteilung zu berücksichtigen. - die Auswirkungen von Angebotsveränderungen auf die Verkehrsmittelwahl und Routenwahl durch simultane Modellierung der Entscheidungen konsistent und ohne Rückkoppelungschritte zu berechnen.