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

枢纽选址问题的主题是运输网络的战略规划：许多仓库的目标是交换货物。建立从每个仓库到每个其他仓库的直接连接成本太高，因此选择一组地点作为枢纽；每批货物都通过一个或两个枢纽从来源发送到下沉。如果捆绑运输节省的成本超过了建设和维护枢纽的额外成本，这种方法就会得到回报。在枢纽选址研究开始25年后的今天，交通网络的战略规划仍然具有挑战性。八十年代的简化模型可以用当代的方法解决，因为它们使用了线性化的成本结构：采用了每吨和公里的固定成本系数，在枢纽-枢纽连接上按预定的百分比减少。这往往导致车辆的运力利用率较低。此外，经典模型假定所有数据都是精确已知的，忽略了所有的变化或干扰。与应用相关的模型需要更多的研究。在第一个项目阶段，我们在将复杂的运输成本函数纳入模型方面取得了实质性进展。两个项目合作伙伴的密切合作导致了启发式和精确优化算法的发展。即使对于大的、现实的问题规模，它们也会产生良好的结果。所开发的二次优化方法在单分配问题上尤其成功，在该问题中，货物在没有事先分拣的情况下被发送到枢纽(如邮政问题)。所讨论的模型的可用性的关键是从确定性数据到随机数据的扩展。实际的运输量和运输时间是事先不知道的，枢纽故障可能会严重扰乱规划不善的网络。在新的项目阶段，我们将构建随机和稳健的模型，并使用启发式和精确优化算法进行求解。重点放在单个分配问题上，因为我们成功的前期工作使我们能够产生真正确凿的结果。通过这个扩展项目，我们希望为解决与应用相关的交通规划问题做出贡献，同时也扩展了算法和数学知识，特别是关于具有随机影响的二次优化技术的组合。

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.