Solving a truck dispatching scheduling problem using branch-and-cut

Solving a truck dispatching scheduling problem using branch-and-cut

0.00 Avg rating0 Votes
Article ID: iaor19992004
Country: United States
Volume: 46
Issue: 3
Start Page Number: 355
End Page Number: 367
Publication Date: May 1998
Journal: Operations Research
Authors: ,
Keywords: vehicle routing & scheduling
Abstract:

A branch-and-cut integer programming solver is developed for a class of structured 0/1 integer programs arising from a truck dispatching scheduling problem. This problem involves a special class of knapsack equality constraints. Families of facets for the polytopes associated with individual knapsack constraints are identified. In addition, a notion of ‘conflict graph’ is utilized to obtain an approximating node-packing polytope for the convex hull of all 0/1 solutions. The branch-and-cut solver generates cuts based on both the knapsack equality constraints and the approximating node-packing polytope, and incorporates these cuts into a tree-search algorithm that uses problem reformulation and linear programming-based heuristics at each node in the search tree to assist in the solution process. Numerical experiments are performed on large-scale real instances supplied by Texaco Trading & Transportation, Inc. The optimal schedules correspond to cost savings for the company and greater job satisfaction for drivers due to more balanced work schedules and income distribution.

Reviews

Required fields are marked *. Your email address will not be published.