### Refine

#### Document Type

- Report (5)
- Preprint (3)
- Diploma Thesis (1)

#### Keywords

- hub location (9) (remove)

#### Faculty / Organisational entity

On the Complexity of the Uncapacitated Single Allocation p-Hub Median Problem with Equal Weights
(2007)

The Super-Peer Selection Problem is an optimization problem in network topology construction. It may be cast as a special case of a Hub Location Problem, more exactly an Uncapacitated Single Allocation p-Hub Median Problem with equal weights. We show that this problem is still NP-hard by reduction from Max Clique.

Using covering problems (CoP) combined with binary search is a well-known and successful solution approach for solving continuous center problems. In this thesis, we show that this is also true for center hub location problems in networks. We introduce and compare various formulations for hub covering problems (HCoP) and analyse the feasibility polyhedron of the most promising one. Computational results using benchmark instances are presented. These results show that the new solution approach performs better in most examples.

In contrast to p-hub problems with a summation objective (p-hub median), minmax hub problems (p-hub center) have not attained much attention in the literature. In this paper, we give a polyhedral analysis of the uncapacitated single allocation p-hub center problem (USApHCP). The analysis will be based on a radius formulation which currently yields the most efficient solution procedures. We show which of the valid inequalities in this formulation are facet-defining and present non-elementary classes of facets, for which we propose separation problems. A major part in our argumentation will be the close connection between polytopes of the USApHCP and the uncapacitated p-facility location (pUFL). Hence, the new classes of facets can also be used to improve pUFL formulations.

Using covering problems (CoP) combined with binary search is a well-known and successful solution approach for solving continuous center problems. In this paper, we show that this is also true for center hub location problems in networks. We introduce and compare various formulations for hub covering problems (HCoP) and analyse the feasibility polyhedron of the most promising one. Computational results using benchmark instances are presented. These results show that the new solution approach performs better in most examples.

We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet defining. We show its superior computational performance by benchmarking it on a well known data set.

Given a public transportation system represented by its stops and direct connections between stops, we consider two problems dealing with the prices for the customers: The fare problem in which subsets of stops are already aggregated to zones and "good" tariffs have to be found in the existing zone system. Closed form solutions for the fare problem are presented for three objective functions. In the zone problem the design of the zones is part of the problem. This problem is NP hard and we therefore propose three heuristics which prove to be very successful in the redesign of one of Germany's transportation systems

We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet–defining. We show its superior computational performance by benchmarking it on a well known data set.

In this paper, a new mixed integer mathematical programme is proposed for the application of Hub Location Problems (HLP) in public transport planning. This model is among the few existing ones for this application. Some classes of valid inequalities are proposed yielding a very tight model. To solve instances of this problem where existing standard solvers fail, two approaches are proposed. The first one is an exact accelerated Benders decomposition algorithm and the latter a greedy neighborhood search. The computational results substantiate the superiority of our solution approaches to existing standard MIP solvers like CPLEX, both in terms of computational time and problem instance size that can be solved. The greedy neighborhood search heuristic is shown to be extremely efficient.

In this paper, we are going to propose the first mathematical model for Multi- Period Hub Location Problems (MPHLP). We apply this mixed integer program- ming model on public transport planning and call it Multi-Period Hub Location Problem for Public Transport (MPHLPPT). In fact, HLPPT model proposed earlier by the authors is extended to include more facts and features of the real-life application. In order to solve instances of this problem where existing standard solvers fail, a solution approach based on a greedy neighborhood search is developed. The computational results substantiate the efficiency of our solution approach to solve instances of MPHLPPT.