1 Department of Mathematical Sciences, Faculty of Science, Aarhus University, Aarhus University2 Department of Mathematics, Science and Technology, Aarhus University3 Department of Mathematics, Science and Technology, Aarhus University
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