Valid Inequality and Variable Fixation for Unrestricted Block Relocation Problems

Shuo Liu, Shixin Liu, Chao Lu, Meng Chu Zhou, Abdullah Abusorrah

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In modern logistics and smart warehouse, a terminal exists as a hub to connect multiple transportation modes and exchange goods. Solving a block relocation problem (BRP) arising from block retrieval processes in a terminal is fundamentally important to enhance the terminal's overall efficiency and save its energy. In this paper, we improve the state-of-the-art mixed integer programming (MIP) formulation of an unrestricted BRP by extracting valid inequalities from structural properties and proposing a new variable fixation method to solve it. Computational results show that the improved model can be optimally solved much more easily than the original model. Among over five-hundred benchmark instances with height limits, the improved model can solve 12.3% more than the original one. For the instances that can be optimally solved by the latter, the improved model shows six times faster speed than the latter. This work represents a significant advance in this important area.

Original languageEnglish (US)
Pages (from-to)18822-18834
Number of pages13
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number10
StatePublished - Oct 1 2022

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications


  • Block relocation problem
  • mixed integer programming
  • smart warehouse
  • valid inequality
  • variable fixation


Dive into the research topics of 'Valid Inequality and Variable Fixation for Unrestricted Block Relocation Problems'. Together they form a unique fingerprint.

Cite this