Jump label

Service navigation

Main navigation

You are here:

Main content

Exact and heuristic algorithms for uncertain and time-dependent hub location problems based on quadratic optimization

Background

The strategic planning of transportation networks is an important issue for logistics service providers due to the growing internationalization, rising freight traffic and intensified competitive situation. In transportation networks a number of depots aim to mutually exchange shipments. Since establishing direct connections is too cost-intensive, hubs are constructed at some locations. Then each shipment is routed form source to sink depot through one or two hubs to bundle shipments and thus to save transport costs. The task of the hub location problem is to choose hubs, in such a way that the sum of hub construction costs and transport costs is minimized.

The research project focuses on the single allocation variant of the hub location problem, where the shipments are transported without prior sorting from the depot to a chosen hub. This variant has an inherent quadratic structure.

Even today after 25 years of research on the hub location problem, the strategic planning of transportation networks is still challenging. All previous models expect deterministic data for transport volume and transport times. Real data is not known in advance and can only be estimated approximately. Furthermore, disruptions like a hub breakdown have not been considered.

 

Aims

The aim of the research project is to examine the hub location problem under stochastic influences. The focus is on the construction of stochastic and robust models for the single allocation hub location problem. The models will be solved by heuristic and exact algorithms.

To the best of our knowledge quadratic optimization under stochastic influences has not been considered yet in literature. Thus, our research project is also interesting from a more general mathematical point of view. 

 

Approach

The research project is divided into eight working packages:

  1. Analysis of the uncertainty in hub location problems
  2. Construction of robust and stochastic models
  3. Quadratic optimization techniques for uncertain shipping volumes and costs
  4. Meta-heuristic procedures for models with non-linear structure
  5. Combination of heuristic and exact methods
  6. Hedging against hub breakdown
  7. Time-expanded models and stochastic travel times
  8. Solution evaluation by event-driven computer simulation

In a first step, stochastic and robust models, which represent the reality as much as possible, are constructed. According the stochastic models, exact and heuristic optimization algorithms are developed. Furthermore, the robustness of the models, for instance with respect to a breakdown of a hub, is examined. In a final step, the suitability for practice of the models is reviewed by an event-driven computer simulation. During the research project there will be a close collaboration with the group for discrete optimization of the Faculty for Mathematics at TU Dortmund University.

Contact: Prof. Dr.-Ing. Uwe Clausen

Partner

DFG Deutsche Forschungsgemeinschaft
Prof. Dr. Christoph Buchheim
Lehrstuhl für Diskrete Optimierung (LSV)
Fakultät für Mathematik
Technische Universität Dortmund