An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns

Aristide Mingozzi () and Roberto Roberti ()
Additional contact information
Aristide Mingozzi: Department of Mathematics, University of Bologna, 40126 Bologna, Italy
Roberto Roberti: VU University Amsterdam, 1081 HV Amsterdam, Netherlands

Transportation Science, 2018, vol. 52, issue 2, 229-238

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.

Keywords: decomposition method; integer programming; column generation; branch and cut and price; fixed charge; transportation problem (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0742 (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:ortrsc:v:52:y:2018:i:2:p:229-238

Access Statistics for this article

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