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

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

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.