A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem

Erika Buson (), Roberto Roberti () and Paolo Toth ()
Additional contact information
Erika Buson: DEI, University of Bologna, 40136 Bologna, Italy
Roberto Roberti: DEI, University of Bologna, 40136 Bologna, Italy
Paolo Toth: DEI, University of Bologna, 40136 Bologna, Italy

Operations Research, 2014, vol. 62, issue 5, 1095-1106

Abstract: The fixed-charge transportation problem (FCTP) is a generalization of the transportation problem where an additional fixed cost is paid for sending a flow from an origin to a destination. We propose an iterated local search heuristic based on the utilization of reduced costs for guiding the restart phase. The reduced costs are obtained by applying a lower bounding procedure that computes a sequence of nondecreasing lower bounds by solving a three-index mathematical formulation of the problem strengthened with valid inequalities. The proposed method was tested on two sets of benchmark instances from the literature. The first set was used to evaluate the state-of-the-art heuristics for the problem; the proposed heuristic was able to provide new best-knownupper bounds on all 124 open instances. On the second set of instances, which was recently introduced for testing the currently best exact method for the problem, the new heuristic was able to provide provably good upper bounds within short computing times.

Keywords: iterated local search; reduced costs; fixed charge transportation problem (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2014.1288 (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:oropre:v:62:y:2014:i:5:p:1095-1106

Access Statistics for this article

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