Applying simulation and reliability to vehicle routing problems with stochastic demands

J. ANGEL; S. GRASMAN; J. FAULIN; C.A. MÉNDEZ; B. RUIZ

Reggio Emilia, Italia

Conferencia; International RCRA workshop (RCRA 2009); 2009

The Vehicle Routing Problem covers a wide range of deeply studied NP problems where the aim is to serve a set of customers with a fleet of vehicles under certain constraints. Literature contains several di®erent approaches coming from fields like Operations Research, Artificial Intelligence, etc.; which try to get good (quasi-optimal) solutions for mid and large-size instances. The Vehicle Routing Problem with Stochastic Demands is an specification of the previous where demands made by clients are not deterministic. That makes uncertainty appear. Thus, a good static solution (calculated a priori) may become unfeasible when applied to real life. That adds the objective of  finding solutions flexible enough to avoid the routes failures appearance when executed. The presented approach is based on Monte Carlo Simulation, reliability indices and GRASP meta-heuristic. The idea is to provide a set of alternative solutions for the problem. These solutions, which can then be stored in a database so that the decision-maker can filter them and choose, depend on a parameter which controls the probability of route failures to appear in real time. Some numerical experiments based on well-known large-size benchmarks are included in the paper in order to illustrate our approach's performance. quasi-optimal) solutions for mid and large-size instances. The Vehicle Routing Problem with Stochastic Demands is an specification of the previous where demands made by clients are not deterministic. That makes uncertainty appear. Thus, a good static solution (calculated a priori) may become unfeasible when applied to real life. That adds the objective of  finding solutions flexible enough to avoid the routes failures appearance when executed. The presented approach is based on Monte Carlo Simulation, reliability indices and GRASP meta-heuristic. The idea is to provide a set of alternative solutions for the problem. These solutions, which can then be stored in a database so that the decision-maker can filter them and choose, depend on a parameter which controls the probability of route failures to appear in real time. Some numerical experiments based on well-known large-size benchmarks are included in the paper in order to illustrate our approach's performance.