Abstract
In this paper, we propose a procedure, based on statistical design of experiments and gradient descent, that finds effective settings for parameters found in heuristics. We develop our procedure using four experiments. We use our procedure and a small subset of problems to find parameter settings for two new vehicle routing heuristics. We then set the parameters of each heuristic and solve 19 capacity-constrained and 15 capacity-constrained and route-length-constrained vehicle routing problems ranging in size from 50 to 483 customers. We conclude that our procedure is an effective method that deserves serious consideration by both researchers and operations research practitioners.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ball, M., T. Magnanti, C. Monma, and G. Nemhauser (eds.). (1995). Network Models. Amsterdam: North-Holland.
Barr, R., B. Golden, J. Kelly, M. Resende, and W. Stewart. (1995). “Designing and Reporting on Computational Experiments with Heuristic Methods.” Journal of Heuristics 1, 9–32.
Bodin, L., B. Golden, A. Assad, and M. Ball. (1983). “Routing and Scheduling of Vehicles and Crews.” Computers & Operations Research 10(2), 63–211.
Christofides, N., A. Mingozzi, and P. Toth. (1979). “TheVehicle Routing Problem.” InN. Christofides, A. Mignozzi, P. Toth, and C. Sandi (eds.), Combinatorial Optimization. Chichester, UK: John Wiley & Sons, pp. 315–338.
Coy, S. (1998). “Fine-Tuned Learning: A New Approach to Improving the Performance of Local Search Heuristics.” Ph.D. Dissertation, University of Maryland, College Park, Maryland.
Coy, S., B. Golden, G. Runger, and E. Wasil. (1997). “Solving the TSP with Sequential Smoothing.” In Proceedings of the 2nd International Conference on Computational Intelligence and Neuroscience. Research Triangle Park, North Carolina, pp. 280–283.
Gendreau, M., A. Hertz, and G. Laporte. (1991). “A Tabu Search Heuristic for the Vehicle Routing Problem.” CRT-777, Centre de Recherche sur les Transports, Université de Montréal, Montréal, Canada.
Gendreau, M., A. Hertz, and G. Laporte. (1994). “A Tabu Search Heuristic for the VRP.” Management Science 40, 1276–1290.
Gendreau, M., G. Laporte, and J.-Y. Potvin. (1997). “Vehicle Routing: Modern Heuristics.” In E. Aarts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization. London, England: John Wiley & Sons, Ltd., pp. 311–336.
Golden, B. and A. Assad (ed.). (1988). Vehicle Routing: Methods and Studies, Studies in Management Science and Systems, Vol. 16. Amsterdam, The Netherlands: North Holland.
Golden, B., E. Wasil, J. Kelly, and I-M. Chao. (1998). “The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problems Sets, and Computational Results.” In T. Crainic and G. Laporte (eds.), Fleet Management and Logistics. Boston, MA: Kluwer Academic Publishers, pp. 33–56.
Johnson, D. and L. McGeoch. (1997). “The Traveling Salesman Problem: A Case Study in Optimization.” In E. Aarts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization. London, England: John Wiley & Sons, Ltd., pp. 215–310.
Laporte, G. (1992). “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms.” European Journal of Operational Research 59, 345–358.
Montgomery, D. (1991). Design and Analysis of Experiments, John Wiley & Sons, New York.
Morgan, J. and J. Sonquist. (1963). “Problems in the Analysis of Survey Data and a Proposal.” Journal of the American Statistical Association 58, 415–434.
Osman, I. and J. Kelly. (1996). “Metaheuristics: An Overview.” In I. Osman and J. Kelly (eds.), Metaheuristics: Theory and Applications. Boston, MA: Kluwer Academic Publishers, pp. 1–21.
Park, M.-W. and Y.-D. Kim. (1998). “A Systematic Procedure for Setting Parameters in Simulated Annealing Algorithms.” Computers & Operations Research 24(3), 207–217.
Parsons, R. and M. Johnson. (1997). “A Case Study in Experimental Design Applied to Genetic Algorithms with Applications to DNA Sequence Assembly.” American Journal of Mathematical and Management Sciences 17(3/4), 369–396.
Reeves, C. (ed.). (1993). Modern Heuristic Techniques for Combinatorial Problems. New York: Halstead Press.
Robertson, S., B. Golden, and E. Wasil. (1998). “Neural Network Models for Initial Public Offerings.” Neurocomputing 18, 165–182.
Stewart, W. and B. Golden. (1984). “A Lagrangean Relaxation Heuristic for Vehicle Routing.” European Journal of Operational Research 15, 84–88.
Taillard, E. (1993). “Parallel Iterative Search Methods for Vehicle Routing Problems.” Networks 23, 661–673.
Van Breedam, A. (1996). “An Analysis of the Effect of Local Improvement Operators in Genetic Algorithms and Simulated Annealing for the Vehicle Routing Problem.” RUCA Working Paper 96/14, Faculty of Applied Economics, University of Antwerp, Antwerp, Belgium.
Van Breedam, A. (1995). “Improvement Heuristics for the Vehicle Routing Problem Based on Simulated Annealing.” European Journal of Operational Research 86, 480–490.
Xu, J., S. Chiu, and F. Glover. (1996). “Fine-tuning a Tabu Search Algorithm with Statistical Tests.” Working Paper, Graduate School of Business, University of Colorado, Boulder, Colorado.
Xu, J. and J. Kelly. (1996). “A Network Flow-based Tabu Search Heuristic for the Vehicle Routing Problem.” Transportation Science 30, 379–393.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Coy, S.P., Golden, B.L., Runger, G.C. et al. Using Experimental Design to Find Effective Parameter Settings for Heuristics. Journal of Heuristics 7, 77–97 (2001). https://doi.org/10.1023/A:1026569813391
Issue Date:
DOI: https://doi.org/10.1023/A:1026569813391