Un Mecanismo de Vecindad con Búsqueda Local y Algoritmo Genético para el Problema de Transporte con Ventanas de Tiempo

Marco Antonio Cruz Chávez; Ocotlán Díaz Parra

doi:10.30973/progmat/2009.1.1/6

Autores/as

Marco Antonio Cruz Chávez CIICAp, Universidad Autónoma del estado de Morelos, MÉXICO
Ocotlán Díaz Parra CIICAp, Universidad Autónoma del estado de Morelos, MÉXICO

DOI:

https://doi.org/10.30973/progmat/2009.1.1/6

Resumen

Las técnicas de búsqueda por vecindad han resultado medios útiles para encontrar soluciones aproximadas a problemas de optimización combinatoria. Una vecindad está definida como el conjunto de soluciones cercanas a una solución inicial dada. En este artículo se presenta un mecanismo de vecindad combinado con un algoritmo genético, mostrando la etapa de análisis y diseño de la estructura de vecindad con búsqueda local combinada con un algoritmo genético para el problema de transporte con ventanas de tiempo. Este diseño hibrido se propone con la finalidad de explotar el espacio de soluciones del problema del transporte con ventanas de tiempo. La vecindad se propone con movimientos tipo uno-óptimos.

Citas

VONDOURIS, C. and TSANG, E.,: Guided Local Search for the Traveling Salesman Problem. European Journal of Operations Research. Vol. 113, pp 469-499. (1999). https://doi.org/10.1016/S0377-2217(98)00099-X

FEO, T. A. and RESENDE, M. G. C.: A Probabilistic heuristic for a computationally difficult Set Covering Problem. Operations Research Letters. Vol, 8, pp 67-71. (1989). https://doi.org/10.1016/0167-6377(89)90002-3

FEO, T. A. and RESENDE, M. G. C.: Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization. Vol. 2, pp 1-27. (1995). https://doi.org/10.1007/BF01096763

ROSING, K. E. and REVELLE, C. S. Heuristic Concentration: Two Stage solution Construction. European Journal of Operational Research. Vol. 97, pp 75-86. (1997). https://doi.org/10.1016/S0377-2217(96)00100-2

MOSCATO, P.: On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Caltech Concurrent Computation Program, C3P Report 826. (1989).

GLOVER, F.: Tabu Search: Part I. ORSA Journal on Computing. Vol. 1, pp 190-206. (1.989). https://doi.org/10.1287/ijoc.1.3.190

GLOVER, F.: Tabu Search: Part II. ORSA Journal on Computing. Vol. 2, pp. 4-32. (1990). https://doi.org/10.1287/ijoc.2.1.4

LAGUNA, M.: Scatter Search. Aparecerá en Handbook of Applied. Optimization, (1999) P. M. Pardalos and M. G. C. Resende (eds). Oxford Academic Press.

KIRPATRICK S., GELATT C. D. and VECCHI M. P.: Optimization by Simulated Annealing. IBM Research Report RC 9355. (1982).

KIRPATRICK S., GELATT C. D. and VECCHI M. P.: Optimization by Simulated Annealing. Science, Vol. 220, pp 671-680. (1983) https://doi.org/10.1126/science.220.4598.671

A. A. MARTÍNEZ MORALES.: Algoritmo Basado en Tabu Search para el Cálculo del Índice de Transmisión de un Grafo. Departamento de computación Facultad de ciencias y tecnología. FARAUTE de Ciencias y Tecnología, Vol. 1, No. 1, páginas 31-39. Universidad de Carabobo, Valencia, Estado Carabobo, Venezuela (2006).

P. TOTH and D. VIGO.: The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. Society of Industrial and Applied Mathematics. Philadelphia. USA.(2001).

WHITLEY D.: A genetic Algorithm Tutorial, Tech. Report CS-93-103, Colorado State University. (1993).

OR, I.: 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. (1.976).

LIN, S.: Computer Solutions to the Traveling Salesman Problem. Bell Syst. Tech. Jou. Vol. 44, pp 2245-2269. (1965). https://doi.org/10.1002/j.1538-7305.1965.tb04146.x

LIN, S. y KERNIGHAN, B. W.: An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research. Vol. 20, pp 498-516. (1973). https://doi.org/10.1287/opre.21.2.498

PACHECO, J. y DELGADO, C.: Resultados de Diferentes Experiencias con Búsqueda Local Aplicadas a Problemas de Rutas. Revista Electrónica Rect@.ASEPUMA, vol.2, nº 1, pp. 54- 81. (2000).

GAREY, M. R., JOHNSON, D.S.: Computers and intractability, A Guide to the theory of NP-Completeness. W.H.Freeman and Company, New York. USA.ed. (2003).

BARAJAS,N.: Estado del arte del problema de ruteo de vehículos (VRP) Colombia.Nov.(2006).

BAKER, B.M. and AYECHEW, M.A.: A genetic algorithm for the vehicle routing problem. Computers and operations research, 30(5):787-800, Apr. 2003. https://doi.org/10.1016/S0305-0548(02)00051-5

BARBAROSOGLU G. and OZGUR D.: A tabu search algorithm for the vehicle routing problem. Computers and operations research, 26(3):255-270, Mar. (1999). https://doi.org/10.1016/S0305-0548(98)00047-1

GLOVER F.: Handbook of metaheuristics. Kluwer Academic plublishers, (2002).

LAPORTE, G., GENDREAW, M., POTVIN J. Y. and SEMET, F.: Classical and modern heuristics for the vehicle routing problem. International transactions in operational research, 7(4-5):285-300, sept. (2000). https://doi.org/10.1111/j.1475-3995.2000.tb00200.x

SMITH, J.E. and EIBEN, A.E.: Introduction to evolutionary computing. (2003).

TOTH, P.: Optimization engineering techniques for the exact solution of np-hard combinatorial optimization problems. European journal of operational research, 125(2):222-238, sept. (2000). https://doi.org/10.1016/S0377-2217(99)00453-1

DE-ALBA Romenus. K.: Un procedimiento heurístico para un problema de diseño de redes multiproducto con capacidad finita y cargos fijos, Facultad de Ingeniería Mecánica y Eléctrica. Sn Nicolás de los Garza, N.L.(2004).

CHRISTOFIDES, N., MINGOZZI, A., and TOTH, P.: The vehicle routing problem. In combinatorial optimization, P. Toth, N. Christofides, R. Mingpzzi and C. Sandi (Eds.), John Wiley, New York, 315-338, 1989.

DESROCHERS, M., DESROCHERS, J. and SOLOMON, M.: A new optimization algorithm for the vehicle routing problem with time windows, Operations Research 40(2), 1992. https://doi.org/10.1287/opre.40.2.342

SAVELSBERGH, M.W.P.: Local Search for Routing Problems with time windows. Annals for Operations Research 4, 285-305, 1985. https://doi.org/10.1007/BF02022044

SOLOMON, M.M. and DESROISERS, J.: Time window constrained routing and scheduling problems: A survey. Transportation Science 22(1), 1-11, 1986.