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

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

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. ***