Abstract
This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baeck, T., Fogel, D. and Michalewicz Z. (eds.): Evolutionary Computation 1: Basic Algorithms and Operators, Institute of Physics, Bristol, UK, 2000.
Bertsimas, D. J.: A vehicle routing problem with stochastic demand, Oper. Res. 40(3) (1992), 574–585.
Bertsimas, D. J., Chervi, P. and Peterson, M.: Computational approaches to stochastic vehicle routing problems, Trans. Sci. 29(4) (1995), 342–352.
Bertsimas, D. J. and Simchi-Levi, D.: A new generation of vehicle routing research: Robust algorithms, addressing uncertainty, Oper. Res. 44(2) (1996), 216–304.
Bianchi, L., Birattari, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O. and Schiavinotto, T.: Research on the vehicle routing problem with stochastic demand. Technical Report IDSIA-07-04, IDSIA, March 2004.
Birattari, M.: On the estimation of the expected performance of a metaheuristic on a class of instances. How many instances, how many runs? Technical Report TR/IRIDIA/2004-01.2, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium, 2004.
Birattari, M.: The Problem of Tuning Metaheuristics, as seen from a machine learning perspective, PhD thesis, Université Libre de Bruxelles, Brussels, Belgium, 2004.
Conover, W. J.: Practical Nonparametric Statistics, John Wiley & Sons, New York, New York, 1999.
Dean, A. and Voss, D.: Design and Analysis of Experiments, Springer, Berlin Heidelberg New York, 1999.
Dorigo, M. and Stützle, T.: Ant Colony Optimization, MIT, 2004.
Gendreau, M., Laporte, G. and Séguin, R.: An exact algorithm for the vehicle routing problem with stochastic demands and customers, Trans. Sci. 29(2) (1995), 143–155.
Gendreau, M., Laporte, G. and Séguin, R.: Stochastic vehicle routing, Eur. J. Oper. Res. 88 (1996), 3–12.
Gendreau, M., Laporte, G. and Séguin, R.: A tabu search heuristic for the vehicle routing problem with stochastic demands and customers, Oper. Res. 44(3) (1996).
Glover, F.: Tabu search – Part I, ORSA J. Comput. 1(3) (1989), 190–206.
Gutjahr, W.: S-ACO: An ant-based approach to combinatorial optimization under uncertainty, in Proceedings of ANTS 2004 – Ant Colony Optimization and Swarm Intelligence, volume 3172 of Lecture Notes in Computer Science, Springer, Berlin Heidelberg New York, 2004, pp. 238–249.
Haimovitch, M. and Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems, Math. Oper. Res. 10 (1985), 527–542.
Jaillet, P.: Probabilistic Traveling Salesman Problems, PhD thesis, MIT, Cambridge, Massachusetts, 1985.
Jaillet, P.: A priori solution of a travelling salesman problem in which a random subset of the customers are visited, Oper. Res. 36(6) (1988), 929–936.
Jaillet, P. and Odoni, A.: in B. L. Golden and A. A. Assad (eds.), Vehicle Routing: Methods and Studies, chapter The probabilistic vehicle routing problems, Elsevier, Amsterdam, The Netherlands, 1988.
Johnson, D. S. and McGeoch, L. A.: The travelling salesman problem: A case study in local optimization, in E. H. L. Aarts and J. K. Lenstra (eds.), Local Search in Combinatorial Optimization, Wiley, New York, USA, 1997, pp. 215–310.
Johnson, D. S. and McGeoch, L. A.: Experimental analysis of heuristics for the STSP, in G. Gutin and A. Punnen (eds.), The Traveling Salesman Problem and its Variations, Kluwer, Dordrecht, The Netherlands, 2002, pp. 369–443.
Kenyon, A. and Morton, D. P.: A survey on stochastic location and routing problems, Cent. Eur. J. Oper. Res. 9 (2002), 277–328.
Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P.: Optimization by simulated annealing, Science (4598) (1983), 671–680.
Laporte, G. and Louveaux, F.: The integer l-shaped method for stochastic integer programs with complete recourse, Oper. Res. Lett. 33 (1993), 133–142.
Lourenço, H. R., Martin, O. and Stützle, T.: in F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management, chapter Iterated Local Search, Kluwer, Boston, USA, 2002, pp. 321–353.
Or, I.: Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Blood Banking, PhD thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 1976.
Secomandi, N.: Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands, Comput. Oper. Res. 27(5) (2000), 1171–1200.
Secomandi, N.: A rollout policy for the vehicle routing problem with stochastic demands, Oper. Res. 49(5) (2001), 796–802.
Sheskin, D. J.: Handbook of Parametric and Nonparametric Statistical Procedures, 2nd edn., Chapman & Hall, 2000.
Stützle, T. and Hoos, H.: in P. Hansen and C. Ribeiro (eds.), Essays and Surveys on Metaheuristics, chapter Analyzing the Run-time Behaviour of Iterated Local Search for the TSP, Kluwer Academic, Boston, USA, 2002, pp. 589–612.
Teodorović, D. and Pavković, G.: A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand, Trans. Plan. Tech. 16 (1992), 261–273.
Whitley, D., Starkweather, T. and Shaner, D.: The travelling salesman and sequence scheduling: Quality solutions using genetic edge recombination, in L. Davis (ed.), Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, USA, 1991, pp. 350–372.
Yang, W., Mathur, K. and Ballou, R. H.: Stochastic vehicle routing problem with restocking, Trans. Sci. 34(1) (2000), 99–112.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bianchi, L., Birattari, M., Chiarandini, M. et al. Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands. J Math Model Algor 5, 91–110 (2006). https://doi.org/10.1007/s10852-005-9033-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-005-9033-y