Cell-Based Local Search Heuristics for Guide Path Design of Automated Guided Vehicle Systems with Dynamic Multicommodity Flow

Tatsushi Nishi, Shuhei Akiyama, Toshimitsu Higashi, Kenji Kumagai

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


This article discusses the guide path design of automated guided vehicle (AGV) systems for which we propose a model that incorporates a dynamic multicommodity flow with capacity constraints from a pickup to a delivery point. The problem is formulated as the selection of a guide path connecting a given set of pickup/delivery points. A cell-based local search that is based on an original neighborhood technique is developed. In the proposed method, the guide path is effectively optimized based on a local search of cell-based neighborhood search preserving connectivity constraints and the subsequent solution of a dynamic multicommodity flow problem. The performance of the proposed method is strengthened by the redundant elimination of arcs and intensification of search according to the concept of the flow-concentrated cell. The effectiveness of the proposed method is demonstrated by comparing it with a general-purpose solver and recent algorithms for fixed-charge capacitated multicommodity network design problems. A real case study is presented to demonstrate the applicability of the proposed method by using simulation software. Note to Practitioners - Due to the recent growth of online shipping, the design of automated warehousing systems is receiving much attention. Most automated warehousing systems introduce multiple automated guided vehicles (AGVs) for transportation. This article presents an efficient optimization of guide path design considering congestions and dynamic multicommodity flow routing. We develop cell-based local search heuristics for the guide path design problem for AGV systems that can be applied to a large-scale transportation model to solve the problem efficiently. Our major finding is that the guide path design with the dynamic multicommodity flow can significantly reduce the delays caused by congestions and improve the efficiency of the warehousing systems. The effectiveness of the derived guide path design is evaluated by simulation software. The feasibility of the guide path is confirmed in several case studies.

Original languageEnglish
Article number8932602
Pages (from-to)966-980
Number of pages15
JournalIEEE Transactions on Automation Science and Engineering
Issue number2
Publication statusPublished - Apr 2020
Externally publishedYes


  • Automated guided vehicles (AGVs)
  • block layout
  • dynamic multicommodity flow
  • flow path design
  • heuristics

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Cell-Based Local Search Heuristics for Guide Path Design of Automated Guided Vehicle Systems with Dynamic Multicommodity Flow'. Together they form a unique fingerprint.

Cite this