|
REVISIÓN BIBLIOGRÁFICA |
Ubicación y Capacidad de Infraestructura.
El problema de ubicación y capacidad de infraestructura no es nuevo para quienes son practicantes de la investigación operativa. Las principales categorías se describen a continuación: Modelos de localización-asignación que son cubiertos por formulaciones que varían en complejidad desde formulaciones lineales, unietapa, uniproducto, sin restricciones de capacidad, determinística hasta los modelos probabilísticos no-lineales. Un resumen de la clasificación de los modelos disponibles se presenta a continuación:
1. La forma como la topografía del conjunto se ubica en el plano, lo cual influye en la métrica utilizada en este problema.
2. Los objetivos pueden ser del tipo MinSum o MinMax. Los modelos Minsum están diseñados para reducir al mínimo distancias promedio mientras que los modelos MinMax han de reducir al mínimo las distancias máximas. Los modelos minsum abarcan los problemas de localización de las empresas privadas mientras que los modelos MinMax generalmente se utilizan en la localización de infraestructura pública.
3. Los modelos sin restricciones de capacidad no restringen la asignación de la demanda. Si la limitación de la capacidad para los sitios potenciales está sobrerestringida la demanda tiene que ser asignada con cuidado y usando variables de factibilidad o déficit. En este último caso se debe examinar si una sola o múltiples instalaciones de abastecimiento son esenciales.
4. Modelos de una etapa centrada en los sistemas de distribución que cubre solamente una etapa de forma explícita. En los modelos de múltiples etapas el flujo de bienes que comprende varias etapas jerárquicas debe ser analizado.
5. Modelos de un solo producto que se caracterizan por el hecho de que la demanda, el costo y la capacidad para varios productos se pueden agregar a un producto homogéneo. Si los productos son heterogéneos su efecto en el diseño del sistema de distribución tiene que ser analizado, a saber usando modelos multiproducto.
6. Con frecuencia, los modelos de ubicación se basan en el supuesto de que la demanda es inelástica, es decir, la demanda es independiente de las decisiones espaciales. Si la demanda es elástica la relación entre, por ejemplo, la distancia y la demanda tiene que tenerse en cuenta de forma explícita. En algunos de estos casos, las funciones de minimización de costos que éstos modelos incorporan tienen que ser sustituidas, por ejemplo, por funciones de maximización de utilidad.
7. Los modelos estáticos tratan de optimizar el rendimiento del sistema en un período representativo (estratégico). En contraste, los modelos dinámicos reflejan los datos (costo, demanda, capacidad, etc) variando con el tiempo dentro de un horizonte de planificación dado.
8. En la práctica, los datos de entrada al modelo por lo general no se conocen con certeza. Los datos se basan en previsiones y, por tanto, tienen una probabilidad de estar errados. Como consecuencia, se tienen modelos deterministas si es de entrada (que se supone) conocida con certeza o modelos probabilísticos si la entrada está sujeta a incertidumbre.
9. En los modelos clásicos la asignación de la demanda se mide en forma aislada para cada par de puntos de oferta y demand. Por desgracia, si la demanda es satisfecha por medio de recorridos de entrega continuos, el costo no se puede calcular para cada par oferta/demanda por separado. Los modelos de ubicación combinados con modelos de enrutamiento dan más detalles sobre esta interrelación.
Problemas Generales de ruteo de vehículos
Esta revisión comienza con Flood (1956) planteando el Problema del Vendedor Viajero (TSP). El problema que se plantea es que un vendedor necesita visitar n puntos de la ciudad, sin importar el orden en que lo haga, cada uno exactamente una vez y en el menor tiempo posible.
Posteriormente a la aparición de el problema del vendedor viajero aparece el Problema de Ruteo de Vehículos (VRP), que es una generalización del TSP: Se cuenta con una flota de m vehículos cada uno con capacidad Q, y se necesita despachar carga a n puntos de la ciudad partiendo cada vehículo desde algún centro de acopio. Cada uno de los puntos i tiene asociada una demanda di que debe ser satisfecha por uno y solo uno de los vehículos.
Dentro de los VRP existen diversas variaciones al modelo original, por ejemplo el Problema de Ruteo de Vehículos con Ventanas de Tiempo (VRPTW) en que a cada nodo de demanda i se le asocia un par de valores (li,ui) que representan un intervalo de tiempo dentro del cual debe ser atendido el nodo i. Está el Problema de Ruteo de Vehículos con Carga/Descarga (VRPB) en el cual la demanda se puede dividir en 2 conjuntos B y L, el primero de los nodos de oferta y el segundo de nodos demanda. Cada nodo debe ser visitado una sola vez y por tan solo un vehículo y se debe satisfacer toda la oferta/demanda de los nodos. Por último se menciona el Problema de Recoger y Dejar Pasajeros (PDP) en el cual cada cliente i tiene asociado un par origen/destino (i+, i−) donde debe ser recogido/entregado respectivamente. El detalle de estos problemas se
encuentra con mayor profundidad descrito en Toth y Vigo (2002).
Métodos de solución exactos
Dentro de los métodos exactos para resolver el VRP, destacan los algoritmos del tipo Ramificación y Acotamiento (R&A), Ramificación y Corte (R&C) y Partición de Conjuntos -Generación de Columnas (PC-GC). Dentro de los algoritmos de tipo R&A, destacan los trabajos de Laporte, Mercure y Nobert (1986); Fischetti, Toth y Vigo (1994); Fisher (1994). La idea de estos trabajos es la de dar cotas inferiores a las soluciones de los respectivos problemas, por medio de relajaciones de
las variables enteras o eliminación de algunas restricciones. Con estas relajaciones se llega a problemas conocidos en la literatura con soluciones rápidas y que representan cotas para el valor del problema original.
Laporte et al. (1986) transforma el problema VRP original en un Problema de Transporte (para el caso asimétrico) o en un Problema de Asignación (para el caso simétrico) mediante la relajación de las variables enteras y la eliminación de las restricciones de capacidad. Lamentablemente las cotas obtenidas mediante esta relajación son muy pobres, obteniendo un gap promedio entre la cota y la solución óptima del problema cercana al 9% para el caso asimétrico y sobre un 30% para el caso simétrico (ver Toth y Vigo 2002).
Fischetti et al. (1994) propone dos procedimientos aditivos para calcular cotas inferiores. Los procedimientos son aditivos en el sentido de que se para la iteración i-ésima se usa como entrada la salida de la iteración (i−1)-ésima y prueba en ambos casos que la suma de las cotas obtenidas son cotas inferiores del VRP. Para uno de los procedimientos se prueba que la cota obtenida domina a la cota de Laporte et al. (1986), pero se debe pagar un costo computacional alto. Toth y Vigo (2002) muestra que las cotas obtenidas con este método son mejores que las obtenidas usando los métodos de Laporte et al. (1986) tanto para el caso simétrico como para el asimétrico.
Tanto en los trabajos de Laporte como de Fischetti, las cotas son aplicadas al comienzo del algoritmo de R&A, y se proponen distintas estrategias de ramificación. Los algoritmos de tipo R&C proponen la agregación de nuevos cortes o desigualdades válidas al polítopo factible de soluciones del problema. Las desigualdades propuestas en su mayoría son adaptaciones de cortes válidos para el TSP simétrico (STSP) (ver Cornuéjols, Fonlupt y Naddef 1985; Naddef y Rinaldi 1993). Toth y Vigo (2002) muestran con detalle como estas desigualdades se pueden aplicar al VRP. Estas desigualdades han mostrado tener bastante
éxito en la resolución de problemas, pero lamentablemente dependen mucho de la estructura particular del VRP. Otro problema que se ha encontrado es que muchas de las desigualdades válidas para este problema son deducibles a partir de la solución de problemas tan complejos como el original y se ha necesitado desarrollar heurísticas que permitan encontrar cortes de manera rápida.
Los algoritmos de tipo Partición de Conjuntos - Generación de Columnas se basan en el método de descomposición de Dantzig-Wolfe (Dantzig y Wolfe 1960). La idea clave consiste en enumerar todas las rutas factibles para todos los vehículos y resolver el problema de setcovering asociado. Lamentablemente, como la cantidad factible de rutas es exponencial en el número de nodos es inviable computacionalmente resolver directamente este problema. Una técnica para resolverlo consiste en enumerar un set más pequeño de rutas factibles y resolver el problema relajado para ese set de rutas más pequeño. Como una solución óptima de este problema no necesariamente es solución óptima del problema original (el relajado con la enumeración de todas las rutas) se usa una técnica para encontrar rutas que no estén consideradas en el subconjunto de rutas inicial, y que bajen el costo de la solución. Lamentablemente, el algoritmo para encontrar dichas rutas también es difícil computacionalmente (requiere resolver el TSP eficientemente) Agarwal, Marthur y Salkin (1989); Desrochers, Desrosiers y Solomon (1992); Bixby, Coullard y Simchi-Levi (1997) desarrollan distintas técnicas para resolver el problema de encontrar nuevas rutas.
Otra visión es la de intentar resolver directamente el problema de set-covering mediante técnicas de ramificación y corte (ver Padberg y Rinaldi 1991; Hoffman y Padberg 1993). La limitación de estos métodos es que encuentran la mejor solución para un set determinado de rutas elegido a priori, sin embargo no asegura optimalidad en el sentido de encontrar el mínimo para el set completo de rutas factibles.
Finalmente, Desrochers et al. (1992) resuelven el problema mediante un método de ramificación y precio en el cual en cada nodo del árbol de búsqueda se generan nuevas columnas y se agregan al problema. Este método a diferencia de los anteriores asegura optimalidad de las soluciones.
Flood, Merrill M. The Traveling Salesman Problem. Operations Research 4:61–75 (1956).
Toth, Paolo y Vigo, Daniele. The Vehicle Routing Problem. Society of Industrial and Applied Mathematics (SIAM) (2002).
Laporte, Gilbert, Mercure, H. y Nobert, Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks 16:33–46 (1986).
Fischetti, Matteo, Toth, Paolo y Vigo, Daniele. A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Operations Research 42:846–859 (1994).
Boctor, F. F. and Renaud J. (2000), The column-circular sub-sets selection problem: Complexity
and solutions, Computers and Operation Research, 27, 383-398.
Cornuéjols, G., Fonlupt, J. y Naddef, Denis. The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming 33:1–27 (1985).
Desrochers, Martin, Desrosiers, Jacques y Solomon, Marius M. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research 40:342–354 (1992).
Clarke, G. and Wright J. (1964), Scheduling of vehicles from a central depot to a number of
delivery points. Operations Research, 12, 568-581.
Foster, B. A. and Ryan D. M. (1976), An integer programming approach to the vehicle scheduling problem. Operational Research Quarterly, 27, 377-384.
Gendreau, M., Hertz A. and Laporte G. (1994), A tabu search heuristic for the vehicle routing
problem. Management Science, 40, 1276-1290.
Bixby, A., Coullard, C. y Simchi-Levi, D. The capacited prize-collecting traveling salesman problem (1997). Working Paper, Department of Industrial Engineering and Engineering Management, Northwestern University, Evanston, IL.
Gendreau, M, Laporte G., Musaraganyi Ch. and Taillard E. (1999), A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers and Operations Research, 26,
1153-1173.
Gheysens, F., Golden B. and Assad A. (1984), A comparison of techniques for solving the fleet size and mix vehicle routing problem. OR Spektrum, 6, 207-216.
Woods, D. G. and Harris F. C. (1979), Truck fleet size composition for concrete distribution.
International Journal of Physical Distribution, 10, 3-14.
|
