Observamos que en el caso de la Mancomunidad de Servicios (MAS), tal y como tiene distribuidos las poblaciones por bases, no se nos plantea recorridos de más de veinte puntos. En este entorno los algoritmos exactos basados en MILP no nos han dado problemas. Con nuestro planteamiento utilizando MILP observamos que en alguno de los casos, como se puede ver en sus estadísticas, los tiempos de computación han llegado a varias horas para darnos un resultado coherente y en otros varios minutos, pero siempre hemos tenido una convergencia y por tanto una solución.
Este tipo de distribución de poblaciones por bases no es algo excepcional cuando se trata de recogi-da de residuos por poblaciones y, por tanto, nuestro acercamiento puede ser útil para otros casos similares y sin tener que recurrir a métodos metaheurísticos.
Cuando nos metamos en la optimización de los recorridos dentro de una población de tamaño medio-grande, cada contenedor o cada cruce de calle es un punto y por tanto podemos estar ha-blando de miles. Es muy probable que el empleo de algoritmos metaheurísticos sea indispensable.
Como puntos para ser continuados en trabajos futuros podríamos considerar los siguientes.
Continuando el nivel operativo:
· Nuestro planteamiento parte de las coordenadas geográficas de las poblaciones, Bases y estaciones y las distancias que se calculan son geométricas. Una mejora es emplear distan-cias pasándole a Google Maps nuestras coordenadas geográficas para que nos devuelva las distancias reales a través del web service adecuado.
· Basándonos en la experiencia real, afinar los supuestos como el tiempo medio de recogida de un contenedor, el tiempo de descarga y vaciado de un vehículo en la Estación de Transfe-rencia, la velocidad media de los vehículos en carretera, la distancia recorrida dentro de cada población, etc., que son parámetros de entrada de nuestro estudio.
· Elegir una o varias bases de las que han participado en este estudio y comparar los resulta-dos actuales reales con los proporcionados en nuestro planteamiento llevándolo a la práctica.
· Trabajar en la optimización de los recorridos dentro de las poblaciones como Ayamonte, Almonte, Aljaraque, Punta Umbría, etc. con un número de contenedores importante.
· Complementar este trabajo con otros modelos basados en algoritmos metaheurísticos y compararlos.
· En nuestro planteamiento nos hemos centrado en la optimización de una función objetivo que se ha considerado fundamentalmente la distancia recorrida. Sabemos que esta distancia es solo parte del coste, quizá el más importante, pero hemos descartado otras consideracio-nes que se podrían abordar en una segunda fase. Desde un punto de vista del coste:
o Trabajar con el coste del recorrido en vez del kilometraje. En este caso intervendría el consumo por tipo de vehículo, cotas de las poblaciones, Bases y Estaciones que influí-rían en el consumo con el vehículo cargado o no durante el incremento o decremen-to de la altura en el tramo del recorrido.
o Disponibilidad del vehículo. Por el simple hecho de disponer de un vehículo se use poco o mucho tiene un coste asociado a su amortización si es propio o a un alquiler si es ajeno y un coste de operarios que es independiente de su uso.
o Costes asociados al mantenimiento del vehículo que en algunos casos está relaciona-do con el kilometraje y, en otros, a las horas de utilización.
o Aunque el coste de vehículos podría inducirnos a utilizarlos en turnos durante las veinticuatro horas al día para minimizar el número de vehículos, tendríamos que relacionarlos con el coste de los operarios en los diferentes turnos y las limitaciones que tendríamos en determinadas horas del día. Este enfoque sería más abordable desde el nivel táctico que desde este nivel, donde ya partimos de los vehículos disponibles.
· Hacer un estudio de la influencia de los diferentes parámetros del modelo y parámetros internos de CPLEX en los tiempos de cómputo.
· Introducción de planos de corte en el algtoritmo de Branch and Bound que acote los espa-cios de búsqueda y reduzcan el tiempo de cómputo.
Llevar a la práctica inicialmente un estudio a nivel táctico utilizando métodos exactos y meta-heurísticos y cambiar las asignaciones actuales de las poblaciones a sus Bases y Estaciones, así como el número y tipo de vehículos a utilizar en cada base.
Y, por último, realizar un estudio estratégico para optimizar las ubicaciones de las Estaciones de Transferencia y Bases de Vehículos actuales y futuras.
1. Williams, Hilary Paul (University of Edinburgh), Model building in mathematical programming. John Wiley & Sons 1978, p177-p180.
2. Gómez Cámara, José Rubén (Escuela Politécnica Superior de la Universidad de Burgos), Diseño de un sistema de recogida de residuos urbanos: enfoque multiobjetivo y uso de metaheurísticos. Tesis doctoral. 2010
3. Lucía Gorostegui López-Alonso (Universidad Complutense de Madrid, Universidad Nacional de Educación a Distancia) Modelado, Optimización y Planificación de una Red de distribución de gas natural. Máster en Ingeniería de Sistemas y de Control.
4. JJ Ruz, Introducción a la Programación Matemática, Máster Universitario en Ingeniería de Sistemas y de Control. Universidad Complutense de Madrid y UNED.
5. Toth, P. y D. Vigo, An Overview of Vehicle Routing Problems, en Discrete Mathematics and Applications. The Vehicle Routing Problem. 2000, SIAM. p. 1-26.
6. Kulkarni, R.V. y P.R. Bhave, Integer programming formulations of vehicle routing problems. European Journal of Operational Research, 1985. 20(1): p. 58-67.
7. Russell, R. y W. Igo, ASSIGNMENT ROUTING PROBLEM. Networks, 1979. 9(1): p. 1-17.
8. Dror, M., G. Laporte y P. Trudeau, VEHICLE-ROUTING WITH STOCHASTIC DEMANDS - PROPERTIES AND SOLUTION FRAMEWORKS. Transportation Science, 1989. 23(3): p. 166-176.
9. Dror, M. y P. Trudeau, SPLIT DELIVERY ROUTING. Naval Research Logistics, 1990. 37(3): p.383-402.
10. Dror, M., G. Laporte y P. Trudeau, VEHICLE-ROUTING WITH SPLIT DELIVERIES. Discrete Applied Mathematics, 1994. 50(3): p. 239-254.
11. Archetti, C., R. Mansini y M.G. Speranza, Complexity and reducibility of the skip delivery problem. Transportation Science, 2005. 39(2): p. 182-187
12. Tillman, F., The multiple terminal delivery problem with probabilistic demands. Transportation Science, 1969. 3: p. 192-204.
13. Wilson, H., et al., Scheduling algorithms for dial-a-ride systems. . 1971, Urban system Laboratory, MIT. Technical Report USL TR-70-13: Cambridge, MA.
14. Kohl, N., et al., 2-path cuts for the vehicle routing problem with time windows. Transportation Science, 1999. 33(1): p. 101-116.
15. du Merle, O., et al., Stabilized column generation. Discrete Mathematics, 1999. 194(1-3): p. 229- 237.
16. Knight, K.W. y J.P. Hofer, VEHICLE SCHEDULING WITH TIMED AND CONNECTED CALLS - A CASE STUDY. Operational Research Quarterly, 1968. 19(3): p. 299-&.
17. Kolen, A.W.J., A. Kan y H. Trienekens, VEHICLE-ROUTING WITH TIME WINDOWS. Operations Research, 1987. 35(2): p. 266-273.
18. Desrochers, M., J. Desrosiers y M. Solomon, A NEW OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS. Operations Research, 1992. 40(2): p. 342-354.
19. Laporte, G. y Y. Norbert, Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 1987. 31: p. 147-184.
20. Laporte, G., The vehicle routing problem: an overview of exact and approximate agorithms. European Journal of Operational Research, 1992. 59: p. 345-358.
21. Clarke, G. y W. Wright, Scheduling of vehicles from a central depot to a numbre of delivery points. Operations Research, 1964. 12: p. 568-581.
22. Gillett, B.E. y L.R. Miller, HEURISTIC ALGORITHM FOR VEHICLE-DISPATCH PROBLEM. Operations Research, 1974. 22(2): p. 340-349.
23. Balinski, M. y R. Quandt, On an Integer program for a delivery problem. Operations Research, 1964. 12: p. 300-304.
24. Mole, R.H. y S.R. Jameson, SEQUENTIAL ROUTE-BUILDING ALGORITHM EMPLOYING A GENERALIZED SAVINGS CRITERION. Operational Research Quarterly, 1976. 27(2): p. 503-511.
25. Lin, S., COMPUTER SOLUTIONS OF TRAVELING SALESMAN PROBLEM. Bell System Technical Journal, 1965. 44(10): p. 2245-+.
26. Osman, I., Metastrategy Simulated Annealing and Tabu Search for the Vehicle Routing Problem. Annals of Operations Research, 1993. 41: p. 421-451
27. Rochat, Y. y E.D. Taillard, Probabilistic diversification and intensification in local earch for vehicle routing. Journal of Heuristics, 1995. 1: p. 147-167.
28. Ghaziri, H., Solving routing problem by a self-organizing map, en Artificial Neural networks, T. Kohonen, et ál., Editors. 1991: North-Holland, Amsterdam. p. 829-834.
29. Schumann, M. y R. Retzko, Self-organizing maps for vehicle routing problems-minimizing an explicit cost function, en Proceedings of the International Conference on Artificial Neural Networks, F. Fogelman-Soulie, Editor. 1995: Paris. p. 401-406.
30. Laporte, G., What you should know about the vehicle routing problem. Naval Research Logistics, 2007. 54(8): p. 811-819.
31. Reimann, M., K. Doerner y R.F. Hartl, D-Ants: Savings Based Ants divide and conquer the vehicle routing problem. Computers & Operations Research, 2004. 31(4): p. 563-591.
Capítulo 2: Especificación del problema
Capítulo 3: Modelo MILP básico