CAREER: Efficient Network Design and Routing Algorithms for Logistics and Communications Networks

职业：物流和通信网络的高效网络设计和路由算法

• 批准号: 0238815
• 负责人: Ozlem Ergun
• 金额: $ 40万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-02-01 至 2010-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0238815&HistoricalAwards=false
• 关键词: CAREER; Efficient; Network; Design; Routing

The primary goal of this Faculty Early Career Development (CAREER) Program research project is to develop state-of-the-art fast solution methodologies that generate high quality solutions for complex problems in designing and managing logistics and communications networks. Real-world communications and logistics problems are large-scale, time sensitive, and coupled with side constraints that further contribute to the hardness of underlying mathematical structures. The specific tasks that will be undertaken for achieving the goal of this project include: understanding the applications in detail, analyzing the underlying mathematical structures, and evaluating the various solution approaches through computational testing. A logistics network rarely functions as planned due to external factors such as unscheduled delays or dynamically changing customer demand. The main thrust of the proposal is a study on techniques for augmenting a given solution in order to incorporate a disruption to a large-scale system. In the literature, these types of problems are usually solved by extracting a subset of the problem through preprocessing and then re-solving this smaller problem. This research, proposes to develop techniques that consider a large part of the problem by designing auxiliary networks together with fast augmentation algorithms that find near optimal solutions in almost real-time. Also, two important network design and routing problems related to: (i) identifying synergies in a collaborative logistics network, and (ii) routing multiple packets on partially disjoint paths over a communications network, will be studied as collaborative research projects. With the advancement of globalization and new technologies in telecommunications, not only does the importance of solving network problems keep growing but also this task is becoming harder to accomplish efficiently. For example, global trade has created logistics networks that span several continents, and the possibility of real-time multi-media communications introduced network problems that need to be solved in less than a second. To face this challenge, it is necessary to employ fast approximation (heuristic) algorithms that try to find good solutions rather than identify an optimal one. This research plan proposes (i) to study fast heuristic techniques for generating close to optimal solutions for large-scale and time-sensitive logistics and communications network applications that are implementable in practice and (ii) to further the theoretical understanding of problems arising from these applications.

该教师早期职业发展（CAREER）计划研究项目的主要目标是开发最先进的快速解决方案方法，为设计和管理物流和通信网络中的复杂问题提供高质量的解决方案。 现实世界的通信和物流问题是大规模的，时间敏感的，并与侧约束，进一步有助于底层的数学结构的硬度。 为实现本项目的目标，将承担的具体任务包括：详细了解应用程序，分析底层数学结构，并通过计算测试评估各种解决方案。由于外部因素，如计划外的延迟或动态变化的客户需求，物流网络很少按计划运行。该提案的主旨是研究扩大特定解决方案的技术，以便将破坏纳入大规模系统。在文献中，这些类型的问题通常通过预处理提取问题的子集，然后重新解决这个较小的问题来解决。这项研究，建议开发技术，考虑了很大一部分的问题，通过设计辅助网络与快速增强算法，几乎实时找到接近最优的解决方案。此外，两个重要的网络设计和路由问题有关：（一）确定协同作用的协同物流网络，和（二）路由多个数据包的部分不相交的路径上的通信网络，将作为合作研究项目进行研究。 随着全球化和电信新技术的发展，不仅解决网络问题的重要性不断增加，而且这项任务也变得越来越难以有效地完成。 例如，全球贸易创造了跨越几大洲的物流网络，实时多媒体通信的可能性带来了需要在不到一秒钟内解决的网络问题。面对这一挑战，有必要采用快速近似（启发式）算法，试图找到好的解决方案，而不是确定一个最佳的。本研究计划提出：（i）研究快速启发式技术，为可在实践中实施的大规模和时间敏感的物流和通信网络应用程序生成接近最优的解决方案;（ii）进一步从理论上理解这些应用程序中出现的问题。