A branch-and-price algorithm for the Vehicle Routing with Stochastic Demands, Probabilistic Duration Constraint, and Optimal Restocking Policy - J J Salazar ( Universidad de la Laguna, Tenerife)
Wednesday 21 August 2019, 1:00pm to 2:00pm
Professor J.J. Salazar will present a seminar to the Management Science Department
Abstract: When customers' demands are stochastic,the duration of the routes are also stochastic. We consider the vehicle routing problem with stochastic demands and probabilistic duration constraints where we must design a set of routes with minimal total expected cost, visiting all customers, and such that the duration of each route, with some high probability, does not exceed some prescribed limit. We assume that the "Optimal Restocking Policy" is applied, which means that, before starting a route, the drive is given with a sequence of customers to serve, and with threshold values to check whether the vehicle must continue directly to the next customer in the sequence, or restock at the depot before. This is a more convenient and sophisticated policy than the "detour-to-depot policy", commonly used in the literature and where the driver is only given with the customer sequence and must keep following the route until it failures or ends at the depot.
We solve the problem to optimality for the first time with a novel branch-and-price algorithm. An orienteering-based completion bound is proposed to control the growth of labels in the pricing algorithm. New procedures are developed to keep track of the variance of the duration of a route. The feasibility of an a-priori route is verified either by applying Chebyshev's bounds, or by Monte Carlo simulation and statistical inference. Consistency checks are incorporated into the branch-and-price framework to detect statistical errors. Computational experiments are performed with demands following binomial, Poisson, or negative binomial probability distributions, and with duration constraints enforced at levels of 90%, 95% and 98%. The vehicle capacity is considered in the objective function to force the vehicle going to the depot when convenient. Then, optimal solutions may contain a-priori routes that serve an expected demand larger than the capacity of the vehicle. These solutions actively employ optimal restocking to reduce travelling costs and the number of required vehicles when compared to the detour-to- depot policy solutions. Sensitivity analyses indicate that over-dispersed demands and strict duration constraints negatively impact the solution, both in terms of total expected cost and number of routes employed.
This content is part of an on-going research work together with Alexandre Florio, Richard Hartl and Stefan Minner.
Bio: J.J. Salazar is Professor of Operational Research at Universidad de La Laguna (Tenerife, Spain).
He got his PhD at University of Bologna (Italy) in 1992 on Vehicle Routing, and has continued working on related problems in Transportation, Telecommunication, Scheduling,...
His main area of interest are models and algorithms for difficult Combinatorial Optimization problems.
He has published around 100 research articles that can be found in Google Scholar: http://scholar.google.es/citations?user=pd7y0AcAAAAJ&hl=en&oi=ao
Research id: http://www.researcherid.com/rid/C-3671-2014
Most of them are in journals like "European Journal of Operational Research", "Transportation Science","Computers & Operations Research", "Mathematical Programming",...
He has been involved in several research project founded by the European Union, some of them related to Research on Official Statistics(Confidentiality, Data Cleaning,...).
He worked on a contract for the Office of National Statistics (ONS), London, 2004-2006. He is Editor-in-Chief of the Springer journal TOP https://link.springer.com/journal/11750 and in the Editorial Board of other journals like OMEGA https://www.journals.elsevier.com/omega, EURO Journal on Computational Optimization https://link.springer.com/journal/13675, INFOR: Information Systems and Operational Research https://www.tandfonline.com/toc/tinf20/current
He has been visitor of the School of Management Science(Lancaster University) since 2012, for three months every year, and published some articles with Adam Letchford; see e.g. https://doi.org/10.1016/j.ejor.2018.06.002
+44 1524 592408