ON MOBILE ROBOTS FLOW IN LOCALLY UNIFORM NETWORKS

In a mobile robot flow network different levels of flow intensity exis t between the origin and destination nodes as a result of different pa rt production requirements and mix. Henceforth, nodes handling heavy f lows require additional alternative paths to the rest of the network i n order to reduce blocking and traffic congestion, compared to nodes w hich handle moderate or light flows which require less alternative pat hs. In this study we make a distinction between light, moderate and he avy flows and assign one, two or three alternative node disjoint paths respectively, to handle these flows. Our aim is to find a cheapest ne twork such that for a given node subset S of an undirected graph with a cost function on its edges, and positive integers r(i), i is an elem ent of S, there are r(i) internally node disjoint paths from each i is an element of S to any other node. We denote such a problem as the lo cally uniform network design problem. This problem is a special case o f the network design problem and is NP-hard. The following results are obtained: For r(i) is an element of (1,2) we present an approximation algorithm that achieves a factor of 2. For r(i) is an element of (1, 2, 3) we present an approximation algorithm that achieves a factor of 4 and in some cases a factor of 3.