## 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING

### Refine

#### Document Type

- Doctoral Thesis (2)
- Diploma Thesis (1)
- Preprint (1)

#### Keywords

- Hub-and-Spoke-System (1)
- Polyhedron (1)
- integer programming (1)
- intermediate stops (1)
- large neighborhood search (1)
- metaheuristics (1)
- path relinking (1)
- personnel scheduling (1)
- physicians (1)
- reverse logistics (1)

#### Faculty / Organisational entity

This thesis addresses several challenges for sustainable logistics operations and investigates (1) the integration of intermediate stops in the route planning of transportation vehicles, which especially becomes relevant when alternative-fuel vehicles with limited driving range or a sparse refueling infrastructure are considered, (2) the combined planning of the battery replacement infrastructure and of the routing for battery electric vehicles, (3) the use of mobile load replenishment or refueling possibilities in environments where the respective infrastructure is not available, and (4) the additional consideration of the flow of goods from the end user in backward direction to the point of origin for the purpose of, e.g., recapturing value or proper disposal. We utilize models and solution methods from the domain of operations research to gain insights into the investigated problems and thus to support managerial decisions with respect to these issues.

This paper presents a case study of duty rostering for physicians at a department of orthopedics and trauma surgery. We provide a detailed description of the rostering problem faced and present an integer programming model that has been used in practice for creating duty rosters at the department for more than a year. Using real world data, we compare the model output to a manually generated roster as used previously by the department and analyze the quality of the rosters generated by the model over a longer time span. Moreover, we demonstrate how unforeseen events such as absences of scheduled physicians are handled.

We introduce and investigate a product pricing model in social networks where the value a possible buyer assigns to a product is influenced by the previous buyers. The selling proceeds in discrete, synchronous rounds for some set price and the individual values are additively altered. Whereas computing the revenue for a given price can be done in polynomial time, we show that the basic problem PPAI, i.e., is there a price generating a requested revenue, is weakly NP-complete. With algorithm Frag we provide a pseudo-polynomial time algorithm checking the range of prices in intervals of common buying behavior we call fragments. In some special cases, e.g., solely positive influences, graphs with bounded in-degree, or graphs with bounded path length, the amount of fragments is polynomial. Since the run-time of Frag is polynomial in the amount of fragments, the algorithm itself is polynomial for these special cases. For graphs with positive influence we show that every buyer does also buy for lower prices, a property that is not inherent for arbitrary graphs. Algorithm FixHighest improves the run-time on these graphs by using the above property.
Furthermore, we introduce variations on this basic model. The version of delaying the propagation of influences and the awareness of the product can be implemented in our basic model by substituting nodes and arcs with simple gadgets. In the chapter on Dynamic Product Pricing we allow price changes, thereby raising the complexity even for graphs with solely positive or negative influences. Concerning Perishable Product Pricing, i.e., the selling of products that are usable for some time and can be rebought afterward, the principal problem is computing the revenue that a given price can generate in some time horizon. In general, the problem is #P-hard and algorithm Break runs in pseudo-polynomial time. For polynomially computable revenue, we investigate once more the complexity to find the best price.
We conclude the thesis with short results in topics of Cooperative Pricing, Initial Value as Parameter, Two Product Pricing, and Bounded Additive Influence.

A hub location problem consists of locating p hubs in a network in order to collect and consolidate flow between node pairs. This thesis deals with the uncapacitated single allocation p-hub center problem (USApHCP) as a special type of hub location problem with min max objective function. Using the so-called radius formulation of the problem, the dimension of the polyhedron of USApHCP is derived. The formulation constraints are investigated to find out which of these define facets. Then, three new classes of facet-defining inequalities are derived. Finally, efficient procedures to separate facets in a branch-and-cut algorithm are proposed. The polyhedral analysis of USApHCP is based on a tight relation to the uncapacitated facility location problem (UFL). Hence, many results stated in this thesis also hold for UFL.