Solving a truck dispatching scheduling problem using branch-and-cut
成果类型：
Article
署名作者：
Bixby, RE; Lee, EK
署名单位：
Rice University; University System of Georgia; Georgia Institute of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.3.355
发表日期：
1998
页码：
355-367
关键词：
摘要：
A branch-and-cut IP solver is developed for a class of structured Oil 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.