article

Optimal routing of multiple-load AGV subject to LIFO loading constraints

Authors:

G. Levitin,

R. AbezgaouzAuthors Info & Claims

Computers and Operations Research, Volume 30, Issue 3

Pages 397 - 410

https://doi.org/10.1016/S0305-0548(01)00106-X

Published: 01 March 2003 Publication History

Abstract

When simple automated guided vehicles (AGVs) having no random access load transfer mechanism are used for carrying multiple loads between workstations, the loads cannot be handled independently. This paper considers the case when loads are placed in flat pallets and each new picked up pallet is loaded on the top of batch of pallets already carried by the AGV. To avoid use of excessive space and time needed to reorder pallets in the batch, the loading-unloading procedures should be performed in accordance with last-in-first-out (LIFO) rule. In this paper we formulate the condition of existence of AGV routes in which, it visits each workstation only once and meets LIFO constraint. We also suggest an algorithm for finding the shortest one among such routes. Examples are provided to illustrate the performance of the algorithm.

References

[1]

{1} Tanchoco J, Co C. Real time control strategies for multiple-load AGVs. In: Tanchow J, editor. Material flow systems in manufacturing. London: Chapman and Hall, 1994.

Google Scholar

[2]

{2} Bilge U, Tanchoco J. AGV Systems with multi-load carriers--basic issues and potential benefits. Journal of Manufacturing Systems 1997;16(3):159-74.

Google Scholar

[3]

{3} Hodgson T, King R, Monteith S. Developing control rules for an AGVs using Markov decision processes. Material flow 1987;4(1-2):85-96.

Google Scholar

[4]

{4} Özden M. A simulation study of multiple-load carrying automated guided vehicle vehicles in a flexible manufacturing system. International Journal of Production Research 1988;26(8):1353-66.

Google Scholar

[5]

{5} Bartoldi J, Platzman L. Decentralized control of automated guided vehicles on a simple loop. IIE Transactions 1989;21(1):76-81.

Google Scholar

[6]

{6} Nayyar P, Khator S. Operation control of multi-load vehicles in an automated guided vehicle system. Computers and Industrial Engineering 1993;25(1-4):503-6.

Digital Library

Google Scholar

[7]

{7} Occeña L, Yokota T. Analysis of the AGV loading capacity in a JIT environment. Journal of Manufacturing Systems 1993;12(1):24-35.

Google Scholar

[8]

{8} Lin J, Chang C, Liu W. Load-routing control in a tandem configuration automated guided vehicle system. International Journal of Production Research 1994;32(2):411-27.

Google Scholar

[9]

{9} Lee J, Tangjarukij M, Zvu Z. Load selection of automated guided vehicles in flexible manufacturing systems. International Journal of Production Research 1996;34(12):3383-400.

Google Scholar

[10]

{10} Sinriech D, Palni L. Scheduling pickups and deliveries in a multiple-load discrete carrier environment. IIE Transactions 1998;30(11):1035-47.

Google Scholar

[11]

{11} Abezgaouz R. Optimal AGV routing subject to shifting constraints. MSc thesis, The Israel Institute of Technology, Faculty of Industrial Engineering & Management, 2000 (in Hebrew).

Google Scholar

[12]

{12} Volchenkov S. Organization of calculations that allows the use of stack memory. Engineering Cybernetics 1982;20(1).

Google Scholar

[13]

{13} Levitin G. Organization of computations that enables one to use stack memory optimally. Soviet Journal of Computer & System Science 1986;24(6):151-9.

Google Scholar

Cited By

View all

Miyamoto TInoue K(2016)Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systemsComputers and Industrial Engineering10.1016/j.cie.2015.10.01791:C(1-9)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.cie.2015.10.017
Fazlollahtabar HSaidi-Mehrabad M(2015)RETRACTED ARTICLE: Methodologies to Optimize Automated Guided Vehicle Scheduling and Routing Problems: A Review StudyJournal of Intelligent and Robotic Systems10.1007/s10846-013-0003-877:3-4(525-545)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s10846-013-0003-8
Pollaris HBraekers KCaris AJanssens GLimbourg S(2015)Vehicle routing problems with loading constraintsOR Spectrum10.1007/s00291-014-0386-337:2(297-330)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00291-014-0386-3
Show More Cited By

