Investigacion De operaciones Set-Covering

...

A ij = {

El problema del set – covering se puede formular de la siguiente manera:

Min [pic 4][pic 5] m = características

s.a: [pic 6][pic 7] n = actividades

Xij € {0,1} xj = si la actividad j se realiza

Cj = costo unitario de la actividad j

Aij= 1 si la característica i esta en la actividad j.

Un conjunto de necesidades corresponde a las filas, y el conjunto de soluciones a la selección de columnas que cubres en forma óptima al conjunto de filas.

PROBLEMA DE APLICACIÓN DEL SET COVERING

Maximizar el área de servicio: Un criterio para elegir la solución óptima en la ubicación del problema de cobertura del conjunto

- INTRODUCCIÓN

El transporte público es una herramienta muy importante para reducir la congestión del tránsito, mejorar la condición ambiental y, en consecuencia, afectar la vida social de las personas. Por lo tanto, la necesidad de nuevas infraestructuras de transporte público para servir a nuevas ciudades y / o mejorar las estructuras de transporte existentes para hacer frente a este aumento es un impulso [1]. Planificación, diseño y gestión del transporte público son las cuestiones clave para ofrecer un modo competitivo que puede competir con el transporte privado [2].

El proceso de planificación y operación del tránsito incluye habitualmente cinco actividades básicas, generalmente realizadas en secuencia: (1) diseño de la ruta de la red, (2) establecimiento de la frecuencia, (3) desarrollo del cronograma, (4) programación del vehículo y (5) programación de la tripulación.

La importancia de la conducta es el componente más importante en la planificación del tránsito porque el costo total del sistema público de transporte depende en gran medida de ello. Una vez, se identifica un conjunto de rutas a través de la red de calles, todas las decisiones sobre el desarrollo del horario están acondicionados en este conjunto [3] - [5].

La Planificación de Tránsito también se clasifica de acuerdo con el período de diseño dirigido en etapas estratégicas, tácticas y operacionales. El diseño de la ruta constituye la etapa estratégica, el establecimiento de la frecuencia se lleva a cabo en la etapa táctica y su diseño completo en el estado operativo y el resto de las actividades se manejan en la fase operativa [6]. Si el diseño de la ruta se aborda por separado, el problema se llama Problema de diseño de la red de ruta de tránsito (TrNDP), pero si se combina con el diseño de la frecuencia, el problema se convierte en problema de diseño de red de tránsito (TNDP). Es un argumento común que la configuración de la red y la frecuencia de la red debe tratarse simultáneamente. Otro argumento puede surgir en relación con el proceso de decisión [7].

Diseño simultáneo de la ruta y la frecuencia en el TNDP por lo general aparece como problema de dos niveles. Esto se deriva de la tendencia al equilibrio entre la decisión del operador (nivel superior) y la reacción de los usuarios (nivel inferior). El diseño de la red de rutas y la frecuencia se aborda en el modelo de nivel superior, mientras que el nivel inferior se refiere al problema de asignación de pasajeros [8] - [10]. Esto añade más complejidad al TrNDP y, en consecuencia, más carga computacional.

TrNDP se clasifica como un problema combinatorio. Para cualquier red, hay un enorme conjunto de rutas de tal manera que cualquier subconjunto de él puede ser considerado como una solución potencial. Se agrega más complejidad, debido a la naturaleza multi-objetivo del diseño de la ruta de tránsito. Se asocia con la minimización de los costos tanto para el operador como para el usuario, que son objetivos conflictivos. Podría clasificarse como problema combinatorio multiobjetivo (MOCO), que a menudo impide encontrar una solución óptima única [11].

En esta investigación, la naturaleza multiobjetivo de TrNDP se analiza en términos estratégicos y políticos, sin embargo, el diseño completo se encuentra en la etapa estratégica. En la etapa de planificación estratégica, el costo del operador puede medirse en términos del tiempo total de viaje (duración) de las rutas de tránsito que refleja el costo total de operación. El uso de la información puede ser medido por la dirección de la red (desviación de la red de rutas de tránsito de los trayectos más cortos del gráfico de red (G), lo que revela el costo adicional que suponen los usuarios de tránsito), desatendiendo el efecto del tiempo de espera en la planificación a largo plazo. En cuanto al término de planeación táctica, el costo del operador puede ser medido por el tamaño requerido de la flota (costo del operador principal). El coste del usuario puede medirse con el tiempo medio total de viaje (ATT).

La estructura de este documento es la siguiente. La sección II da el estado del arte. La Sección III proporciona datos básicos de entrada. En la Sección IV se definen los objetivos y las restricciones que figuran en el presente documento. La Sección V describe la metodología de la solución adoptada. En la Sección IV se utilizan estudios de casos reales para evaluar la metodología propuesta. En la sección VI se presenta la conclusión.

- ESTADO DEL ARTE

Durante los últimos cinco decenios, se han realizado muchos estudios de investigación para investigar el TrNDP. En cada estudio, se ha considerado una función objetiva diferente en función de la visión del (de los) autor (es) del problema. Debido a la alta complejidad del problema, Heurística o Meta-heurística son siempre adoptadas para resolverlo. El enfoque pionero para la solución del problema es Una técnica heurística. Depende de encontrar un conjunto de rutas de esqueleto consideradas como una solución inicial para la etapa de diseño de la ruta. Las rutas de esqueleto usualmente vienen del camino más corto y k-más cortas pathalgorithms.Afterdefiningthe skeletonroutes, un proceso de la siembra de estos esqueletos con nuevos nodos se lleva a cabo. Los nodos sembrados se catalogan y se ordenan de acuerdo con distintas estrategias que reflejan los objetivos del diseño. La limitación de este enfoque es que el diseñador es continuamente encargado de dirigir el algoritmo [12] - [14].

A finales de los años 90, los enfoques de la Meta-heurística comenzaron a demostrar