Resultados de diferentes experiencias con búsqueda local aplicadas a problemas de rutas

  1. J.A. Pacheco
  2. Delgado Serna, Cristina R.
Revista:
Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Año de publicación: 2000

Volumen: 2

Número: 1

Páginas: 53-81

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openDialnet editor

Otras publicaciones en: Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

Resumen

En los problemas de optimización combinatoria siempre han tenido gran importancia los Algoritmos de Búsqueda Local (o de Búsqueda Vecinal) dentro de las técnicas heurísticas, especialmente a partir de la aparición de muchas de las recientes técnicas Metaheurísticas basadas en buena parte en el uso de estos movimientos vecinales. En este trabajo se analizan algunas experiencias relacionadas con estos, aplicados al VRPTW Mixto (carga y descarga). La primera de ellas es la definición y comparación de diferentes tipos de vecindarios para elegir el más adecuado; la segunda es la determinación de qué solución se elige en cada movimiento; la tercera es el uso de una técnica estrategia Búsqueda Local Rápida que puede servir para reducir considerablemente el tiempo de computación en problemas de gran tamaño. Para estas experiencias se usan instancias simuladas.

Referencias bibliográficas

  • BACKER (DE) B., FURNON V., KILBY P., PROSSER P. and SHAW P. (1.997). "Solving Vehicle Routing Problems using Constraint Programming and Metaheuristics". Journal of Heuristics. Vol. 1 - 160.
  • BENTLEY J.L. (1.992): "Fast Algorithms for Geometric Traveling Salesman Problems". ORSA Journal on Computing. Vol. 4, pp. 387-411.
  • BODIN L.D. and GOLDEN,B.L. (1.981): "Classification in Vehicle Routing and Scheduling". Networks. Vol.11, nº 2, 97-108.
  • BULLHEIMER B., HARTI R.F. and STRAUSS C. (1.997). “Applying the Ant System for the Vehicle Routing Problem”. 2nd Metaheuristics International Conference (MIC-97), Sophie-Antipolis, France, July 1.997.
  • CAMPOS,V y MOTA, E. (1.995): "Metaheurísticos para el CVRP". XXII Congreso Nacional de Estadística e Investigación Operativa. Sevilla, Noviembre 1.995.
  • CLARKE,G. and WRIGHT,J.W. (1.964): "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points". Oper.Res. Vol. 12, pp 568-581.
  • DESROCHERS, M., LENSTRA, J. K. SAVELSBERGH, M. W. P. and SOUMIS, F. (1.988): "Vehicle Routing with Time Windows: Optimization and Approximation". In Vehicle Routing: Methods and Studies, (Studies in Management Sciences and Systems, vol.16), eds: GOLDEN,B.L. and ASSAD,A.A., Nort-Holland, 65-84.
  • FEO, T. A. and RESENDE, M. G. C. (1.989): "A Probabilistic heuristic for a computationally difficult Set Covering Problem". Operations Research Letters. Vol, 8, pp 67-71.
  • FEO, T. A. and RESENDE, M. G. C. (1.995): "Greedy Randomized Adaptive Search Procedures". Journal of Global Optimization. Vol. 2, pp 1-27.
  • GENDREAU M., HERTZ A. and LAPORTE G. (1.991): "A Tabu Search Heuristic for Vehicle Routing Problem". Report CRT-777. Centre de Recherche sur les Transports. Univ. Montréal.
  • GENDREAU M., HERTZ A. and LAPORTE G. (1.994): "A Tabu Search Heuristic for Vehicle Routing Problem". Management Sci.. 40 (10), pp.1276-1290.
  • GLOVER, F (1.989): “Tabu Search: Part I.” ORSA Journal on Computing. Vol. 1, pp. 190-206.
  • GLOVER,F (1.990). “Tabu Search: Part II.” ORSA Journal on Computing. Vol. 2, pp. 4-32. Guided Local Search (GLS) Project: http://cswww.essex.ac.uk/Research/CSP/gls.html.
  • HAOUARI M., DEJAX P. et DESROCHERS M. (1.990): "Les Problems de Tournées avec Contraintes des Fenênetres de Temps: L'Etat de l'Art". Recherche Operationnelle/Operations Research. Vol. 24, N 3, pp 217-244.
  • KILBY P., PROSSER P. and SHAW P. (1.997). “Guided Local Search for the Vehicle Routing Problem.” 2nd Metaheuristics International Conference (MIC-97), Sophie-Antipolis, France, July 1.997.
  • KIRPATRICK S., GELATT C. D. and VECCHI M. P. (1.982): "Optimization by Simulated Annealing". IBM Research Report RC 9355.
  • KIRPATRICK S., GELATT C. D. and VECCHI M. P. (1.983): "Optimization by Simulated Annealing". Science, Vol. 220, pp 671-680.
  • KONTORAVDIS,G. and BARD,J.F. (1.995): "A GRASP for the Vehicle Routing Problem with Time Windows". ORSA Journal on Computing. Vol. 7, pp 10-23.
  • LAGUNA, M. (1.999): "Scatter Search". Aparecerá en Handbook of Applied Optimization, P. M. Pardalos and M. G. C. Resende (eds). Oxford Academic Press.
  • LAGUNA, M., FEO, T. and ELROD, H. (1.994): "A Greedy Randomized Adaptive Search Procedures for the 2-Partition Problem". Operations Research. Vol. 42, N 4, pp 677-687.
  • LAGUNA,M., MARTI,R. and CAMPOS,V. (1.998): "Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem". Aceptada para su publicación en Computers & Ops.Res.
  • LAPORTE,G. (1.992): "The Vehicle Routing Problem: An overview of exact and approximate algorithms". European Journal of Operations Research. Vol. 59, pp 345-358.
  • LAPORTE, G. and OSMAN, I. H. (1.995). "Routing Problems: A Bibliography". Ann. Oper. Res. Vol. 61, pp 227-262.
  • LIN, S. (1.965): "Computer Solutions to the Traveling Salesman Problem". Bell Syst. Tech. Jou. Vol. 44, pp 2245-2269.
  • LIN, S. y KERNIGHAN, B. W. (1.973): "An Effective Heuristic Algorithm for the Traveling Salesman Problem". Operations Research. Vol. 20, pp 498-516. Memetic Algorithms' Home Page: http://densis.fee.unicamp.br/~moscato/memetic_home.html.
  • MOSCATO, P. (1.989): "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms". Caltech Concurrent Computation Program, C3P Report 826.
  • NURMI,K. (1.991): "Traveling Salesman Problem Tools for Microcomputers". Computers & Ops.Res. Vol. 18, N. 8, 741-749.
  • OR, I. (1.976). “Traveling Salesman Type Combinatorial Problems y their Relations to the Logistics of Blood Banking.” Ph. Thesis. Dpt. of Industrial Engineering y Management Sciences, Northwestern Univ.
  • OSMAN, I. H. (1.993): "Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem". Annals of Operations Research. Vol. 41, pp 421-451.
  • PACHECO J. y DELGADO C. (1.997). "Problemas de Rutas con Ventanas de tiempo y carga y Descarga simultánea: Diseño de Filtros para algoritmos de intercambio (caso de un sólo vehículo)". Estudios de Economía Aplicada, nº 7 , pgs. 79-100.
  • POTVIN,J.Y. and BENGIO,S. (1.994). "A Genetic Approach to the Vehicle Routing Problem with Time Windows". Technical Report CRT-953. Centre de Recherche sur les Transports. Univ. Montréal.
  • POTVIN J. Y., KERVAHUT T., GARCIA B. L. and ROUSSEAU J. M. (1.993)."A Tabu Search Heuristic for Vehicle Routing Problem with Time Windows". Report CRT-777. Management Sci. Vol. 40 (10), pp 1276-1290.
  • REGO, C. (1.998): "A Subpath Ejection Method for the Vehicle Routing Problem". Management Science. Vol. 44, N. 10, pp 1447-1459.
  • ROCHAT, Y. and TAILLARD, E. D. (1.995). "Probabilistic Diversification and Intensification in Local Search for Vehicle Routing". Journal of Heuristics. Vol. 1 (1), pp 147-167.
  • ROSING, K. E. and REVELLE, C. S. (1.997). "Heuristic Concentration: Two Stage solution Construction". European Journal of Operational Research. Vol. 97, pp 75-86.
  • TAILLARD E., BADEAU P., GENDREU M., GUERTAIN F. and POTVIN J.Y. (1.995). "A new Neighborhood structure for the Vehicle Routing Problem with Time Windows". Technical Repport CRT-95-66. Centre de Recherche sur les Transports. Univ. Montréal.
  • TAILLARD, E., BADEAU,P., GENDREU,M., GUERTAIN,F. and POTVIN,J.Y. (1.997). "A Tabu Search heuristic for the Vehicle Routing Problem with Time Windows". Transportation Science. Vol. 31, pp 170-186.
  • THANGIAH S. R., OSMAN I. H., and SUN T. (1.994). "Hybrid Genetic Algorithm, Simulated Annealing, and Tabu Search methods for the Vehicle Routing Problem with Time Windows". Working paper UKC/OR94/4. Institute of Mathematics and Statistics. University of Kent, Canterbury.
  • THANGIAH S. R., VINAYAGAMOORTY R., and SUN T. (1.993). "Vehicle Routing Problem with Time Deadlines using Genetic and Local Algorithms". In 5th International Conference on Genetic Algorithms, 1.993.
  • VONDOURIS, C. and TSANG, E., (1.999): "Guided Local Search for the Traveling Salesman Problem". European Journal of Operations Research. Vol. 113, pp 469-499.
Fuente de los datos: Dialnet