Robust Partitioning for Stochastic Multivehicle Routing

John Gunnar Carlsson () and Erick Delage ()
Additional contact information
John Gunnar Carlsson: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Erick Delage: Department of Management Sciences, HEC Montréal, Montréal, Quebec H3T 2A7, Canada

Operations Research, 2013, vol. 61, issue 3, 727-744

Abstract: 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.

Keywords: programming; infinite dimensional; transportation; vehicle routing (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1160 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:3:p:727-744

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().