An exact algorithm for the fixed charge transportation problem based on matching source and sink patterns

Aristide Mingozzi, Roberto Roberti

Research output: Contribution to JournalArticleAcademicpeer-review

117 Downloads (Pure)

Abstract

This paper describes an exact algorithm for the fixed charge transportation problem based on a new integer programming formulation that involves two sets of variables representing flow patterns from sources to sinks and from sinks to sources. The formulation states to select a pattern for each source and each sink and to match the corresponding flows. The linear relaxation of this new formulation is enforced by adding a pseudo-polynomial number of equations that are shown to contain, as special cases, different valid inequalities recently proposed for the problem. The resulting lower bound dominates the lower bounds proposed in the literature. Such a lower bound is embedded into an exact branch-And-cut-And-price algorithm. Computational results on benchmark instances show that the proposed algorithm is several times faster than the state-of-The-Art exact methods and could solve all open instances. New harder instances with up to 120 sources and 120 sinks were solved to optimality. Z.

Original languageEnglish
Pages (from-to)229-238
Number of pages10
JournalTransportation Science
Volume52
Issue number2
Early online date27 Apr 2017
DOIs
Publication statusPublished - Mar 2018

Keywords

  • Branch and cut and price
  • Column generation
  • Decomposition method
  • Fixed charge
  • Integer programming
  • Transportation problem

Fingerprint

Dive into the research topics of 'An exact algorithm for the fixed charge transportation problem based on matching source and sink patterns'. Together they form a unique fingerprint.

Cite this