Métodos Exactos De Solución Para Los Problemas De Localización Con Los Costos De Transporte Uncapacitated Convexos

Métodos exactos de solución para los problemas de localización con los costos de transporte uncapacitated convexos

Abstracto

En este trabajo se estudian los métodos exactos de solución de problemas de las instalaciones uncapacitated localización donde los costos de transporte son no lineales y convexas. Una linealización exacta de los costes se hace, lo que permite la formulación del problema como un extendido, modelo lineal puro cero una ubicación. Un método de ramificación y la envolvente sobre la base de un ascenso doble y procedimiento de ajuste se desarrolla, y en comparación con la aplicación de un método de descomposición de Benders modificada. La aplicación específica estudiado es el problema de localización de plantas simple (SPLP) con interacción espacial, que es un modelo adecuado para la ubicación de las instalaciones públicas. Métodos de solución previamente aproximados se han utilizado para este problema, mientras que en este trabajo investigar métodos exactos de solución. Los resultados computacionales se presentan.

Palabras clave

• Programación matemática ;

• Lugar ;

• Dual ascenso ;

• Branch-and-bound ;

• Descomposición de Benders

________________________________________

1. Introducción

Modelos de instalaciones de localización de diferentes tipos han sido ampliamente tratado en la literatura.En el problema de localización de plantas simple (SPLP), véase, por ejemplo Cornuejols et al. (1990) , y la mayoría de otros modelos de ubicación discretas, la estructura del transporte entre las instalaciones y los puntos de cliente se obtiene minimizando los costes de transporte lineales. En algunos modelos, sin embargo, los costos de transporte son no lineales y convexas. Esto, junto con los costes de producción cóncavas (los cargos fijos de las instalaciones) por lo general hace que los problemas más difíciles. (EnHolmberg y Tuy (1993) otro modelo con esta dificultad específica, ambas funciones no lineales cóncavas y convexas de costos, se trata).

En este trabajo se estudian los métodos de solución de problemas de las instalaciones uncapacitated ubicación con generales no lineales separables costos de transporte convexos. Suponemos requisitos enteras en las cantidades transportadas (que se satisface automáticamente en el SPLP, pero puede no ser en nuestro modelo), lo cual nos permite realizar una linealización exacta de los costes no lineales. De esta manera se obtiene una relación lineal, puro cero un modelo, al precio de un aumento significativo del número de variables. A continuación, investigar métodos exactos de solución para este modelo. En algunos casos, los costes de transporte no lineales son el resultado de una reformulación del modelo original. Nosotros, en este trabajo sobre todo estudiar uno de estos casos, se discute más adelante.

La minimización frecuente de los costes de transporte (lineal) es a menudo muy natural cuando se trata de transporte de mercancías. Sin embargo, en público los problemas de ubicación de las instalaciones de los clientes suelen ser libre de hacer su propia elección de centro. Modelado de tales situaciones, el objetivo no sólo puede ser reducir al mínimo el transporte total y los costes de las instalaciones. El efecto de lainteracción espacial se ha utilizado para mejorar los modelos de localización de este tipo. SPLP con la interacción espacial entre los viajeros han sido tratados en Coelho y Wilson, 1976 , Leonardi, 1978 ,Leonardi, 1983 , Erlenkotter y Leonardi, 1985 , Jacobsen, 1986 y Jacobsen, 1988 , modelado como un problema no lineal, programación entera mixta. En Holmberg y Jörnsten (1990) un modelo diferente se deriva, llamado el "exacta" formulación de SPLP con la interacción espacial, ya que las aproximaciones que producen términos de entropía se evitan. El modelo resultante es un problema de programación lineal entero, con una estructura especial que puede ser explotada por varios métodos de solución diferentes.

Métodos aproximados de solución para este problema se han propuesto e investigado en los informes anteriores. Un procedimiento de ascenso dual para este problema se ha desarrollado, ver Holmberg y Jörnsten (1996a) . Otro método, basado en la misma doble, es la relajación lagrangiana y optimización subgradiente, investigado en Holmberg y Jörnsten (1996b) . Métodos de solución basadas en técnicas de descomposición primal y dual también se puede utilizar, ver Holmberg y Jörnsten (1995) . Para obtener un método de solución exacta para el problema, en este trabajo incrustar el método de doble ascenso en un marco branch-and-bound. Nosotros comparamos este método de solución a una versión modificada de descomposición de Benders, que se encontró que era más eficaz en Holmberg y Jörnsten (1995) . En la sección 2 se presenta el modelo general, y en la sección 3 se discute el caso especial de la SPLP con la interacción espacial. Sección 4 está dedicado a los métodos de solución. En la sección 4.2 se revisa el método de doble subida, en la Sección 4.3 se describe el marco branch-and-bound para el método de doble ascenso de unSección 4.4 se revisa el método modificado Benders descomposición. En la sección 4.5hemos ultimar los métodos que se comparan, y en la sección 5 se presentan los resultados computacionales

...