Events Calendar

A Branch-and-Cut Approach for the Vehicle Routing Problems with Time Windows

Daniel J. Epstein Department of Industrial and Systems Engineering Seminar: "A Branch-and-Cut Approach for the Vehicle Routing Problems with Time Windows"Dr. Jonathan F. BardGraduate Program in Operations Research and Industrial Engineering, Department of Mechanical Engineering, The University of Texas, Austin, TexasABSTRACT: Many routing and scheduling problems have similar characteristics: they have an underlying network structure, they can be modeled as mixed-integer linear programs, the models contain a large number of variables and an exponential number of constraints, and they are NP-hard. This talk focuses on a representative problem in this class where the objective is to find the minimum number of vehicles required to visit a set of customers, subject to time window and capacity constraints. It is assumed that the fleet is homogeneous, is located at a common depot, and that each customer requires the same type of service. An exact solution methodology is described based on branch and cut. In the computations, increasing lower bounds on the optimal solution are obtained by solving a series of relaxed problems that incorporate newly found valid inequalities. Feasible solutions or upper bounds are obtained with several methods including a greedy randomized adaptive search procedure (GRASP). A wide variety of cuts are introduced to tighten the linear programming (LP) relaxation of the original mixed-integer program. To find violated cuts, it is necessary to solve a corresponding separation problem. A substantial portion of the solution methodology revolves around the use of efficient procedures developed for this purpose. A new approach for obtaining feasible solutions from the LP relaxation is also discussed. The computational results indicate that a large number of the standard 50- and 100-node benchmark problems can be solved in a short amount of time.TUESDAY, MAY 8, 2007, GERONTOLOGY BUILDING (GER) ROOM 309, 10:00 – 11:00 AM

Location: Ethel Percy Andrus Gerontology Center (GER) - 309

Audiences: Everyone Is Invited

Contact: Georgia Lum