Given a connected network with arc set R where every arc (i,j) has a service time t(i,j), arcs with zero travel time are added to R such that the resulting network with arc set R' has exactly two arcs between every pair of nodes. The Arc Partitioning Problem is to break R' into connected subnetworks (partitions) such that the workload in each partition is about the same, each arc in R' is assigned to one and only one partition and both arcs between a pair of nodes are assigned to the same partition. In this paper, the authors present the Arc Partitioning Algorithm (APA). As demonstrated in the computational results in this paper, the APA is a robust procedure that produces extremely well balanced solutions to this Arc Partitioning Problem.