Uso de conjunto de concentración en búsqueda tabú para problemas de rutas

  1. Joaquín A. Pacheco
  2. Cristina R. Delgado
Revista:
Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Año de publicación: 2001

Volumen: 3

Número: 1

Páginas: 49-87

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openDialnet editor

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

Resumen

En este trabajo se propone un algoritmo para el problema de rutas con ventanas de tiempo, carga y descarga simultánea y flota heterogénea, basado en un proceso de Búsqueda Tabú. Lo más novedoso en este algoritmo es la incorporación en el procedimiento de intensificación de las ideas de Rosing (1.997) y Rosing y ReVelle (1.997) sobre el denominado Conjunto de Concentración. Para comprobar la eficacia tanto de este procedimiento de Intensificación, como la de todo el algoritmo, se usan instancias simuladas y diferentes librerías disponibles en la red.

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. nº 1 - 16.
  • 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.
  • CHIANG W. C. and RUSSELL R. A. (1.993). "Hybrid Heuristics for the Vehicle Routing Problem with Time Windows". Working Paper, Dpto. Quantitative Methods. University of Tulsa.
  • CLARKE G. and WRIGHT J. W. (1.964): "Scheduling of Vehicles from a Central Depot to a Number of Delevery Points". Oper.Res., 12, (1.964), 568-581.
  • DESROCHERS M., DESROSIERS J. and SOLOMON M. M. (1.992). "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows". Operations Research 40, 342-354.
  • 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.
  • DIAZ J.A. y FERNANDEZ E. (1.998). "A Tabu Search Heuristic for the Generalized Assigment Problem". Document de Recerca, Departament d´Estatistica i Investigacio Operativa. Secció Informàtica. Universitat Politècnica de Catalunya. DR 98/08
  • FISHER M. L. y JAIKUMAR R. (1.981). "A Generalized Assignment Heuristic for Vehicle Routing". Networks, vol.11, nº 2, 109-124.
  • GENDREU 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.
  • GENDREU M., HERTZ A. and LAPORTE G. (1.994): "A Tabu Search Heuristic for Vehicle Routing Problem". Management Sci.. 40 (10), pg.1276-1290.
  • GLOVER F. (1.989). Tabú Search: Part I. ORSA Journal on Computing, Vol 1, pp. 190-206.
  • GLOVER F. (1.990). Tabú Search: Part II. ORSA Journal on Computing, Vol 2, pp. 4-32.
  • GLOVER F. (1.996). Búsqueda Tabú en Optimización Heurística y Redes Neuronales. Adenso Díaz (coordinador). Paraninfo. Madrid. pp. 105-143.
  • GLOVER F. y LAGUNA M. (1.993). Tabu Search in Modern Heuristic Techniques for Combinatorial Problems. C. Reeves, ed., Blackwell Scientific Publishing, pp, 70-141.
  • GLOVER F. y LAGUNA M. (1.997). Tabu Search. Kluver Academic Publishers, Boston.
  • GLOVER F. y LAGUNA M. (1.999). Tabu Search, aparecerá en Handbook of Applied Optimization, P.M.Paradalos and M.G.S.Resende (eds). Oxford Academic Press, (1.999)
  • GOLDEN B., BODIN L., DOYLE T. y STEWART W. Jr. (1.980). "Approximate Traveling Salesman Algorithms". Operations Research, vol. 28, nº 3, parte II, 649-711.
  • 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, 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.
  • KONTORAVDIS G. and BARD J. F. (1.995): "A GRASP for the Vehicle Routimg Problem with Time Windows". ORSA Journal on Computing, 7: 10-23.
  • LAPORTE G. (1.992): "The Vehicle Routing Problem: An overview of exact and approximate algorithms". European Journal of Operations Research, 59, 345-358.
  • LAPORTE G. and OSMAN I. H. (1.995). "Routing Problems: A Bibliography". Ann.Oper. Res., 61, 227-262.
  • LENSTRA J. K. and RINNOY KAN A. H. G. (1.981): "Complexity of Vehicle Routing and Scheduling Problems". Networks, vol.11, nº 2, (1.981), 221-228.
  • LIN S. (1.965): "Computer Solutions to the Traveling Salesman Problem". Bell Syst.Tech.Jou., vol 44, 2245-2269.
  • LIN S. y KERNIGHAN B. W. (1.973): "An Effective Heuristic Algorithm for the Traveling Salesman Problem". Operations Researsch, vol.20, 498-516.
  • 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 Enginnering 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, 41, pg. 421-451.
  • PACHECO J. y DELGADO C. (1.996). Adaptación del Algoritmo de Or al VRPTW con Carga y Descarga simultánea. X Reunión ASEPELT-ESPAÑA , Albacete, Junio 1.996.
  • 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.
  • PACHECO J. y DELGADO C. (1.999). "Diseño de Metaheurísticos híbridos para Problemas de Rutas con Flota Heterogénea: GRASP". Cuadernos de Estudos Empresariales. Universidad Complutense de Madrid, nº 9, pgs.173-192.
  • PACHECO J. y DELGADO C. (2.000). "Diseño de Metaheurísticos híbridos para Problemas de Rutas con Flota Heterogénea: Concentración Heurística". Estudios de Economía Aplicada, nº 14, pp. 137-151.
  • PACHECO J. ARAGÓN,A. y DELGADO C. (1.999). "Diseño de un sistema que facilite soluciones racionales al problema del Transporte Escolar en la provincia de Burgos". XIII Reunión ASEPELT-España. Burgos, Junio 1.999.
  • PACHECO J., ARAGÓN A. y DELGADO C. (2.000). "Diseño de algoritmos para el problema del Transporte Escolar. Aplicación en la provincia de Burgos". Qüestiio, vol.24, nº 1, pp. 55-82.
  • 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.. 40 (10), pg.1276-1290.
  • REGO C. (1.998): "A Subpath Ejection Method for the Vehicle Routing Problem". Management Science, vol.44, nº 10, pg. 1447-1459.
  • REINELT G. (1.991): "TSPLIB: A Travelling Salesman Problem Library". ORSA Journal on Compouting, 3, 376-384.
  • ROCHAT Y. and TAILLARD E. D. (1.995). "Probabilistic Diversification and Intensification in Local Search for Vehicle Routing". Journal of Heuristics, 1 (1), 147-167.
  • ROSING K. E. (1.997). "Heuristic Concentration: An Introduction with Examples". The Tenth Meeting of the European Chapter on Combinatorial Optimization. Tenerife. Spain. May, 1.997.
  • ROSING K. E. and REVELLE C. S. (1.997). "Heuristic Concentration: Two Stage solution Construction". European Journal of Operational Research 97, 75-86.
  • ROSING K. E., REVELLE C. S., ROLLAND E., SCHILLING D.A. and CURRENT J. R. (1.998). "Heuristic Concentration and Tabu Search: A head to head comparison". European Journal of Operational Research 104, 93-99.
  • SAVELSBERGH M. W. P. (1.985). "Local Search for Routing Problems with Time Windows". Ann.Oper.Res., 4, 285-305.
  • SOLOMON M. M. (1.987). "Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows Constraints". Operations Research 35, 254-265.
  • TAILLARD E., BADEAU P., GENDREU M., GUERTAIN F. and POTVIN,J.Y. (1.995). "A new Neighbourhood 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 31, 170-186.
Fuente de los datos: Dialnet