The fixed charge transportation problem generalizes the well-known transportation problem where the cost of sending goods from a source to a sink is composed of a fixed cost and a continuous cost proportional to the amount of goods sent. In this paper, we describe a new integer programming formulation with exponentially many variables corresponding to all possible flow patterns to sinks. We show that the linear relaxation of the new formulation is tighter than that of the standard mixed integer programming formulation. We describe different classes of valid inequalities for the new formulation and a column generation method to compute a valid lower bound embedded into an exact branch-and-price algorithm. Computational results on test problems from the literature show that the new algorithm outperforms the state-of-the-art exact methods from the literature and can solve instances with up to 70 sources and 70 sinks.

The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation

ROBERTI, ROBERTO;BARTOLINI, ENRICO;MINGOZZI, ARISTIDE;
2015

Abstract

The fixed charge transportation problem generalizes the well-known transportation problem where the cost of sending goods from a source to a sink is composed of a fixed cost and a continuous cost proportional to the amount of goods sent. In this paper, we describe a new integer programming formulation with exponentially many variables corresponding to all possible flow patterns to sinks. We show that the linear relaxation of the new formulation is tighter than that of the standard mixed integer programming formulation. We describe different classes of valid inequalities for the new formulation and a column generation method to compute a valid lower bound embedded into an exact branch-and-price algorithm. Computational results on test problems from the literature show that the new algorithm outperforms the state-of-the-art exact methods from the literature and can solve instances with up to 70 sources and 70 sinks.
Roberti, Roberto; Department of Electrical, Electronic; Bartolini, Enrico; Department of Mathematics and Systems Analysis, Aalto University School of Science; Mingozzi, Aristide; Department of Mathematics, University of Bologna
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/679571
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 17
social impact