Hybrid cost and time path planning for multiple autonomous guided vehicles

摘要

In this paper, simultaneous scheduling and routing problem for autonomous guided vehicles (AGVs) is investigated. At the beginning of the planning horizon list of orders is processed in the manufacturing system. The produced or semi-produced products are carried among stations using AGVs according to the process plan and the earliest delivery time rule. Thus, a network of stations and AGV paths is configured. The guide path is bi-direction and AGVs can only stop at the end of a node. Two kinds of collisions exist namely: AGVs move directly to a same node and AGVs are on a same path. Delay is defined as an order is carried after the earliest delivery time. Therefore, the problem is defined to consider some AGVs and material handling orders available and assign orders to AGVs so that collision free paths as cost attribute and minimal waiting time as time attribute, are obtained. Solving this problem leads to determine: the number of required AGVs for orders fulfillment assign orders to AGVs schedule delivery and material handling and route different AGVs. The problem is formulated as a network mathematical model and optimized using a modified network simplex algorithm. The proposed mathematical formulation is first adapted to a minimum cost flow (MCF) model and then optimized using a modified network simplex algorithm (NSA). Numerical illustrations verify and validate the proposed modelling and optimization. Also, comparative studies guarantee superiority of the proposed MCF-NSA solution approach.