Displaying similar documents to “La combinatoria poliédrica y el problema del viajante. Aplicación al caso de ciento tres ciudades españolas.”

Del poliedro del agente viajero gráfico al de rutas de vehículos con demanda compartida.

Carmen Martínez, Enrique Mota (2000)

Qüestiió

Similarity:

En este trabajo abordamos el estudio del poliedro asociado al Problema de Rutas de Vehículos con Demanda Compartida, problema de distribución que surge cuando hay que repartir mercancías a un conjunto de clientes utilizando una flota fija de vehículos de capacidad limitada. El objetivo es diseñar las rutas de forma que se minimice la distancia total recorrida. Se diferencia de otros problemas más conocidos de rutas con capacidades en que se permite abastecer la demanda de cada cliente...

Problemas de rutas por arcos.

Enrique Benavent López, Vicente Campos Aucejo, Angel Corberan Salvador, Enrique Mota Vidal (1983)

Qüestiió

Similarity:

El objetivo de este artículo es ofrecer una visión general de la situación actual de la investigación en Problemas de Rutas por Arcos, que consisten, básicamente, en encontrar rutas óptimas que atraviesen las aristas o/y arcos de un grafo dado. Se analizan, entre otros, el Problema del Cartero Chino (definido sobre grafos dirigidos, no dirigidos o mixtos), el Problema del Cartero Rural (dirigido y no dirigido), así como el problema de los m-Carteros con alguna de sus variantes. En todos...

Análisis de heurísticos para el problema del cartero rural.

Enrique Benavent, Vicente Campos, Angel Corberán, Enrique Mota (1985)

Trabajos de Estadística e Investigación Operativa

Similarity:

En este artículo se estudia el comportamiento en el peor de los casos de dos algoritmos heurísticos propuestos para el Problema del Cartero Rural definido sobre un grafo no dirigido (RPP) y sobre un grafo dirigido (DRPP). En ambos problemas se determina el radio del peor caso de los heurísticos estudiados, que para el RPP es 3/2, mientras que para el DRPP no está acotado. Para conseguir cotas que sean más significativas, se ha determinado también este radio en función de ciertos parámetros...

Experiencias computacionales con procedimientos de identificación de restricciones para algunos tipos de programas enteros.

Jaime Barceló (1985)

Qüestiió

Similarity:

Desde los primeros trabajos de Padberg, Grötschel y otros, los procedimientos de identificación de restricciones han demostrado su utilidad en la resolución de clases especiales de problemas enteros de estructura combinatoria, tales como el del viajante de comercio, los de apareamientos en grafos, el de la mochila, etc., entre otros. Por otra parte, muchos otros tipos de problemas enteros incluyen en su estructura aspectos combinatorios, como es el caso, por ejemplo, de los...

Problemas de Knapsack 0-1 con una restricción adicional.

Jaume Barceló, E. Fernández (1988)

Qüestiió

Similarity:

En este artículo se estudian los problemas de Knapsack con una restricción adicional. Este estudio viene motivado por la aparición de problemas con esta estructura en la formulación de distintas relajaciones lagrangianas asociadas a problemas enteros. Hemos considerado dos tipos de problemas: unos tienen las dos restricciones del mismo sentido, mientras que los otros las tienen de distinto sentido. Para ambos tipos de problemas presentamos algoritmos de enumeración implícita para su...

Cotas inferiores para el QAP-árbol.

Enrique Benavent López (1985)

Trabajos de Estadística e Investigación Operativa

Similarity:

El QAP-Arbol es un caso especial del problema de asignación cuadrática en que los flujos distintos de cero forman un árbol. No se requiere ninguna condición para la matriz de distancias. En este artículo presentamos una formulación del QAP-Arbol como un problema de programación lineal entera. Basándonos en esta formulación hemos construido cuatro relajaciones lagrangianas distintas que nos permiten obtener una serie de cotas inferiores para este problema. Para resolver una de estas relajaciones,...

Un algoritmo de subgradiente y un filtro adicional para la resolución del subproblema entero en la partición de Benders.

Jaume Barceló, L. Olivella (1981)

Qüestiió

Similarity:

El método de partición de Benders es particularmente útil para resolver modelos matemáticos del tipo de "multicommodity flows" o modelos econométricos del tipo de planificación descentralizada, sin embargo, en algunos casos, el subproblema entero generado por la descomposición dual es resuelto deficientemente por los procedimientos habituales de enumeración debido a su estructura matemática, carente de función objetivo e incluyendo una variable no restringida. En nuestro...

Cotas inferiores para el problema de secuenciación con restricciones sobre los recursos.

Ramón Alvarez Valdés, José Manuel Tamarit Goerlich (1984)

Qüestiió

Similarity:

El trabajo explora dos vías de obtención de cotas inferiores para el problema de secuenciación de actividades con restricciones sobre los recursos, a partir de una formulación entera del problema. Una primera cota se obtiene de la relajación lineal y la aplicación sucesiva de planos de corte. El segundo método utiliza la relajación lagrangiana. El problema relajado se descompone en dos subproblemas para los que se proponen algoritmos de resolución. Se incluyen resultados computacionales...

Heurístico para los problemas de rutas con carga y descarga en sistemas LIFO.

Joaquín A. Pacheco (1997)

Qüestiió

Similarity:

En este trabajo se propone un algoritmo heurístico para el "Problema de Carga y Descarga (PDP) con un solo vehículo sin restricciones de capacidad en sistemas de descarga LIFO", -es decir, en cada momento sólo se puede descargar la última mercancía que ha entrado en el vehículo de entre todas las que se encuentran en él-. Este algoritmo es una extensión y adaptación del método de Or para el Problema del Viajante (TSP) que sirve también para matrices asimétricas. Con este heurístico se...