Solving a Truck Dispatching Scheduling Problem Using Branch-and-Cut

Robert E. Bixby and Eva K. Lee
Additional contact information
Robert E. Bixby: Rice University, Houston, Texas
Eva K. Lee: Georgia Institute of Technology, Atlanta, Georgia

Operations Research, 1998, vol. 46, issue 3, 355-367

Abstract: A branch-and-cut IP 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.

Keywords: Programming; integer; algorithms; cutting plane/facet generation; branch-and-cut algorithm for a structured 0/1 problem; Transportation; vehicle routing; dispatching of trucks for an oil company (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.355 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:3:p:355-367

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().