Dividing a Territory Among Several Vehicles

We consider an uncapacitated stochastic vehicle routing problem in which vehicle depot locations are fixed, and client locations in a service region are unknown but are assumed to be independent and identically distributed samples from a given probability density function. We present an algorithm for partitioning the service region into subregions so as to balance the workloads of all vehicles when the service region is simply connected and point-to-point distances follow some natural metric, such as any L p norm. This algorithm can also be applied to load balancing of other combinatorial structures, such as minimum spanning trees and minimum matchings.