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.
Original language | English |
---|---|
Journal | Operations Research |
Volume | 62 |
Issue number | 5 |
Pages (from-to) | 1095-1106 |
Number of pages | 12 |
ISSN | 0030-364X |
DOIs | |
Publication status | E-pub ahead of print - 2014 |
Externally published | Yes |