Mixed-Integer Programming for Capacitated Logistics Network Design

这笔赠款提供资金，用于开发有效和高效的方法，以解决大规模有能力的物流网络设计和路线问题。解决网络设计和路由问题的一个主要障碍是它们的混合整数规划模型的线性松弛的边界相当弱。为了加强这些边界，将通过对通用网络设计多面体的严格分析来开发强割平面。所采取的方法将是利用存在于大类物流网络设计和路线选择问题中的公共子结构，而不对网络的拓扑结构和能力的具体特征做出任何假设。将开发利用这些网络子结构的通用原始启发式算法。我们将在一大类物流问题上进行大量的计算实验，以测试该方法的可行性。该项目最重要的成果之一将是开发出一种智能的下一代混合整数求解器，它将自动识别混合整数规划问题的网络设计和布线子结构，并使用本项目中开发的方法来开发这些子结构。如果成功，这项研究将大大提高我们解决以容量网络设计问题为子结构的大类混合整数规划问题的能力。由于许多电信和交通网络规划、车辆/乘务路径选择和调度、生产和分配、设施选址和容量分配问题都是容量受限网络设计和路径选择问题的变体，因此该项目的结果将对许多行业产生重大影响。

This grant provides funding for the development of effective and efficient methodologies for solving large-scale capacitated logistics network design and routing problems. A major obstacle in solving network design and routing problems is that the bounds from the linear relaxations of their mixed-integer programming models are quite weak. In order to strengthen these bounds, strong cutting planes will be developed through rigorous analysis of generic network design polyhedra. The approach taken will beto exploit common substructures that exist in large classes of logistics network design and routing problems without making any assumptions on the topology of the network and the specific characteristics of thecapacities. Generic primal heuristics that make use of these network substructures will be developed. Extensive computational experiments will be performed on a large class of logistics problems to test the viability of the approach.One of the most important outcomes of the project will be the development of an intelligent next-generation mixed-integer solver that will automatically identify the network design and routing substructures of mixed-integer programming problems and employ the methods developed in this project to exploit these substructures. If successful, this research project will significantly advance our capabilities in solving large classes of mixed-integer programming problems that have capacitated network design problem as a substructure. Since many telecommunication and transportation network planning, vehicle/crew routing and scheduling, production and distribution, facility location and capacity allocation problems are variations of capacitated network design and routing problems, the results of the project are expected to have a significant impact on many industries.