Robust Partitioning for Stochastic Multivehicle Routing

The problem of coordinating a fleet of vehicles so that all demand points on a territory are serviced and the workload is most evenly distributed among the vehicles is a hard one. For this reason, it is often an effective strategy to first divide the service region and impose that each vehicle is only responsible for its own subregion. This heuristic also has the practical advantage that over time, drivers become more effective at serving their territory and customers. In this paper, we assume that client locations are unknown at the time of partitioning the territory and that each of them will be drawn identically and independently according to a distribution that is actually also unknown . In practice, it might be impossible to identify precisely the distribution if, for instance, information about the demand is limited to historical data. Our approach suggests partitioning the region with respect to the worst-case distribution that satisfies first- and second-order moments information. As a side product, our analysis constructs for each subregion a closed-form expression for the worst-case density function, thus providing useful insights about what affects the completion time most heavily. The successful implementation of our approach relies on two branch-and-bound algorithms: whereas the first finds a globally optimal partition of a convex polygon into two convex subregions, the second finds a local optimum for the harder n -partitioning problem. Finally, simulations of a parcel delivery problem will demonstrate that our data-driven approach makes better use of historical data as it becomes available.