Step fixed-charge solid transportation problem: a Lagrangian relaxation heuristic approach

Masoud Sanei, Ali Mahmoodirad, Sadegh Niroomand, Ali Jamalian, Shahin Gelareh

Research output: Contribution to journalArticlepeer-review

582 Downloads (Pure)


A new large-scale optimization problem in the field of transportation engineering is introduced in this paper as step fixed-charge solid transportation problem, where products are sent from sources to destinations by some conveyances in existence of both unit and step fixed-charges. The problem has many real-world applications in transportation area. As a moderate-sized instance of this problem becomes intractable for general-purpose solvers, we propose a dual decomposition approach, which is based on a Lagrangian relaxation and capable of tackling larger instances. The Lagrangian approach is also equipped with a Lagrangian heuristic to produce upper bounds. Our extensive numerical experiments show that the approach produces high-quality solutions in very reasonable time when compared with general-purpose solvers such as CPLEX. The applicability of the step fixed-charge solid transportation problem is also shown by a real-life example of furniture production company.
Original languageEnglish
Pages (from-to)1–21
Number of pages22
JournalJournal of Computational and Applied Mathematics
Early online date31 Oct 2015
Publication statusEarly online - 31 Oct 2015
Externally publishedYes


  • transportation problem
  • large-scale problem
  • mathematical model
  • Lagrangian relaxation
  • heuristic


Dive into the research topics of 'Step fixed-charge solid transportation problem: a Lagrangian relaxation heuristic approach'. Together they form a unique fingerprint.

Cite this