Reliable single allocation hub location problem under hub breakdowns

The design of hub-and-spoke transport networks is a strategic planning problem, as the choice of hub locations has to remain unchanged for long time periods. However, strikes, disasters or traffic breakdown can lead to the unavailability of a hub for a short period of time. Therefore it is important to consider such events already in … Read more

A Robust Approach to the Capacitated Vehicle Routing Problem with Uncertain Costs

We investigate a robust approach for solving the Capacitated Vehicle Routing Problem (CVRP) with uncertain travel times. It is based on the concept of K-adaptability, which allows to calculate a set of k feasible solutions in a preprocessing phase before the scenario is revealed. Once a scenario occurs, the corresponding best solution may be picked … Read more

Solving the Probabilistic Traveling Salesman Problem by Linearising a Quadratic Approximation

The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The … Read more

Solving Classical and New Single Allocation Hub Location Problems on Euclidean Data

Transport networks with hub structure organise the exchange of shipments between many sources and sinks. All sources and sinks are connected to a small number of hubs which serve as transhipment points, so that only few, strongly consolidated transport relations exist. While hubs and detours lead to additional costs, the savings from bundling shipments, i.e. … Read more

A Versatile Heuristic Approach for Generalized Hub Location Problems

The usability of hub location models heavily depends on an appropriate modelling approach for the economies of scale. Realistic hub location models require more sophisticated transport cost structures than the traditional flow-independent discount. We develop a general modelling scheme for such problems allowing the definition of complicated (non-linear) costs and constraints; its structure allows an … Read more

Lower Bounding Procedures for the Single Allocation Hub Location Problem

This paper proposes a new lower bounding procedure for the Uncapacitated Single Allocation p-Hub Median Problem based on Lagrangean relaxation. For solving the resulting Lagrangean subproblem, the given problem structure is exploited: it can be decomposed into smaller subproblems that can be solved efficiently by combinatorial algorithms. Our computational experiments for some benchmark instances demonstrate … Read more

A Compact Linearisation of Euclidean Single Allocation Hub Location Problems

Hub location problems are strategic network planning problems. They formalise the challenge of mutually exchanging shipments between a large set of depots. The aim is to choose a set of hubs (out of a given set of possible hubs) and connect every depot to a hub so that the total transport costs for exchanging shipments … Read more