Abstract
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.
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.
| Original language | English |
|---|---|
| Title of host publication | Operations Research in the Service Industry : International Annual Conference of the German Operations Research Society |
| Number of pages | 1 |
| Publisher | Universitaet des Saarlandes |
| Publication date | 2007 |
| Pages | 103 |
| Publication status | Published - 2007 |
| Event | International Annual Scientific Conference of the German Operations Research Society - Saarbruecken, Germany Duration: 5 Sept 2007 → 7 Sept 2007 |
Conference
| Conference | International Annual Scientific Conference of the German Operations Research Society |
|---|---|
| Country/Territory | Germany |
| City | Saarbruecken |
| Period | 05/09/2007 → 07/09/2007 |