A transportation problem with minimum quantity commitment

Andrew Lim, Fan Wang, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

28 Citations (Scopus)

Abstract

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
Volume40
Issue number1
DOIs
Publication statusPublished - 1 Jan 2006
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Cite this