A challenging problem in real world logistics applications consists in planning service territories for customer deliveries, in contexts where customers must be clustered into groups that satisfy various conditions such as balance and connectivity. In this paper we propose new algorithms for producing such clusters based upon special procedures for exploiting Thiessen polygons. Our methods are able to handle multiple criteria for balancing the clusters, such as the number of customers in each cluster, the service revenue in each cluster, or the delivery/pickup quantity in each cluster. Computational results demonstrate the efficacy of our new procedures, which are able to assist users to plan service personal service territories and vehicle routes more efficiently.