Applying simulation and reliability to vehicle routing problems with stochastic demands

J. ANGEL; S. GRASMAN; J. FALIN; D. RIERA; C.A. MÉNDEZ; B. RUIZ

Proceedings of the XI Conference of the Italian Association for Artificial Intelligence (AIIA09)

AIIA

Año: 2009; p. 201 - 214

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 different approaches | coming from felds like Operations Research, Artifcial 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.