The fixed charge transportation problem (FCTP) is a well-known and difficult optimization problem with lots of applications in logistics. It consists in finding a minimum cost network flow from a set of suppliers to a set of customers. Beside costs proportional to quantities transported, transportation costs do, however, include a fixed charge.
Iterated local search and record-to-record travel are both simple local search based meta-heuristics that, to our knowledge, not yet have been applied to the FCTP. In this paper, we apply both types of search strategies and combine them into a single heuristic search procedure for the FCTP. The hybrid approach results in a relatively efficient heuristic method, capable to improve the currently best known heuristics for the FCTP on some of the test problem instances usually considered in the literature.