×

Hybrid metaheuristics for the vehicle routing problem with stochastic demands. (English) Zbl 1099.90505

Summary: 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.

MSC:

90B06 Transportation, logistics and supply chain management
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baeck, T., Fogel, D. and Michalewicz Z. (eds.): Evolutionary Computation 1: Basic Algorithms and Operators, Institute of Physics, Bristol, UK, 2000. · Zbl 0973.68197
[2] Bertsimas, D. J.: A vehicle routing problem with stochastic demand, Oper. Res. 40(3) (1992), 574–585. · Zbl 0764.90030
[3] Bertsimas, D. J., Chervi, P. and Peterson, M.: Computational approaches to stochastic vehicle routing problems, Trans. Sci. 29(4) (1995), 342–352. · Zbl 0853.90037
[4] 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. · Zbl 0855.90053
[5] 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. · Zbl 1099.90505
[6] 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.
[7] Birattari, M.: The Problem of Tuning Metaheuristics, as seen from a machine learning perspective, PhD thesis, Université Libre de Bruxelles, Brussels, Belgium, 2004. · Zbl 1101.68748
[8] Conover, W. J.: Practical Nonparametric Statistics, John Wiley & Sons, New York, New York, 1999.
[9] Dean, A. and Voss, D.: Design and Analysis of Experiments, Springer, Berlin Heidelberg New York, 1999. · Zbl 0910.62066
[10] Dorigo, M. and Stützle, T.: Ant Colony Optimization, MIT, 2004.
[11] 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. · Zbl 0860.90051
[12] Gendreau, M., Laporte, G. and Séguin, R.: Stochastic vehicle routing, Eur. J. Oper. Res. 88 (1996), 3–12. · Zbl 0913.90094
[13] 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). · Zbl 0864.90043
[14] Glover, F.: Tabu search – Part I, ORSA J. Comput. 1(3) (1989), 190–206. · Zbl 0753.90054
[15] 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.
[16] Haimovitch, M. and Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems, Math. Oper. Res. 10 (1985), 527–542. · Zbl 0582.90030
[17] Jaillet, P.: Probabilistic Traveling Salesman Problems, PhD thesis, MIT, Cambridge, Massachusetts, 1985.
[18] 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. · Zbl 0665.90096
[19] 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. · Zbl 0653.90032
[20] 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. · Zbl 0947.90612
[21] 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. · Zbl 1113.90356
[22] Kenyon, A. and Morton, D. P.: A survey on stochastic location and routing problems, Cent. Eur. J. Oper. Res. 9 (2002), 277–328. · Zbl 1036.90044
[23] Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P.: Optimization by simulated annealing, Science (4598) (1983), 671–680. · Zbl 1225.90162
[24] Laporte, G. and Louveaux, F.: The integer l-shaped method for stochastic integer programs with complete recourse, Oper. Res. Lett. 33 (1993), 133–142. · Zbl 0793.90043
[25] 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.
[26] 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.
[27] Secomandi, N.: Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands, Comput. Oper. Res. 27(5) (2000), 1171–1200. · Zbl 0962.90010
[28] Secomandi, N.: A rollout policy for the vehicle routing problem with stochastic demands, Oper. Res. 49(5) (2001), 796–802. · Zbl 1163.90373
[29] Sheskin, D. J.: Handbook of Parametric and Nonparametric Statistical Procedures, 2nd edn., Chapman & Hall, 2000. · Zbl 0955.62003
[30] 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. · Zbl 1049.90080
[31] 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.
[32] 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.
[33] Yang, W., Mathur, K. and Ballou, R. H.: Stochastic vehicle routing problem with restocking, Trans. Sci. 34(1) (2000), 99–112. · Zbl 1014.90020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.