A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem
Authors:
- 1 October 2014
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 62 (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
This publication has 43 references indexed in Scilit:
- Fixed-Charge Transportation Problem: Facets of the Projection PolyhedronOperations Research, 2012
- Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problemsAnnals of Operations Research, 2008
- Solving the variable size bin packing problem with discretized formulationsComputers & Operations Research, 2008
- k-Partition-based facets of the network design problemNetworks, 2006
- A simple heuristic for solving small fixed-charge transportation problemsOmega, 2003
- Improved Penalties for Fixed Cost Linear Programs Using Lagrangean RelaxationManagement Science, 1986
- Some branch‐and‐bound procedures for fixed‐cost transportation problemsNaval Research Logistics Quarterly, 1984
- A New Optimization Method for Large Scale Fixed Charge Transportation ProblemsOperations Research, 1981
- Edmonds polytopes and a hierarchy of combinatorial problemsDiscrete Mathematics, 1973
- Fixed‐cost transportation problemsNaval Research Logistics Quarterly, 1961