The fixed charge transportation problem 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 also include a fixed charge. The paper describes a linear programming based heuristic approach for computing lower and upper bounds on the minimal cost. To this end, the LP relaxation is iteratively strengthened by means of adding cuts; in each iteration the current LP solution is then used to guide a local search heuristic. In addition to standard polyhedral cuts as lifted cover inequalities and flow cover inequalities, the approach also employs Fenchel cuts that are based on embedded 0-1 single node flow sets. Computational results obtained for a set of standard test problem instances are reported.
Operations Research in the Service Industry: International Annual Conference of the German Operations Research Society, 2007
Main Research Area:
International Annual Scientific Conference of the German Operations Research Society, 2007