Mixed-Integer Programming for Capacitated Logistics Network Design

容量物流网络设计的混合整数规划

• 批准号: 0070127
• 负责人: Alper Atamturk
• 金额: $ 33.46万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0070127&HistoricalAwards=false
• 关键词: Mixed; Integer; Programming; Capacitated; Logistics

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.

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