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