مسیریابی بهینه موضوع AGV بارگذاری متعدد برای محدودیت های بارگذاری LIFO

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. Scope and purpose The loads transfer task is defined by an oriented graph G=(V,E) in which vertices View the MathML source correspond to loading/unloading nodes in a network. Arc (vi,vj)∈E corresponds to existence of load to be transferred from node vi to node vj. The distance between each pair of nodes is defined by a matrix View the MathML source. An autonomous agent has to deliver loads in accordance with graph G. The loads are stored in the stack of the agent and are loaded and unloaded using last-in-first-out (LIFO) rule. To fulfill the transfer task the agent has to pass through all the existing vertices in some order that ensures that for each arc (vi,vj)∈E vertex vi is visited before vertex vj. Conditions of existence of a sequence of vertices which allow all the loads to be transferred without violating LIFO rule and visiting each vertex only once are formulated. An algorithm for finding the shortest tour meeting LIFO constraints is developed. The possible applications of the algorithm are scheduling automated guided multiple load vehicles or routing autonomous intelligent agents with stack memory organization in computer networks.

Automated guided vehicles (AGVs) with multiple load carrying capacities are widely used in modern automated manufacturing as an alternative to increasing size of single load AGVs fleet. A multiple-load vehicle can accomplish material transportation tasks by simultaneously carrying on a board a number of loads with different destinations [1]. This is especially beneficial in manufacturing systems where loading–unloading process is much more time-consuming than transportation. Indeed, using multi-load AGVs allows for minimization of loading–unloading procedures by picking up batches of loads with different destinations and unloading batches of loads coming from different sources at each workstation. The maximum benefit from using multiple load AGVs can be achieved when no limitations on AGV carrying capacity are imposed and all the loads can be loaded and unloaded independently [2]. The last condition requires AGVs to be equipped with shuttle tops or roller decks, which makes vehicles expensive and prevents them to be compact (which is especially important for systems operating in limited spaces). Different aspects of multiple-load AGV management are studied in works of Hodgson et al. [3], Özden [4], Bartoldi and Platzman [5], Nayyar and Khator [6], Occena and Yokota [7], Tanchoco and Co [1], Lin et al. [8], Lee et al. [9] and Sinriech and Palni [10]. These works deal basically with effect of AGV load capacity and with AGV dispatching when loads can be handled independently. A comprehensive review of these studies is provided by Bilge and Tanchoco [2]. In many cases simple AGVs are also used for carrying multiple loads. Since simple AGVs have no facilities for handling different loads independently, excessive unloading and loading procedures are often required at a workstation to access loads destined to it if loads destined to other workstations block them. When materials are transported in flat containers (pallets), each pallet picked up by AGV is placed on the top of batch of pallets loaded previously. In this case unloading of arbitrary pallet is possible only after unloading of all the pallets located above it. If AGV arrives to some workstations having pallets destined to other workstations above pallets destined to this workstation, the former should be unloaded from the AGV and loaded back after unloading proper pallets. This procedure requires special space to store temporarily unloaded pallets and time to carry out excessive loading and unloading (further referred to as rearrangement). To avoid space and time wastes the AGV route can be planned in a way that prevents rearrangements. Such routes should meet last-in-first-out (LIFO) condition in which pallet loaded last (on the top of batch) is unloaded first. It can be easily seen that LIFO condition can always be met by visiting some workstations several times (single load AGVs always meet LIFO condition but make a lot of excessive travels between stations). 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. It is assumed that no limitations on the AGV capacity are imposed. Another assumption is that the distance between pick up and delivery positions for the same workstations are much less than the distances among different workstations (in most cases the pick up and delivery positions coincide). If the route meeting LIFO constraint and visiting each workstation only once does not exist, the transportation problem can be solved by three different ways: 1. using additional AGVs, 2. visiting some workstations more than once, 3. performing excessive unloading and loading procedures. In the first case the transportation problem is decomposed to several smaller ones, each of which can be solved by the suggested algorithm. In the second and third cases the sum of travel and loading–unloading times minimization problem can be formulated. To solve these problems a heuristics can be used based on the suggested algorithm [11]. Observe that the suggested algorithm deals with a fixed set of transfer requirements, which means it cannot be applied directly in dynamic environment where new transfer requests appear during accomplishment of a given transportation task. One of possible solutions of the dynamic transportation problem is division of the transfer requests according to certain decision epochs so that a rout for each epoch is kept unchanged until finished. The number of requests in each epoch can be determined by technological reasons or by efficiency of optimal routing problem solution. In the later case, the routing problem should be solved for several sets of transfer requests before the AGV starts its route.

This paper presents an algorithm for finding shortest tour meeting LIFO constraints for a set of transportation tasks. It is assumed that the set of tasks cannot be changed during their accomplishment (static problem) and that the transporter load capacity is unlimited. The algorithm can be used for routing of multiple-load AGV in production system environment or for routing of autonomous intelligent agents in computer networks. Conditions are formulated for existence of a single route meeting LIFO constraints for a given oriented graph representing a transportation task. If the conditions are met, the algorithm finds the minimum length path that visits each station once and obeys LIFO rule. The graphs not meeting the conditions can be transformed to feasible ones by duplicating some nodes. This procedure corresponds to visiting some stations several times. It is shown that the algorithm finds the optimal path for moderate size problems in a short time. The crucial factor influencing the computation time is the maximal number of transfer requirements with the same destination (maximal HDI of the graph vertices).