Una heurística de tipo tabú para resolver el problema de ruteo de vehículos con ventanas de tiempo suaves
Resumen
En este trabajo se describe una variante del problema de ruteo de vehículos (VRP) denominada el problema de ruteo de vehículos con ventanas de tiempo suaves (VRPSTW). Para resolver este problema se desarrolla una heurística de búsqueda tabú y una heurística de intercambio de aristas para la etapa de post optimización. El procedimiento es implementado en Mathematica 4 y fue probado en el conjunto de problemas de prueba de Salomón para el caso de ventanas duras (VRPHTW), que es un caso particular del VRPSTW. Se reportan resultados computacionales y se realizan comparaciones con los mejores resultados conocidos en la literatura.
Citas
1. Bard, Jonathan F., Kontoravdis George and Yu Gang (2002) “A Branch and cut procedure for the vehicle routing problem with time windows” Transportation Science, Vol 36, No. 2, pp. 250-269
2. Cordeau, J. Gendreau M., Laporte G., Potvin J. and Semet F. (2002) “A guide to vehicle routing heuristics” Journal of the Operational Research Society, Vol 53, pp 512-522
3. Toth, P. and Vigo D. (2002) “The vehicle routing problem” SIAM Monographs on discrete mathematics and applications Philadelphia, P.A.
4. Taillard E., Badeau P., Gendreau M., Guertin F. and Potvin J. (1997) “A Tabu search heuristic for the vehicle routing problem with soft time Windows” Transportation Science, Vol 31, No.2 pp 170-186
5. Nemhauser G. L. and Rinnooy Kam H. G. (1995) “Handbooks in Operations Research and Management Science Network Routing” Volume 8 Elsevier Science B. V. The Netherlands
6. Koskosidis Yiannis, Powell Warren, Solomon Marius (1992) “An Optimization-based heuristic for vehicle routing and scheduling with soft time window
constraints” Transportation Science, Vol. 26, No. 2, pp. 69-85
2. Cordeau, J. Gendreau M., Laporte G., Potvin J. and Semet F. (2002) “A guide to vehicle routing heuristics” Journal of the Operational Research Society, Vol 53, pp 512-522
3. Toth, P. and Vigo D. (2002) “The vehicle routing problem” SIAM Monographs on discrete mathematics and applications Philadelphia, P.A.
4. Taillard E., Badeau P., Gendreau M., Guertin F. and Potvin J. (1997) “A Tabu search heuristic for the vehicle routing problem with soft time Windows” Transportation Science, Vol 31, No.2 pp 170-186
5. Nemhauser G. L. and Rinnooy Kam H. G. (1995) “Handbooks in Operations Research and Management Science Network Routing” Volume 8 Elsevier Science B. V. The Netherlands
6. Koskosidis Yiannis, Powell Warren, Solomon Marius (1992) “An Optimization-based heuristic for vehicle routing and scheduling with soft time window
constraints” Transportation Science, Vol. 26, No. 2, pp. 69-85
