Scientific Program > Talks by Speaker > Larrain Homero

Exact solution methods for the multi-period vehicle routing problem with due dates
Homero Larrain  1@  , Leandro Coelho  2@  , Claudia Archetti  3@  , M. Grazia Speranza  4@  
1 : Pontificia Universidad Católica de Chile  (PUC)  -  Website
2 : Laboratoire CIRRELT Université Laval Quebec  (CIRRELT)  -  Website
Université Laval Pavillon Palasis-Prince, bureau 2642 2325, rue de la Terrasse Québec (Québec) G1V 0A6 CANADA -  Canada
3 : Department of Economics and Management - University of Brescia  (DEM)  -  Website
Contrada S. Chiara 50 - 25122 - Brescia -  Italy
4 : University of Brescia, Department of Quantitative Methods
C.da S. Chiara n. 50, Brescia, Italy -  Italy

We study the multi-period vehicle routing problem with due dates. A supplier has to determine a distribution plan to visit a set of customers over a given planning horizon. Each customer is associated with a release date and a due date, that is, the date at which the goods required by the customer become available at the supplier's depot, and the date by which the customer has to be visited, respectively. A fleet of capacitated vehicles is available at the depot to perform the distribution, and the objective is to minimize the distribution costs and the costs related to delayed deliveries. New families of valid inequalities are presented that allow us to improve a branch-and-bound algorithm from the literature. The new branch-and-bound algorithm reduces to 5.1% the optimality gap, which is 12.1% for the known branch-and-bound on instances with one vehicle. A variable MIP neighborhood descent (VMND) algorithm is also presented, which speeds up the search for high quality solutions through a local search heuristic embedded in the branch-and-bound algorithm. Computational tests are performed to assess the quality of the VMND algorithm against the new branch-and-bound algorithm. The computational results show that the VMND algorithm improves 35 out of 80 solutions on instances with one vehicle, reducing the average optimality gap from 5.1% to 3.6%. It further matches the performance of the new branch-and-bound algorithm on another 35 instances. On instances with two and three vehicles the average optimality gap obtained by the VMND algorithm is 5.5% and 5.6%, respectively.

Online user: 1 RSS Feed