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.

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