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

• Applicants: Professor Dr. Christoph Buchheim; Professor Dr.-Ing. Uwe Clausen
• Subject Area: Traffic and Transport Systems, Intelligent and Automated Traffic
• Term: from 2011 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 201197672

The topic of hub location problems is the strategic planning of transport networks: A number of depots aim to exchange shipments. Establishing direct connections from every depot to every other depot is too expensive, so that a set of locations is chosen as hubs; each shipment is routed from source to sink through one or two hubs. This approach pays off if the savings from transport bundling outweigh the additional costs of building and maintaining hubs. Today, twenty five years after the beginning of hub location research, the strategic planning of transport networks is still challenging. The simplified models of the eighties can be solved by contemporary methods because they use a linearized cost structure: A fixed cost factor per ton and kilometer is applied, which is reduced by a predefined percentage on hub-hub connections. This often leads to a low capacity utilization of vehicles. Furthermore, the classic models assume that all data is known precisely and all variation or disturbance is ignored.Application-related models require much more research. In the first project phase we made substantial progress on the integration of complex transport cost functions into the models. The close cooperation of both project partners lead to the development of heuristic and exact optimization algorithms. They generate good results even for large, realistic problem sizes. The developed quadratic optimization methods are especially successful on single allocation problems, in which the shipments are sent to the hub without prior sorting (like postal problems). Essential for the usability of the discussed models is the extension from deterministic to stochastic data. Real transport volumes and transport times are not known in advance and hub breakdowns can disrupt a badly planned network considerably. In the new project phase, we will construct stochastic and robust models and solve them by heuristic and exact optimization algorithms. The focus lies on single allocation problems because our successful preliminary work enables us to produce really substantiated results.With this extension project we want to contribute to solving application-related transport planning problems, but also extend the algorithmic and mathematical knowledge, particularly about the combination of quadratic optimization techniques with stochastic influences.

• DFG Programme: Research Grants