A transportation problem with minimum quantity commitment

Andrew Lim, Fan Wang, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

34 Citations (Scopus)


We study a transportation problem with the minimum quantity commitment (MQC), which is faced by a famous international company. The company has a large number of cargos for carriers to ship to the United States. However, the U.S. Marine Federal Commission stipulates that when shipping cargos to the United States, shippers must engage their carriers with an MQC. With such a constraint of MQC, the transportation problem becomes intractable. To solve it practically, we provide a mixed-integer programming model defined by a number of strong facets. Based on this model, a branch-and-cut search scheme is applied to solve small-size instances and a linear programming rounding heuristic for large ones. We also devise a greedy approximation method, whose solution quality depends on the scale of the minimum quantity if the transportation cost forms a distance metric. Extensive experiments have been conducted to measure the performance of the formulations and the algorithms and have shown that the linear rounding heuristic behaves best.
Original languageEnglish
Pages (from-to)117-129
Number of pages13
JournalTransportation Science
Issue number1
Publication statusPublished - 1 Jan 2006
Externally publishedYes


  • Branch and cut
  • Heuristics
  • Logistics
  • Minimum quantity commitment
  • Selection and assignment

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A transportation problem with minimum quantity commitment'. Together they form a unique fingerprint.

Cite this