SGER: The Theory, Algorithms, and Applications of Network Flows Integrated with the World Wide Web

SGER：与万维网集成的网络流的理论、算法和应用

• 批准号: 9810359
• 负责人: James Orlin
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-06-01 至 1999-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9810359&HistoricalAwards=false
• 关键词: SGER; Theory; Algorithms; Applications; Network

9810359 Orlin This grant provides funding to develop, implement, and experimentally test a new neighborhood search heuristic for solving a broad class of partitioning problems. These partitioning problems are typically characterized by a two-phase decision process. In the first phase, a set of objects is partitioned into clusters; in the second phase, each cluster is sequenced or configured optimally. The decision problem is to partition the set of objects into clusters so that the sum of the costs of optimal configurations within clusters is minimum. Examples of partitioning problems include: vehicle routing problems, multi-facility location problems, clustering problems in statistics, parallel machine scheduling problems, telecommunications network design problems, nurse scheduling, exam scheduling, and various other scheduling problems. This grant will develop the cyclic exchange neighborhood search technique. Neighborhood search techniques seek out improvements in a solution by making small changes to the solution. In the cyclic exchange neighborhood approach, items may shifted between multiple clusters. Algorithmic approaches, analyses, test cases, and software will be developed and will be made freely available to other researchers via the World Wide Web. Algorithm animations will be provided to help users visualize algorithms. In addition, outside users will be able to submit problems for solution at the web site. If successful, the results of this research will lead to more effective heuristic algorithms for solving several types of partitioning problems. Moreover, this research will provide a unified approach for solving partitioning problems that can be specialized to various problem types easily. Many of the subroutines for this generic approach can be reused. The web site will also provide software, algorithm animations, and test cases that will facilitate the development of algorithms for partitioning problems by other researchers. ***

9810359 orlin这笔资金用于开发、实施和实验测试一种新的邻域搜索启发式算法，用于解决广泛类别的划分问题。这些划分问题通常以两阶段决策过程为特征。在第一阶段，将一组对象划分为多个簇；在第二阶段，对每个簇进行排序或优化配置。决策问题是将对象集划分为集群，以便集群内最优配置的成本之和最小。划分问题的例子包括：车辆路线问题、多设施选址问题、统计学中的集群问题、并行机调度问题、电信网络设计问题、护士调度、考试调度以及各种其他调度问题。这笔赠款将发展循环交换邻域搜索技术。邻里搜索技术通过对解决方案进行微小的更改来寻求解决方案的改进。在循环交换邻域方法中，项可以在多个集群之间移动。将开发算法方法、分析、测试用例和软件，并将通过万维网免费提供给其他研究人员。将提供算法动画来帮助用户可视化算法。此外，外部用户将能够在网站上提交问题以寻求解决方案。如果成功，本研究的结果将导致更有效的启发式算法来解决几种类型的划分问题。此外，本研究将提供一种解决划分问题的统一方法，该方法可以很容易地专门用于各种问题类型。这种通用方法的许多子例程都可以重复使用。该网站还将提供软件、算法动画和测试案例，以促进其他研究人员开发划分问题的算法。***