Fachbereich / Organisatorische Einheit
- Fachbereich Mathematik (48) (entfernen)
- Universal Shortest Paths (2010)
- We introduce the universal shortest path problem (Univ-SPP) which generalizes both - classical and new - shortest path problems. Starting with the definition of the even more general universal combinatorial optimization problem (Univ-COP), we show that a variety of objective functions for general combinatorial problems can be modeled if all feasible solutions have the same cardinality. Since this assumption is, in general, not satisfied when considering shortest paths, we give two alternative definitions for Univ-SPP, one based on a sequence of cardinality contrained subproblems, the other using an auxiliary construction to establish uniform length for all paths between source and sink. Both alternatives are shown to be (strongly) NP-hard and they can be formulated as quadratic integer or mixed integer linear programs. On graphs with specific assumptions on edge costs and path lengths, the second version of Univ-SPP can be solved as classical sum shortest path problem.
- On the Generality of the Greedy Algorithm for Solving Matroid Base Problems (2013)
- It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or \(k\)-sum objective functions.
- Hierarchical Edge Colorings and Rehabilitation Therapy Planning in Germany (2014)
- In this paper we give an overview on the system of rehabilitation clinics in Germany in general and the literature on patient scheduling applied to rehabilitation facilities in particular. We apply a class-teacher model developed to this environment and then generalize it to meet some of the specific constraints of inpatient rehabilitation clinics. To this end we introduce a restricted edge coloring on undirected bipartite graphs which is called group-wise balanced. The problem considered is called patient-therapist-timetable problem with group-wise balanced constraints (PTTPgb). In order to specify weekly schedules further such that they produce a reasonable allocation to morning/afternoon (second level decision) and to the single periods (third level decision) we introduce (hierarchical PTTPgb). For the corresponding model, the hierarchical edge coloring problem, we present some first feasibility results.
- Transit Dependent Evacuation Planning for Kathmandu Valley: A Case Study (2014)
- Due to the increasing number of natural or man-made disasters, the application of operations research methods in evacuation planning has seen a rising interest in the research community. From the beginning, evacuation planning has been highly focused on car-based evacuation. Recently, also the evacuation of transit depended evacuees with the help of buses has been considered. In this case study, we apply two such models and solution algorithms to evacuate a core part of the metropolitan capital city Kathmandu of Nepal as a hypothetical endangered region, where a large part of population is transit dependent. We discuss the computational results for evacuation time under a broad range of possible scenarios, and derive planning suggestions for practitioners.
- Stop Location Design in Public Transportation Networks: Covering and Accessibility Objectives (2006)
- In StopLoc we consider the location of new stops along the edges of an existing public transportation network. Examples of StopLoc include the location of bus stops along some given bus routes or of railway stations along the tracks in a railway system. In order to measure the ''convenience'' of the location decision for potential customers in given demand facilities, two objectives are proposed. In the first one, we give an upper bound on reaching a closest station from any of the demand facilities and minimize the number of stations. In the second objective, we fix the number of new stations and minimize the sum of the distances between demand facilities and stations. The resulting two problems CovStopLoc and AccessStopLoc are solved by a reduction to a classical set covering and a restricted location problem, respectively. We implement the general ideas in two different environments - the plane, where demand facilities are represented by coordinates and in networks, where they are nodes of a graph.
- A Finite Dominating Set Algorithm for a Dynamic Location Problem in the Plane (2014)
- A single facility problem in the plane is considered, where an optimal location has to be identified for each of finitely many time-steps with respect to time-dependent weights and demand points. It is shown that the median objective can be reduced to a special case of the static multifacility median problem such that results from the latter can be used to tackle the dynamic location problem. When using block norms as distance measure between facilities, a Finite Dominating Set (FDS) is derived. For the special case with only two time-steps, the resulting algorithm is analyzed with respect to its worst-case complexity. Due to the relation between dynamic location problems for T time periods and T-facility problems, this algorithm can also be applied to the static 2-facility location problem.
- Sink Location to Find Optimal Shelters in Evacuation Planning (2014)
- The sink location problem is a combination of network flow and location problems: From a given set of nodes in a flow network a minimum cost subset \(W\) has to be selected such that given supplies can be transported to the nodes in \(W\). In contrast to its counterpart, the source location problem which has already been studied in the literature, sinks have, in general, a limited capacity. Sink location has a decisive application in evacuation planning, where the supplies correspond to the number of evacuees and the sinks to emergency shelters. We classify sink location problems according to capacities on shelter nodes, simultaneous or non-simultaneous flows, and single or multiple assignments of evacuee groups to shelters. Resulting combinations are interpreted in the evacuation context and analyzed with respect to their worst-case complexity status. There are several approaches to tackle these problems: Generic solution methods for uncapacitated problems are based on source location and modifications of the network. In the capacitated case, for which source location cannot be applied, we suggest alternative approaches which work in the original network. It turns out that latter class algorithms are superior to the former ones. This is established in numerical tests including random data as well as real world data from the city of Kaiserslautern, Germany.
- Integrated Scheduling and Location Models: Single Machine Makespan Problems (2002)
- Scheduling and location models are often used to tackle problems in production, logistics, and supply chain management. Instead of treating these models independent of each other, as is usually done in the literature, we consider in this paper an integrated model in which the locations of machines define release times for jobs. Polynomial solution algorithms are presented for single machine problems in which the scheduling part can be solved by the earliest release time rule.
- The Multi Terminal q-FlowLoc Problem: A Heuristic (2011)
- In this paper the multi terminal q-FlowLoc problem (q-MT-FlowLoc) is introduced. FlowLoc problems combine two well-known modeling tools: (dynamic) network flows and locational analysis. Since the q-MT-FlowLoc problem is NP-hard we give a mixed integer programming formulation and propose a heuristic which obtains a feasible solution by calculating a maximum flow in a special graph H. If this flow is also a minimum cost flow, various versions of the heuristic can be obtained by the use of different cost functions. The quality of this solutions is compared.
- Earliest Arrival Flows with Time-Dependent Data (2003)
- In this paper we discuss an earliest arrival flow problem of a network having arc travel times and capacities that vary with time over a finite time horizon T. We also consider the possibility to wait (or park) at a node before departingon outgoing arc. This waiting is bounded by the value of maximum waiting time and the node capacity which also vary with time.