Uso de conjunto de concentración en búsqueda tabú para problemas de rutas
ISSN: 1575-605X
Año de publicación: 2001
Volumen: 3
Número: 1
Páginas: 49-87
Tipo: Artículo
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.
Los documentos del portal se actualizan diariamente. Esta fecha hace referencia a la actualización de la información relacionada con la estructura del portal (personas, grupos de investigación, unidades organizativas, proyectos...).