Index Terms

Optimal routing of multiple-load AGV subject to LIFO loading constraints
1. Applied computing
  1. Operations research
    1. Industry and manufacturing
      1. Command and control
2. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Robotics
      1. Robotic autonomy

Recommendations

Analysis of AntNet routing scheme by using queueing model

We analyzed the AntNet routing scheme's performance by using the network queueing model, and derived the optimal routing strategies to minimize the average time and variance of the end-to-end packet delay. In contrast to existing research, this paper ...
Vehicle routing problems with loading constraints: state-of-the-art and future directions

Distributors are faced with loading constraints in their route planning, e.g.,multi-dimensional packing constraints, unloading sequence constraints, stability constraints and axle weight limits. Ignoring these constraints impairs planning and induces ...
The Mx/G/1 queue with single and multiple vacations under the LIFO service regime

The M^x/G/1 queue without server vacations, with multiple vacations is studied under the LIFO service regime. For each model we derive explicit formulae for the Laplace-Stieltjes transform, mean and second moment of the waiting time W"L"I"F"O of an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 30, Issue 3

March 2003

158 pages

ISSN:0305-0548

Issue’s Table of Contents

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 March 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Miyamoto TInoue K(2016)Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systemsComputers and Industrial Engineering10.1016/j.cie.2015.10.01791:C(1-9)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.cie.2015.10.017
Fazlollahtabar HSaidi-Mehrabad M(2015)RETRACTED ARTICLE: Methodologies to Optimize Automated Guided Vehicle Scheduling and Routing Problems: A Review StudyJournal of Intelligent and Robotic Systems10.1007/s10846-013-0003-877:3-4(525-545)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s10846-013-0003-8
Pollaris HBraekers KCaris AJanssens GLimbourg S(2015)Vehicle routing problems with loading constraintsOR Spectrum10.1007/s00291-014-0386-337:2(297-330)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00291-014-0386-3
Ruan QZhang ZMiao LShen H(2013)A hybrid approach for the vehicle routing problem with three-dimensional loading constraintsComputers and Operations Research10.1016/j.cor.2011.11.01340:6(1579-1589)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.cor.2011.11.013
Confessore GFabiano MLiotta G(2013)A network flow based heuristic approach for optimising AGV movementsJournal of Intelligent Manufacturing10.1007/s10845-011-0612-724:2(405-419)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1007/s10845-011-0612-7
Côté JArchetti CSperanza MGendreau MPotvin J(2012)A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacksNetworks10.1002/net.2145960:4(212-226)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1002/net.21459
Côté JGendreau MPotvin J(2012)Large neighborhood search for the pickup and delivery traveling salesman problem with multiple stacksNetworks10.1002/net.2044860:1(19-30)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1002/net.20448
Gao XLim AQin HZhu W(2011)Multiple pickup and delivery TSP with LIFO and distance constraintsProceedings of the 24th international conference on Industrial engineering and other applications of applied intelligent systems conference on Modern approaches in applied intelligence - Volume Part II10.5555/2025816.2025836(193-202)Online publication date: 28-Jun-2011
https://dl.acm.org/doi/10.5555/2025816.2025836
Xu JChen Q(2009)Modeling and optimal control of automated trolleysProceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics10.5555/1732323.1732444(710-713)Online publication date: 11-Oct-2009
https://dl.acm.org/doi/10.5555/1732323.1732444
Erdoğan GCordeau JLaporte G(2009)The pickup and delivery traveling salesman problem with first-in-first-out loadingComputers and Operations Research10.1016/j.cor.2008.05.00536:6(1800-1808)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1016/j.cor.2008.05.005
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Analysis of AntNet routing scheme by using queueing model

Vehicle routing problems with loading constraints: state-of-the-art and future directions

The Mx/G/1 queue with single and multiple vacations under the LIFO service regime

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations