Positioning Automated Guided Vehicles in a Loop Layout

We address the problem of determining the home positions for m automated guided vehicles (AGVs) in a loop layout where n pickup points are positioned along the circumference (m<n). A home position is the location where idle AGVs are held until they are assigned to the next transportation task. The home positions need to be selected so as to minimize an objective function of the response times, where the response time for a pickup point is defined as the travel time to the pickup point from the nearest home location. For the unidirectional flow system, where all AGVs can move in one direction only, we first point out that the problem of minimizing an arbitrary regular cost function can quite straightforwardly be solved in O(n2) time if m=1 and in O(mnm) time if m2, which is polynomial for a fixed number m of AGVs. For m3, we can do better, however: we derive a generic O(mn3) time and O(mn) space dynamic programming algorithm for minimizing any regular function of the response times. For minimizing maximum response time a further gain in efficiency is possible: this problem can be solved in O(n2) time if m=2 and O(n2 logn) time if m3. Our results improve on earlier published work, where it was suggested that problems with m2 are NP-hard. For the bidirectional flow system, where the AGVs can move in both directions, the problem of determining the home locations is inherently much more difficult. Important objective functions like average response time and maximum response time can nonetheless still be minimized by the same types of algorithms and in the same amount of time as their unidirectional counterparts, once restrictive conditions apply such that the case m=1 can be solved in polynomial time. One such restrictive condition is that each AGV travels at constant speed.

• View at Publisher
• View at Scopus