Mixed-Integer Programming for Capacitated Logistics Network Design

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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 be to 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 the capacities. 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.