Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : Designing driver work areas for pickup & delivery operations
CONFÉRENCIER : Jonathan F. Bard, The University of Texas at Austin, États-Unis
DATE et ENDROIT : 11 décembre 2012, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Jean-François Cordeau
RÉSUMÉ : This talk addresses the problem of constructing a set of work areas for regional pickup and delivery operations. The goal is to find the minimum number of compact clusters (homogeneous vehicles) that satisfy volume, time, and contiguity constraints. Because practical instances contain anywhere from 6,000 to 50,000 data points and can only be described in probabilistic terms, it is not possible to obtain provably optimal solutions to the proposed model. Instead, a novel solution methodology is developed that combines a grid-search metaheuristic with a set covering post-processor. To reduce the problem size, a fraction of the data points are aggregated in a preprocessing phase with the help of a new weighting scheme to estimate “time to next customer.” Two metaheuristics are presented; the first is built around diversification and intensification ideas, the second relies column generation to solve a set covering problem. In the testing, six data sets provided by the sponsoring company were analyzed. All runs for the metaheuristic took less than 3 minutes, and in all but one case produced a sizable improvement over the current service area configurations. The column generation approach took significantly longer to converge but gave marginally better results.