Balancing workloads of service vehicles over a geographic territory
John Gunnar Carlsson, Erik Carlsson, Raghuveer Devulapalli · 2013
Autonomous vehicles (or drones) are very frequently used for servicing a geographic region in numerous applications. Given a geographic territory and a set of n fixed vehicle depots, we consider the problem of designing service districts so as to balance the workload of a collection of vehicles which service this region. We assume that the territory is a connected polygonal region, i.e. a simply connected polygon containing a set of simply connected obstacles. We give a fast algorithm, based on an infinite-dimensional optimization formulation, that divides the territory into compact, connected sub-regions, each of which contains a vehicle depot, such that all regions have equal area. We also show how we can use this algorithm to find better locations of the vehicle depots.