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)在通信网络上的部分不相交路径上对多个分组进行路由。随着全球化和电信新技术的发展，不仅解决网络问题的重要性不断增加，而且这项任务也越来越难以有效地完成。例如，全球贸易创造了跨越几个大洲的物流网络，实时多媒体通信的可能性带来了需要在不到一秒的时间内解决的网络问题。为了应对这一挑战，有必要使用快速近似(启发式)算法，试图找到好的解决方案，而不是确定最优的解决方案。这项研究计划建议(I)研究快速启发式技术，以便为可在实践中实施的大规模和时间敏感型物流和通信网络应用生成接近最优的解决方案，以及(Ii)加深对这些应用所产生的问题的理论理解。