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 the 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 from source to the sink depot through one or two hubs to bundle shipments and thus 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.

Procedure

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 the first step, stochastic and robust models, which represent reality as much as possible, are constructed. According to 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 the 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.

Targeted results

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. 

Contact: Prof. Dr.-Ing. Uwe Clausen

Funding and partners

Prof. Dr. Christoph Buchheim
Chair of Discrete Optimization
Department of Mathematics
TU Dort­mund Uni­ver­sity