权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

基于二次优化的不确定且与时间相关的枢纽位置问题的精确启发式算法

基本信息

批准号：
201197672
负责人：
Professor Dr. Christoph Buchheim
金额：
--
依托单位：
Institut für Transportlogistik (ITL)
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2011
资助国家：
德国
起止时间：
2010-12-31 至 2019-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/201197672?language=en
关键词：
Exact heuristic algorithms uncertain time

项目摘要

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.

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