A review of design and control of automated guided vehicle systems <s> Offline scheduling system <s> Abstract The vehicle routing problem ( vrp ) involves the design of a set of minimum cost routes for a fleet of vehicles which services exactly once a set of customers with known demands. The pickup and delivery problem with time windows ( pdptw ) is a generalization of the vrp which is concerned with the construction of optimal routes to satisfy transportation requests, each requiring both pickup and delivery under capacity, time window and precedence constraints. This paper presents an exact algorithm which solves the pickup and delivery problem when transporting goods. This algorithm uses a column generation scheme with a constrained shortest path as a subproblem. The algorithm can handle multiple depots and different types of vehicles. <s> BIB001 </s> A review of design and control of automated guided vehicle systems <s> Offline scheduling system <s> This paper exploits the interactions between the machine scheduling and the scheduling of the material handling system in an FMS by addressing them simultaneously. The material transfer between machines is done by a number of identical automated guided vehicles (AGVs) which are not allowed to return to the load/unload station after each delivery. This operating policy introduces an additional complexity to the problem because it results in sequence-dependent travel times for the deadheading trips between successive loaded trips of the AGVs. The problem is formulated as a nonlinear mixed integer programming model. Its objective is makespan minimization. The formulation consists of constraint sets of a machine scheduling subproblem and a vehicle scheduling subproblem which interact through a set of time window constraints for the material handling trip starting times. An iterative procedure is developed where, at each iteration, a new machine schedule is generated by a heuristic procedure, the operation completion times obtained from this schedule are used to construct time windows for the trips, and a feasible solution is searched for the second subproblem, which is handled as a sliding time window problem. The procedure is numerically tested on 90 example problems. <s> BIB002 </s> A review of design and control of automated guided vehicle systems <s> Offline scheduling system <s> Abstract This article addresses the problem of simultaneous scheduling of machines and a number of identical automated guided vehicles (AGVs) in a flexible manufacturing system (FMS) so as t minimize the makespan. For solving this problem, a genetic algorithm (GA) is proposed. Here, chromosomes represent both operation sequencing and AGV assignment dimensions of the search space. A third dimension, time, is implicitly given by the ordering of operations of the chromosomes. A special uniform crossover operator is developed which produces one offspring from two parent chromosomes. It transfers any patterns of operation sequences and/or AGV assignments that are present in both parents to the child. Two mutation operators are introduced; a bitwise mutation for AGV assignments and a swap mutation for operations. Any precedence infeasibility resulting from the operation swap mutation is removed by a repair function. The schedule associated with a given chromosome is determined by a simple schedule builder. After a number of problems are solved to evaluate various search strategies and to tune the parameters of the proposed GA, 180 test problems are solved to evaluate various search lower bound is introduced and compared with the results of GA. In 60% of the problems GA reaches the lower bound indicating optimality. The average deviation from the lower bound over all problems is found to be 2.53%. Additional comparison is made with the time window approach suggested for this same problem using 82 test problems from the literature. In 59% of the problems GA outperforms the time window approach where the reverse is true only in 6% of the problems. <s> BIB003
In the offline case, all transportation requests are known in advance. The complete vehicle routes can be optimized and constructed before vehicles carry them out. A small change in job arrival time, a change in driving time (congestion), or failure of a vehicle may impact or even destroy the whole schedule. The scheduling problem in an AGV system is similar to the pick-up and delivery problem with time windows (PDPTW), which often has travel time minimization or minimizing the number of vehicles as objectives. However, the vehicle scheduling problem in AGV systems has some characteristics differing from the PDPTW applied in a truck scheduling environment, such as higher traffic density, higher routing variation, shorter planning horizon due to stochastic load arrivals, vehicle interference and battery charging problems. The PDPTW problem is known to be NP-hard, so it is unlikely that we can find an algorithm to solve this type of problem in polynomial time. Due to this reason heuristics are the most appropriate approach to cope with this type of problem. BIB001 develop an exact algorithm, which uses a column generation scheme with a constrained shortest-path as a subproblem, to solve the PDPTW. The objective is to minimize the sum of the total travel cost. Only homogeneous vehicles (that is of a single type) are considered.  provide a survey on the general pick-up and delivery problem (GPDP). In manufacturing environments, the vehicle schedule is affected by the machine schedule. Hence, in this type of environment, the scheduling system needs to have the capability to schedule both systems at the same time. BIB002 formulate the integrated scheduling problem of machines and the AGV system as a MIP formulation. Since the problem is very difficult to solve by an exact method, they propose a heuristic for the solution. The heuristic solves two scheduling problems (machines and AGVs) iteratively until a sufficiently good result is obtained. BIB003 improve the solution quality by using a genetic algorithm to solve the integrated scheduling problem.