OUT-OF-KILTER BASED HEURISTIC FOR THE INTEGER MULTICOMMODITY TRANSPORTATION PROBLEM

A new formulation of the multicommodity transportation problem is introduced whereby all supply and demand constraints, and in addition, a subset of the capacity constraints are incorporated into an equivalent single commodity, uncapacitated network. Solution of the network problem generally yields stronger lower bounds than one obtains by solving the individual single commodity transportation problems independently. A heuristic algorithm using this formulation is developed for the integer problem, and limited computational experience indicates that the new formulation does provide a significant advantage over the unconstrained approach, and solutions that are generally within seven percent of the lower bound. The application of this formulation in solving the continuous problem is also discussed.

  • Corporate Authors:

    Pergamon Press, Incorporated

    Maxwell House, Fairview Park
    Elmsford, NY  USA  10523
  • Authors:
    • EVANS, J R
    • Jarvis, J J
  • Publication Date: 1977

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00165199
  • Record Type: Publication
  • Source Agency: Engineering Index
  • Files: TRIS
  • Created Date: Mar 29 1978 12:00AM