Διδακτορικές διατριβές

Μόνιμο URI για αυτήν τη συλλογήhttps://pyxida.aueb.gr/handle/123456789/53

Περιήγηση

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 2 από 2

2-sided and multi-sided stable matchings: structures, algorithms, and applications
Eirinakis, Pavlos; Athens University of Economics and Business, Department of Management Science and Technology; Miliotis, Panagiotis
This thesis examines the Stable Matching (SM) problem and some of its most important variants, namely the Stable Admissions (SA), the many-to-many Stable Matching (MM), and the Chain Stable Network (CSN) problem. In the context of the SM problem, a time-optimal algorithm is provided that identifies which of the non-stable pairs can be removed from the agents preference lists without altering the set of solutions. To identify them, we utilize rotations and the transitive reduction of the rotation-poset graph. Then, using a directed line-graph to represent the SM problem, namely the marriage graph, we derive a sparse description of the SM polytope. This description is further reduced to obtain the minimal one by identifying the minimal equation system and the facets of the corresponding polytope. Also, the dimension of the SM polytope is proved to be equal to the number of rotations, while its diameter is also established. Moreover, we study the alternative rotation-based representation of the SM polytope, establishing its dimension and providing its minimal description.Further, we de.ne rotations in the SA setting and propose a time-optimal algorithm for identifying all rotations and all non-stable pairs. This algorithm is then extended to the MM case under pairwise stability, preferences over individuals, and the max-min criterion. In order to maintain the algorithms optimal complexity, we propose the use of a double-stack, a structure which enables exposing and eliminating rotations efficiently. Next, we revisit the corresponding rotation-poset graph and illustrate a time-and space-optimal algorithm for enumerating all solutions to the MM problem. Then, a polynomial algorithm for finding the minimum-weight stable matching is provided, which can also be used to improve the known time-bounds for identifying the egalitarian and the optimal one. The above mentioned algorithms are shown to be applicable even in the case of more complex preference and stability conditions. In a Constraint Programming (CP) context, we show that identifying all stable pairs in the SA and the MM case is equivalent to establishing hyperarc consistency. Furthermore, we provide a predicate which models the MM problem and its encoding as a Constraint Satisfaction Problem. We also propose establishing hyperarc consistency as a preprocessing step in a CP platform, thus obtaining an efficient programming tool to be used especially in the case where specialized algorithms are not applicable (i.e.,in cases where side-constraints are encompassed). The efficiency of our approach is then highlighted by a series of computational results. Last, a multi-sided stable matching configuration is examined; the participating agents are considered to be part of a specialized one-to-one Supply Chain Network (SCN). Under our specialized setting, we prove that every such k-sided SCN can be decomposed into k-1 independent SM sub-markets. Moreover, extending known results on the CSN problem, we show that the set of chain stable networks forms a distributive lattice with respect to the meet and join operations, while intermediary- optimal solutions always exist. Furthermore, we define the notion of contract-rotations, i.e., an extension of rotations, and illustrate that a series of algorithms proposed for the SM problem can be easily extended in our specialized setting.
Optimization methods for complex vehicle routing and scheduling problems
Repoussis, Panagiotis P.; Athens University of Economics and Business, Department of Management Science and Technology; Tarantilis, Christos D.; Prastacos, Gregory P.; Ioannou, George
This dissertation is entitled \Optimization Methods for Complex Vehicle Routing and Scheduling problems". The term \optimization methods" refers to hybrid methodologies that combine heuristic and metaheuristic algorithms to produce effective and robust solution methods for combinatorial optimization problems. The term \complex" denotes the computational complexity and the large-scale nature of the problems considered. Finally, the term \vehicle routing and scheduling problems" describes a subclass of problems emanating from the broader family of Vehicle Routing Problems (VRP). The VRP is the problem of finding a set of optimal routes for a fleet of vehicles to serve a given set of customers. The vehicles are often assumed to have a common home base, called the depot. The cost of traveling between each pair of customers and between the depot and each customer is given. The goal is to find the optimum \assignment" and service \schedule" of customers for each vehicle route, such that the total traveling cost is minimized and all customers are served by exactly one vehicle. Typically the solution has to satisfy several other restrictions, such as total capacity of vehicles, route durations and other operational constraints. In this thesis, the term VRP is used to describe a broad class of problems and not a specific problem with a limited set of restrictions or constraints; thus, in the remainder of the thesis the term VRP includes all problems that involve creating one or more routes, starting and ending in one or more common depots or at predefined start and end terminals, in contrast to most archival literature where VRP is mainly used for the Capacitated Vehicle Routing Problem (CVRP). A subclass of VRPs is the Vehicle Routing Problem with Time Windows (VRPTW); this is the core problem studied in this thesis along with its variants. In the VRPTW, a desired visit time (time window) at each customer is given. Also, a number of additional constraints are often enforced, e.g. heterogeneous fleets of vehicles, open routes, multiple depots, etc. The VRPTW is a classical and well-studied vehicle routing problem. It is an NP-hard combinatorial optimization problem that has attracted the interest of both researchers and practitioners. For many of the problem instances considered in this thesis, the set of feasible solutions is so large that even if we had a computer that in a systematic way could construct and evaluate the cost of a trillion (1012) solutions per second, and we had started that computer right after the big bang, 14 billion years ago, it would still not have evaluated all the feasible solutions today. Consequently we have to resort to other methods and forget simple enumeration. Engineering and technology have been continuously providing examples of difficult optimization problems, with practical as well as theoretical importance. Optimization problems are concerned with the search for the \best" configuration of a set of variables to achieve some goals. A huge collection of optimization techniques has been suggested by several researchers from different fields; an immense number of refinements has made these techniques work for specific types of applications. All these procedures are based on some common ideas, which are being characterized by additional specific features. However, for most optimization problems no procedure is known, in general, to get directly an \optimal" solution. Three types of solution methods are typically employed to solve problems such as the VRPTW: Heuristics, Approximate Algorithms and Exact Methods. Heuristics are solution methods that relatively quickly can _nd a feasible solution with reasonable quality. Approximation algorithms are special heuristics that can provide a solution and an errorquality guarantee. Exact methods guarantee that the optimal solution is found subject to sufficient time and memory space. Although in recent years significant algorithmic achievements have been reached and highly sophisticated exact methods have been proposed, heuristics remain the only reliable and viable approach for the solution of practical large-scale instances. Towards this end, a special class of heuristics that has received special attention during the last two decades is the so-called metaheuristics. Such algorithms provide general frameworks for heuristics that can be applied to different problems, while high quality solutions are often obtained within reasonable computational burdens. This PhD thesis focuses on the exploration of the computational power of metaheuristics, not only in terms of solving effectively and efficiently the VRPTW and other real-life industrial variants of the problem in a limited amount of time, but also developing cooperative and competitive optimization methods that are characterized by simplicity, exibility and robustness. The problems studied have been inspired from real-world applications and the last part of the thesis describes the application of some of the solution methods developed in a real-life industrial environment.

Περιήγηση

Πλοήγηση Διδακτορικές διατριβές ανά Θέμα "Algorithms"