Detailansicht
Essays in Combinatorial Optimization for Graph-Based Problems
Maryam Dehghan Chenary
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doctor of Philosophy-Doktoratsstudium Wirtschaftswissenschaften: Business Analytics, Logistics and Operations Research
Betreuer*innen
Richard Hartl ,
Christian Tilk
DOI
10.25365/thesis.80368
URN
urn:nbn:at:at-ubw:1-18672.66189.700397-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Arbeit entwickelt und bewertet neuartige kombinatorische Optimierungstechniken, die auf zwei hochmoderne netzwerkbasierte Fallstudien angewendet werden. Ihr übergeordnetes Ziel ist es, effiziente Algorithmen zur Analyse groß angelegter Systeme zu identifizieren, zu entwerfen und zu bewerten, die als Graphen darstellbar sind, unabhängig davon, ob diese Systeme aus komplexen Netzwerkinteraktionen entstehen oder für Anwendungen in der Betriebsforschung entwickelt wurden. Der erste Teil der Arbeit konzentriert sich auf die kombinatorische Optimierung und befasst sich mit einem neuartigen kombinierten Abfallsammelproblem (CWCP). Das CWCP als zweistufiges Entscheidungsproblem ist auf einem ungerichteten Graphen definiert, wobei jede Kante mit zwei Transportkosten verbunden ist: eine entspricht einem Punkt-zu-Punkt-Abfallsammelsystem, bei dem der Abfall mit Lastwagen von bestimmten Punkten abgeholt wird, und eine andere einem automatisierten Abfallsammelsystem (AWCS), bei dem der Abfall über ein Rohrleitungsnetz zu einem zentralen Terminal transportiert wird. Das CWCP zielt darauf ab, gleichzeitig zu entscheiden, ob jeder Sammelpunkt von einem Lkw oder vom AWCS bedient werden soll, und gleichzeitig eine Reihe von realisierbaren Lkw-Routen und höchstens einen gültigen Wurzelbaum zu finden, die zusammen alle Kundenknoten im Graphen zu minimalen Kosten bedienen. Dieses zweistufige Optimierungsproblem umfasst sowohl ein Kapazitätsbeschränktes Fahrzeug-Routing-Problem (CVRP) als auch ein Hop/Node-gewichtetes Steiner-Baum-Problem, die stark voneinander abhängig sind. Zur Lösung des CWCP werden matheuristische und exakte Algorithmen entwickelt, die auf Set-Partitioning-Formulierungen, Spaltengenerierung und einem Branch-and-Price-and-Cut-Framework basieren. Es werden zwei Dekompositionsstrategien untersucht, eine separate und eine kombinierte, um die Kopplung zwischen Routing- und Baumdesign-Entscheidungen zu verwalten. Computergestützte Experimente mit Benchmark-Datensätzen und realen Daten aus Wien belegen die Effizienz, Skalierbarkeit und praktische Relevanz der vorgeschlagenen Methoden. Der zweite Teil der Arbeit untersucht optimierungsbasierte Ansätze zur Analyse großer komplexer Netzwerke, wobei ein besonderer Schwerpunkt auf der Gemeinschaftserkennung liegt, also der Aufgabe, dicht miteinander verbundene Gruppen von Knoten innerhalb eines Graphen zu identifizieren. Obwohl diese Forschungsrichtung eher in der Netzwerkwissenschaft als in der klassischen Operationsforschung verwurzelt ist, verwendet sie einen analogen analytischen Rahmen, der auf der Optimierungstheorie basiert. Die in diesem Teil vorgestellten Studien formulieren die Community Detection als ganzzahlige und gemischt-ganzzahlige Programmierprobleme, bei denen exakte, heuristische und hybride Techniken aus der kombinatorischen Optimierung angepasst werden, um strukturelle Muster und funktionale Module innerhalb komplexer Netzwerke aufzudecken. Es wurden experimentelle Auswertungen anhand von Standard-Benchmark-Datensätzen durchgeführt, um die Leistungsfähigkeit der vorgeschlagenen Methoden im Vergleich zu führenden Ansätzen in der Literatur zu bewerten.
Abstract
(Englisch)
This thesis develops and evaluates novel combinatorial optimization techniques applied to two state-of-the-art network-based case studies. Its overarching goal is to identify, design, and evaluate efficient algorithms for analyzing large-scale systems representable as graphs, whether these systems arise from complex network interactions or are engineered for operational research applications. The first part of the thesis focuses on combinatorial optimization and addresses a novel Combined Waste Collection Problem (CWCP). The CWCP as a two-stage decision problem, is defined on an undirected graph where each edge is associated with two transportation costs: one corresponding to a Point-to-Point Waste Collection System, in which waste is collected from designated points using trucks, and another associated with an Automated Waste Collection System (AWCS), in which waste is transported via a pipeline network to a central terminal. The CWCP aims to simultaneously decide whether each collection point should be served by a truck or by the AWCS while also seeking a set of feasible truck routes and, at most, one valid rooted tree that together serve all customer nodes in the graph at minimum cost. This two-stage optimization problem involves both a Capacitated Vehicle Routing Problem (CVRP) and a \emph{Hop/Node-Weighted Steiner Tree Problem}, which are strongly interdependent. To solve the CWCP, matheuristic and exact algorithms are developed based on set-partitioning formulations, column generation, and a branch-price-and-cut framework. Two decomposition strategies, separate and combined, are explored to manage the coupling between routing and tree-design decisions. Computational experiments have been conducted on benchmark datasets and real-world data from Vienna. The second part of the thesis investigates optimization-based approaches for analyzing large-scale complex networks, with a particular focus on community detection, the task of identifying densely interconnected groups of nodes within a graph. While this research is more closely aligned with network science than with classical operational research, it applies a similar analytical framework grounded in optimization theory. The studies presented in this thesis formulate community detection as integer and mixed-integer programming problems, where exact, heuristic, and hybrid techniques from combinatorial optimization are adapted to uncover structural patterns and functional modules within complex networks. Experimental evaluations on standard benchmark datasets were conducted to assess the performance of the proposed methods relative to leading approaches in the literature.
Schlagwörter
Schlagwörter
(Deutsch)
Automatisierte Abfallsammelsysteme Spaltengenerierungsbasierter matheuristischer Algorithmus Herkömmliche Abfallsammelsysteme Knotengewichtetes Steiner-Baum-Problem Elementares kürzestes Weg-Problem Steiner-Baum-Problem mit Einnahmen und Sprungbeschränkungen Spaltengenerierung Verzweigen-und-Preis-und-Schneiden Graphenpartitionierung Gemeinschaftserkennung Komplexe Netzwerkanalyse
Schlagwörter
(Englisch)
Automated waste collection systems Ccolumn-generation-based matheuristic algorithm Conventional waste collection systems Node-weighted Steiner tree problem Elementary shortest path problem Steiner tree problem Column-generation Branch-and-price-and-cut Graph partitioning Community detection Complex network analysis
Autor*innen
Maryam Dehghan Chenary 
Haupttitel (Englisch)
Essays in Combinatorial Optimization for Graph-Based Problems
Paralleltitel (Deutsch)
Aufsätze zur kombinatorischen Optimierung für graphbasierte Probleme
Publikationsjahr
2025
Umfangsangabe
XVI, 129 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Dominique Feillet ,
Stefan Schmid
Klassifikation
85 Betriebswirtschaft > 85.32 Beschaffung. Materialwirtschaft
AC Nummer
AC17782201
Utheses ID
79157
Studienkennzahl
UA | 794 | 370 | 403 |